Reconfiguration

Last updated

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

Contents

Types of problems

Here, a state space is a discrete set of configurations of a system or solutions of a combinatorial problem, called states, together with a set of allowed moves linking one state to another. Reconfiguration problems may ask:

Examples

Examples of problems studied in reconfiguration include:

Related Research Articles

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.
<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

<span class="mw-page-title-main">Matchstick graph</span> Graph with edges of length one, able to be drawn without crossings

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph and a plane graph. For this reason, matchstick graphs have also been called planar unit-distance graphs. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.

In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens.

<span class="mw-page-title-main">Flip graph</span> A graph that encodes local operations in mathematics

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. This is a form of reversible logic in that each sequence of edge orientation changes can be undone.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of convex polygons.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

  1. Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna; Winslow, Andrew (2011), "Algorithms for solving Rubik's cubes", Algorithms – ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings, Lecture Notes in Computer Science, vol. 6942, Springer, Heidelberg, pp. 689–700, arXiv: 1106.5736 , doi:10.1007/978-3-642-23719-5_58, ISBN   978-3-642-23718-8, MR   2893242, S2CID   664306
  2. Culberson, Joseph (1997), Sokoban is PSPACE-complete, Technical report TR97-02, University of Alberta, Department of Computing Science, doi:10.7939/R3JM23K33, hdl: 10048/27119
  3. Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics , 259: 13–42, arXiv: 1207.6296 , doi: 10.1016/j.aim.2014.02.035 , MR   3197650
  4. Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017), "Computing the flip distance between triangulations", Discrete & Computational Geometry , 58 (2): 313–344, arXiv: 1407.1525 , doi:10.1007/s00454-017-9867-x, MR   3679938, S2CID   254033552
  5. Lubiw, Anna; Pathak, Vinayak (2015), "Flip distance between two triangulations of a point set is NP-complete", Computational Geometry , 49: 17–23, arXiv: 1205.2425 , doi: 10.1016/j.comgeo.2014.11.001 , MR   3399985
  6. Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015), "Flip distance between triangulations of a simple polygon is NP-complete", Discrete & Computational Geometry , 54 (2): 368–389, arXiv: 1209.0579 , doi:10.1007/s00454-015-9709-7, MR   3372115, S2CID   254037222
  7. Cereceda, Luis (2007), Mixing graph colourings, doctoral dissertation, London School of Economics. See especially page 109.
  8. Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël (2016), "Finding shortest paths between graph colourings" (PDF), Algorithmica, 75 (2): 295–321, doi:10.1007/s00453-015-0009-7, MR   3506195, S2CID   253974066
  9. Bonsma, Paul; Cereceda, Luis (2009), "Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances", Theoretical Computer Science, 410 (50): 5215–5226, doi:10.1016/j.tcs.2009.08.023, MR   2573973
  10. van der Zanden, Tom C. (2015), "Parameterized complexity of graph constraint logic", 10th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz Int. Proc. Inform., vol. 43, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 282–293, arXiv: 1509.02683 , doi: 10.4230/LIPIcs.IPEC.2015.282 , MR   3452428, S2CID   15959029
  11. Hearn, Robert A.; Demaine, Erik D. (2005), "PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation", Theoretical Computer Science , 343 (1–2): 72–96, arXiv: cs/0205005 , doi:10.1016/j.tcs.2005.05.008, MR   2168845, S2CID   656067