Abstract
Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment \(s\) to another satisfying assignment \(t\) of the Boolean formula. Earlier work characterized the complexity of deciding the existence of a sequence of flips between two given satisfying assignments using Schaefer’s framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the small set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though the path flips variables that have the same value in both \(s\) and \(t\). This is in contrast to all reconfiguration problems studied so far, where polynomial time algorithms for computing the shortest path were known only for cases where the path modified the symmetric difference only. Our proof uses Birkhoff’s representation theorem on a set system that we show to be a distributive lattice. The technique is insightful and can perhaps be used for other reconfiguration problems as well.
A.E. Mouawad and N. Nishimura—Research supported by the Natural Science and Engineering Research Council of Canada.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 13–24. Springer, Heidelberg (2013)
Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York, NY, USA (2009)
Birkhoff, G.: Rings of sets. Duke Mathematical Journal 3(3), 443–454 (1937)
Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. In: Proceedings of the 7th Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS) (2013)
Bose, P., Lubiw, A., Pathak, V., Verdonschot, S.: Flipping edge-labelled triangulations (2013). CoRR, abs/1310.1166
Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Mathematics 308(56), 913–919 (2008)
Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of boolean constraint satisfaction problems. SIAM (2001)
Culik II, K., Wood, D.: A note on some tree similarity measures. Inform. Process. Lett. 15(1), 39–42 (1982)
Eppstein, D., Falmagne, J.-C., Ovchinnikov, S.: Media theory - interdisciplinary applied mathematics. Springer (2008)
Fricke, G., Hedetniemi, S.M., Hedetniemi, S.T., Hutson, K.R.: \(\gamma \)-Graphs of Graphs. Discussiones Mathematicae Graph Theory 31(3), 517–531 (2011)
Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM Journal on Computing 38(6), 2330–2355 (2009)
Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theoretical Computer Science 412(12–14), 1054–1065 (2011)
Ito, T., Kamiński, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discrete Applied Mathematics 160(15), 2199–2207 (2012)
Kamiński, M., Medvedev, P., Milanič, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9–15 (2012)
Lawson, C.L.: Transforming triangulations. Discrete Mathematics 3(4), 365–372 (1972)
A. E. Mouawad, N. Nishimura, and V. Raman. Vertex cover reconfiguration and beyond, 2014. arXiv:1402.4926
Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 281–294. Springer, Heidelberg (2013)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226. New York, NY, ACM (1978)
Schwerdtfeger, K.W.: A computational trichotomy for connectivity of boolean satisfiability (2013). CoRR, abs/1312.4524
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V. (2015). Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_80
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_80
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)