Token reconfiguration

<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a>, the token reconfiguration problem is a <a href="/facts/Reconfiguration/nW4XxGAR">reconfiguration</a> problem on a graph with both an initial and desired state for tokens.
</p><p>Given a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
, an initial state of tokens is defined by a subset 
  
    
      
        V
        ⊂
        V
        (
        G
        )
      
    
    {\displaystyle V\subset V(G)}
  
 of the vertices of the graph; let 
  
    
      
        n
        =
        
          |
        
        V
        
          |
        
      
    
    {\displaystyle n=|V|}
  
.  Moving a token from vertex 
  
    
      
        
          v
          
            1
          
        
      
    
    {\displaystyle v_{1}}
  
 to vertex 
  
    
      
        
          v
          
            2
          
        
      
    
    {\displaystyle v_{2}}
  
 is valid if 
  
    
      
        
          v
          
            1
          
        
      
    
    {\displaystyle v_{1}}
  
 and 
  
    
      
        
          v
          
            2
          
        
      
    
    {\displaystyle v_{2}}
  
 are joined by a path in 
  
    
      
        G
      
    
    {\displaystyle G}
  
 that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move.  A desired end state is defined as another subset 
  
    
      
        
          V
          ′
        
        ⊂
        V
        (
        G
        )
      
    
    {\displaystyle V'\subset V(G)}
  
.  The goal is to minimize the number of valid moves to reach the end state from the initial state.
</p>

Token reconfiguration open-in-new

Token reconfiguration