Document Open Access Logo

Gap Preserving Reductions Between Reconfiguration Problems

Author Naoto Ohsaka

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.49.pdf
  • Filesize: 1.02 MB
  • 18 pages

Document Identifiers

Author Details

Naoto Ohsaka
  • CyberAgent, Inc., Tokyo, Japan

Acknowledgements

I wish to thank the anonymous referees for their suggestions which help improve the presentation of this paper.

Cite AsGet BibTex

Naoto Ohsaka. Gap Preserving Reductions Between Reconfiguration Problems. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.49

Abstract

Combinatorial reconfiguration is a growing research field studying problems on the transformability between a pair of solutions for a search problem. For example, in SAT Reconfiguration, for a Boolean formula φ and two satisfying truth assignments σ_𝗌 and σ_𝗍 for φ, we are asked to determine whether there is a sequence of satisfying truth assignments for φ starting from σ_𝗌 and ending with σ_𝗍, each resulting from the previous one by flipping a single variable assignment. We consider the approximability of optimization variants of reconfiguration problems; e.g., Maxmin SAT Reconfiguration requires to maximize the minimum fraction of satisfied clauses of φ during transformation from σ_𝗌 to σ_𝗍. Solving such optimization variants approximately, we may be able to obtain a reasonable reconfiguration sequence comprising almost-satisfying truth assignments. In this study, we prove a series of gap-preserving reductions to give evidence that a host of reconfiguration problems are PSPACE-hard to approximate, under some plausible assumption. Our starting point is a new working hypothesis called the Reconfiguration Inapproximability Hypothesis (RIH), which asserts that a gap version of Maxmin CSP Reconfiguration is PSPACE-hard. This hypothesis may be thought of as a reconfiguration analogue of the PCP theorem. Our main result is PSPACE-hardness of approximating Maxmin 3-SAT Reconfiguration of bounded occurrence under RIH. The crux of its proof is a gap-preserving reduction from Maxmin Binary CSP Reconfiguration to itself of bounded degree. Because a simple application of the degree reduction technique using expander graphs due to Papadimitriou and Yannakakis (J. Comput. Syst. Sci., 1991) does not preserve the perfect completeness, we modify the alphabet as if each vertex could take a pair of values simultaneously. To accomplish the soundness requirement, we further apply an explicit family of near-Ramanujan graphs and the expander mixing lemma. As an application of the main result, we demonstrate that under RIH, optimization variants of popular reconfiguration problems are PSPACE-hard to approximate, including Nondeterministic Constraint Logic due to Hearn and Demaine (Theor. Comput. Sci., 2005), Independent Set Reconfiguration, Clique Reconfiguration, and Vertex Cover Reconfiguration.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • combinatorial reconfiguration
  • hardness of approximation
  • gap reduction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon. Explicit expanders of every degree and size. Comb., 41(4):447-463, 2021. Google Scholar
  2. Noga Alon and Fan R. K. Chung. Explicit construction of linear sized tolerant networks. Discret. Math., 72(1-3):15-19, 1988. Google Scholar
  3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. Google Scholar
  4. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. Google Scholar
  5. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token sliding on split graphs. Theory Comput. Syst., 65(4):662-686, 2021. Google Scholar
  6. Alexandre Blanché, Haruka Mizuta, Paul Ouvrard, and Akira Suzuki. Decremental optimization of dominating sets under the reconfiguration framework. In IWOCA, pages 69-82, 2020. Google Scholar
  7. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Shortest reconfiguration of colorings under Kempe changes. In STACS, pages 35:1-35:14, 2020. Google Scholar
  8. Édouard Bonnet, Tillmann Miltzow, and Paweł Rzążewski. Complexity of token swapping and its variants. Algorithmica, 80(9):2656-2682, 2018. Google Scholar
  9. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci., 410(50):5215-5226, 2009. Google Scholar
  10. Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest reconfiguration of matchings. In WG, pages 162-174, 2019. Google Scholar
  11. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of spanning trees with degree constraint or diameter constraint. In STACS, pages 15:1-15:21, 2022. Google Scholar
  12. Nicolas Bousquet and Alice Joffard. Approximating shortest connected graph transformation for trees. In SOFSEM, pages 76-87, 2020. Google Scholar
  13. Nicolas Bousquet and Arnaud Mary. Reconfiguration of graphs with connectivity constraints. In WAOA, pages 295-309, 2018. Google Scholar
  14. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. J. Graph Theory, 67(1):69-82, 2011. Google Scholar
  15. Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor. Probabilistically checkable debate systems and nonapproximability of PSPACE-hard functions. Chic. J. Theor. Comput. Sci., 1995, 1995. Google Scholar
  16. Pierluigi Crescenzi. A short guide to approximation preserving reductions. In CCC, pages 262-273, 1997. Google Scholar
  17. Pierluigi Crescenzi and Luca Trevisan. On approximation scheme preserving reducibility and its applications. Theory Comput. Syst., 33(1):1-16, 2000. Google Scholar
  18. Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. Independent-set reconfiguration thresholds of hereditary graph classes. Discret. Appl. Math., 250:165-182, 2018. Google Scholar
  19. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Google Scholar
  20. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 2012. Google Scholar
  21. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  22. Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar, and Abhiruk Lahiri. Reconfiguring shortest paths in graphs. In AAAI, pages 9758-9766, 2022. Google Scholar
  23. Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: Computational and structural dichotomies. SIAM J. Comput., 38(6):2330-2355, 2009. Google Scholar
  24. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci., 343(1-2):72-96, 2005. Google Scholar
  25. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters, Ltd., 2009. Google Scholar
  26. Lenwood S. Heath and John Paul C. Vergara. Sorting by short swaps. J. Comput. Biol., 10(5):775-789, 2003. Google Scholar
  27. Takehiro Ito and Erik D. Demaine. Approximability of the subset sum reconfiguration problem. J. Comb. Optim., 28(3):639-654, 2014. Google Scholar
  28. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054-1065, 2011. Google Scholar
  29. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest reconfiguration of perfect matchings via alternating cycles. SIAM J. Discret. Math., 36(2):1102-1123, 2022. Google Scholar
  30. Takehiro Ito, Marcin Kamiński, and Erik D. Demaine. Reconfiguration of list edge-colorings in a graph. Discret. Appl. Math., 160(15):2199-2207, 2012. Google Scholar
  31. Takehiro Ito, Haruka Mizuta, Naomi Nishimura, and Akira Suzuki. Incremental optimization of independent sets under the reconfiguration framework. J. Comb. Optim., 43(5):1264-1279, 2022. Google Scholar
  32. Takehiro Ito, Hiroyuki Nooka, and Xiao Zhou. Reconfiguration of vertex covers in a graph. IEICE Trans. Inf. Syst., 99-D(3):598-606, 2016. Google Scholar
  33. Matti Järvisalo and Ilkka Niemelä. A compact reformulation of propositional satisfiability as binary constraint satisfaction. In Third International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, pages 111-124, 2004. Google Scholar
  34. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9-15, 2012. Google Scholar
  35. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In ESA, pages 66:1-66:15, 2016. Google Scholar
  36. Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. Explicit near-Ramanujan graphs of every degree. SIAM J. Comput., 51(3):STOC20-1-STOC20-23, 2021. Google Scholar
  37. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. Google Scholar
  38. Naoto Ohsaka. Gap preserving reductions between reconfiguration problems. CoRR, abs/2212.04207, 2022. Google Scholar
  39. Naoto Ohsaka and Tatsuya Matsuoka. Reconfiguration problems on submodular functions. In WSDM, pages 764-774, 2022. Google Scholar
  40. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. Google Scholar
  41. Jan van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, volume 409, pages 127-160. Cambridge University Press, 2013. Google Scholar
  42. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theor. Comput. Sci., 586:81-94, 2015. Google Scholar
  43. Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, and Xiao Zhou. Decremental optimization of vertex-coloring under the reconfiguration framework. In COCOON, pages 355-366, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact