Document Open Access Logo

Using Contracted Solution Graphs for Solving Reconfiguration Problems

Authors Paul Bonsma, Daniël Paulusma

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.20.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Paul Bonsma
Daniël Paulusma

Cite As Get BibTex

Paul Bonsma and Daniël Paulusma. Using Contracted Solution Graphs for Solving Reconfiguration Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.20

Abstract

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from  solution graphs by performing an appropriate series of edge contractions that decrease the graph size without losing any critical information needed to solve the reconfiguration problem under consideration. As an example, we consider a well-studied problem: given two k-colorings alpha and beta of a graph G, can alpha be modified into beta by recoloring one vertex of G at a time, while maintaining a k-coloring throughout? By applying our method in combination with a thorough exploitation of the graph structure we obtain a polynomial-time algorithm for (k-2)-connected chordal graphs.

Subject Classification

Keywords
  • reconfiguration
  • contraction
  • dynamic programming
  • graph coloring

Metrics

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

References

  1. H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  2. H.L. Bodlaender, P. Bonsma, and D. Lokshtanov. The fine details of fast dynamic programming over tree decompositions. In Proc. IPEC, volume 8246 of LNCS, pages 41-53. Springer, 2013. Google Scholar
  3. M. Bonamy and N. Bousquet. Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics, 44:257-262, 2013. Google Scholar
  4. M. Bonamy, M. Johnson, I.M. Lignos, V. Patel, and D. Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27:132-143, 2014. URL: http://dx.doi.org/10.1007/s10878-012-9490-y.
  5. P. Bonsma. Rerouting shortest paths in planar graphs. In Proc. FSTTCS 2012, volume 18 of LIPIcs, pages 337-349. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. Google Scholar
  6. P. Bonsma. The complexity of rerouting shortest paths. Theoretical Computer Science, 510:1 - 12, 2013. Google Scholar
  7. P. Bonsma. Independent set reconfiguration in cographs and their generalizations. Journal of Graph Theory, 2015. URL: http://dx.doi.org/10.1002/jgt.21992.
  8. P. Bonsma and L. Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.08.023.
  9. P. Bonsma, M. Kamiński, and M. Wrochna. Reconfiguring independent sets in claw-free graphs. In Proc. SWAT 2014, volume 8503 of LNCS, pages 86-97. Springer, 2014. Google Scholar
  10. P. Bonsma, A.E. Mouawad, N. Nishimura, and V. Raman. The complexity of bounded length graph recoloring and CSP reconfiguration. In Proc. IPEC 2014, volume 8894 of LNCS, pages 110-121. Springer, 2014. Google Scholar
  11. L. Cereceda, J. van den Heuvel, and M. Johnson. Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5):913-919, 2008. Google Scholar
  12. L. Cereceda, J. van den Heuvel, and M. Johnson. Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7):1593-1606, 2009. Google Scholar
  13. L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between 3-colorings. Journal of Graph Theory, 67(1):69-82, 2011. Google Scholar
  14. R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fourth edition, 2010. Google Scholar
  15. C. Feghali, M. Johnson, and D. Paulusma. A reconfigurations analogue of Brooks’ theorem. In Proc. MFCS 2014, volume 8635 of LNCS, pages 287-298. Springer, 2014. Google Scholar
  16. P. Gopalan, P.G. Kolaitis, E. Maneva, and C.H. Papadimitriou. The connectivity of boolean satisfiability: Computational and structural dichotomies. SIAM Journal on Computing, 38(6), 2009. Google Scholar
  17. A. Haddadan, T. Ito, A.E. Mouawad, N. Nishimura, H. Ono, A. Suzuki, and Y. Tebbal. The complexity of dominating set reconfiguration. In Proc. WADS 2015, volume 9214 of LNCS, pages 398-409. Springer, 2015. Google Scholar
  18. T. Hatanaka, T. Ito, and X. Zhou. The list coloring reconfiguration problem for bounded pathwidth graphs. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 98(6):1168-1178, 2015. Google Scholar
  19. J. van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, pages 127-160. Cambridge University Press, 2013. Google Scholar
  20. T. Ito and E.D. Demaine. Approximability of the subset sum reconfiguration problem. In TAMC 2011, volume 6648 of LNCS, pages 58-69. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20877-5_7.
  21. T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14):1054-1065, 2011. Google Scholar
  22. T. Ito, M. Kamiński, and E.D. Demaine. Reconfiguration of list edge-colorings in a graph. Discrete Applied Mathematics, 160(15):2199-2207, 2012. Google Scholar
  23. T. Ito, K. Kawamura, and X. Zhou. An improved sufficient condition for reconfiguration of list edge-colorings in a tree. IEICE TRANSACTIONS on Information and Systems, 95(3):737-745, 2012. Google Scholar
  24. Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, and Xiao Zhou. Reconfiguration of list L (2, 1)-labelings in a graph. Theoretical Computer Science, 544:84-97, 2014. Google Scholar
  25. M. Johnson, D. Kratsch, S. Kratsch, V. Patel, and D. Paulusma. Finding shortest paths between graph colourings. Algorithmica, 75(2):295-321, 2016. URL: http://dro.dur.ac.uk/15595/.
  26. M. Kamiński, P. Medvedev, and M. Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. Google Scholar
  27. T. Kloks. Treewidth: computations and approximations, volume 842 of LNCS. Springer, 1994. Google Scholar
  28. D. Lokshtanov, A.E. Mouawad, F. Panolan, M.S. Ramanujan, and S. Saurabh. Reconfiguration on sparse graphs. In Proc. WADS 2015, volume 9214 of LNCS, pages 506-517. Springer, 2015. Google Scholar
  29. A. E. Mouawad, N. Nishimura, V. Raman, and M. Wrochna. Reconfiguration over tree decompositions. In Proc. IPEC 2014, volume 8894 of LNCS, pages 246-257. Springer, 2014. Google Scholar
  30. A.E. Mouawad, N. Nishimura, and V. Raman. Vertex cover reconfiguration and beyond. In Proc. ISAAC 2014, volume 8889 of LNCS, pages 452-463. Springer, 2014. Google Scholar
  31. A.E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki. On the parameterized complexity of reconfiguration problems. In Proc. IPEC 2013, volume 8246 of LNCS, pages 281-294. Springer, 2013. Google Scholar
  32. A.E. Mouawad, N. Nishimura, Pathak V., and V. Raman. Shortest reconfiguration paths in the solution space of boolean formulas. In Proc. ICALP 2015, volume 9134 of LNCS, pages 985-996. Springer, 2015. Google Scholar
  33. R. Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  34. M. Wrochna. Reconfiguration in bounded bandwidth and treedepth. arXiv:1405.0847, 2014. URL: http://arxiv.org/abs/1405.0847.
  35. M. Wrochna. Homomorphism reconfiguration via homotopy. In Proc. STACS 2015, volume 30 of LIPIcs, pages 730-742. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  36. T.C. van der Zanden. Parameterized complexity of graph constraint logic. In Proc. IPEC 2015, volume 43 of LIPIcs, pages 282-293. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. 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 About DROPS Imprint Privacy Contact