Introduction to reconfiguration

DOI10.3390/a11040052zbMath1461.68164OpenAlexW2754517646MaRDI QIDQ2331456

Naomi Nishimura

Publication date: 29 October 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a11040052

zbMATH Keywords

complexityalgorithmsreconfiguration problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ A polynomial version of Cereceda's conjecture ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ List-recoloring of sparse graphs ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Token sliding on graphs of girth five ⋮ Token Swapping on Trees ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ ZDD-based algorithmic framework for solving shortest reconfiguration problems ⋮ Optimally reconfiguring list and correspondence colourings ⋮ Feedback vertex set reconfiguration in planar graphs ⋮ On reachable assignments under dichotomous preferences ⋮ Order Reconfiguration under Width Constraints ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Flipping plane spanning paths ⋮ On the longest flip sequence to untangle segments in the plane ⋮ Reconfiguration of vertex-disjoint shortest paths on graphs ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Complexity results on untangling red-blue matchings ⋮ 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids ⋮ Block symmetries in graph coloring reconfiguration systems ⋮ The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs ⋮ On reconfiguration graphs of independent sets under token sliding ⋮ Token sliding on graphs of girth five ⋮ Extremal independent set reconfiguration ⋮ Mixing is hard for triangle-free reflexive graphs ⋮ Digraph redicolouring ⋮ Reconfiguration graphs of zero forcing sets ⋮ Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters ⋮ Sequentially swapping tokens: further on graph classes ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ Reconfiguration of time-respecting arborescences ⋮ Unnamed Item ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles ⋮ Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ Token shifting on graphs ⋮ Reconfiguration of cliques in a graph ⋮ Editorial: Special issue on reconfiguration problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ Paths between colourings of graphs with bounded tree-width ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Optimal reconfiguration of optimal ladder lotteries ⋮ Approximating Shortest Connected Graph Transformation for Trees ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Cyclic shift problems on graphs ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Linear transformations between dominating sets in the TAR-model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Dominating sets reconfiguration under token sliding ⋮ A Thomassen-type method for planar graph recoloring ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Reconfiguring dominating sets in minor-closed graph classes ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\) ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ The Perfect Matching Reconfiguration Problem ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Reconfiguration graphs for dominating sets ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Cliques in realization graphs ⋮ Hamilton paths in dominating graphs of trees and cycles ⋮ On reconfigurability of target sets ⋮ A triangle process on regular graphs ⋮ Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs

Cites Work

• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• A group-theoretic model for symmetric interconnection networks
• Reoptimizing the traveling salesman problem
• A note on some variations of the $\gamma$-graph
• A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
• Using contracted solution graphs for solving reconfiguration problems.
• Sliding Tokens on a Cactus
• Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes.
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Recursive Unsolvability of a problem of Thue
• THE k-INDEPENDENT GRAPH OF A GRAPH
• Graph homomorphism reconfiguration and frozen H‐colorings
• Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
• Recognizing Graphs Close to Bipartite Graphs
• Reconfiguring k-colourings of Complete Bipartite Graphs
• Parameterized Complexity of Graph Constraint Logic
• The complexity of satisfiability problems
• On the Parameterized Complexity for Token Jumping on Graphs
• How to Morph Planar Graph Drawings
• Reconfigurations in Graphs and Grids
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Reconfiguring spanning and induced subgraphs
• Kempe equivalence of colourings of cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classifying coloring graphs
• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• Reconfiguration of dominating sets
• Colored pebble motion on graphs
• Local search: is brute-force avoidable?
• Complexity of independent set reconfigurability problems
• Approximability of the subset sum reconfiguration problem
• Linear-time algorithm for sliding tokens on trees
• The complexity of dominating set reconfiguration
• Incremental problems in the parameterized complexity setting
• On the parameterized complexity of reconfiguration problems
• The gamma graph of a graph
• On the Boolean connectivity problem for Horn relations
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• A note on \(\gamma\)-graphs
• A survey of very large-scale neighborhood search techniques
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Perfectly contractile graphs
• Fast recoloring of sparse graphs
• Flip distance between two triangulations of a point set is NP-complete
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Kempe classes and the Hadwiger conjecture
• Geometric coloring theory
• Les 5-colorations d'un graphe planaire forment une classe de commutation unique
• A linear-time algorithm for the feasibility of pebble motion on trees
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• Straightening polygonal arcs and convexifying polygonal cycles
• The traveling salesman problem and its variations
• Reconfiguration on nowhere dense graph classes
• Reconfiguration graphs of shortest paths
• Token jumping in minor-closed classes
• Reconfiguration in bounded bandwidth and tree-depth
• Token sliding on chordal graphs
• Fixing improper colorings of graphs
• Graph editing to a given neighbourhood degree list is fixed-parameter tractable
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
• Reconfiguration on sparse graphs
• Graph puzzles, homotopy, and the alternating group
• Token graphs
• Multi-color pebble motion on graphs
• The \(k\)-dominating graph
• Which graphs occur as \(\gamma\)-graphs?
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Swapping labeled tokens on graphs
• Gamma graphs of some special classes of trees
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• On the structure of dominating graphs
• Reconfiguration of maximum weight \(b\)-matchings in a graph
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Flip distance between triangulations of a planar point set is APX-hard
• Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
• Connectedness of the graph of vertex-colourings
• Pushing squares around
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The Complexity of Induced Tree Reconfiguration Problems
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Reconfiguration of Steiner Trees in an Unweighted Graph
• Independent Set Reconfiguration in Cographs and their Generalizations
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• INDUCED SUBGRAPHS OF GAMMA GRAPHS
• The complexity of change
• Kempe Equivalence of Edge-Colorings in Subcubic and Subquartic Graphs
• The canonical coloring graph of trees and cycles
• A Theory and Algorithms for Combinatorial Reoptimization
• The Complexity of Rerouting Shortest Paths
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Vertex Cover Reconfiguration and Beyond
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding Shortest Paths Between Graph Colourings
• Reconfiguration over Tree Decompositions
• Reconfiguration of Vertex Covers in a Graph
• Degree-Constrained Subgraph Reconfiguration is in P
• Reconfiguration of Cliques in a Graph
• Flip Distance Is in FPT Time O(n+ k * c^k)
• Homomorphism reconfiguration via homotopy
• The Complexity of (List) Edge-Coloring Reconfiguration Problem
• Sequentially Swapping Colored Tokens on Graphs
• The Time Complexity of the Token Swapping Problem and Its Parallel Variants
• Sliding Tokens on Block Graphs
• Finding paths between 3-colorings
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• γ-graphs of graphs
• Gray code numbers for graphs
• Reconfiguring Independent Sets in Claw-Free Graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Ground State Connectivity of Local Hamiltonians
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Swapping Colored Tokens on Graphs
• Sliding Token on Bipartite Permutation Graphs
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings