[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the Parameterized Complexity of Reconfiguration Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem \(\mathcal {Q}\) takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to \(\mathcal {Q}\). For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: k, a bound on the size of solutions, and \(\ell \), a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set, all parameterized by k. In contrast, we show that reconfiguring Unbounded Hitting Set is W[2]-hard when parameterized by \(k+\ell \). We also demonstrate the W[1]-hardness of reconfiguration variants of a large class of maximization problems parameterized by \(k+\ell \), and of their corresponding deletion problems parameterized by \(\ell \); in doing so, we show that there exist problems in FPT when parameterized by k, but whose reconfiguration variants are W[1]-hard when parameterized by \(k+\ell \).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Bang-Jensen, J., Gutin, G.: Digraphs: theory, algorithms and applications. In: Springer Monographs in Mathematics. Springer-Verlag, London (2008)

  2. Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Proceedings of the 24th Annual Conference on Theoretical Aspects of Computer Science, pp. 320–331 (2007)

  3. Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electron. Notes Discrete Math. 44, 257–262 (2013)

    Article  Google Scholar 

  4. Bonsma, P.: The complexity of rerouting shortest paths. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, pp. 222–233 (2012)

  5. Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50), 5215–5226 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bonsma, P., Mouawad, A.E., Nishimura, N., Raman, V.: The complexity of bounded length graph recoloring and CSP reconfiguration. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 110–121 (2014)

  7. Cereceda, L.: Mixing graph colourings. Ph.D. thesis, London School of Economics (2007)

  8. Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. Eur. J. Comb. 30(7), 1593–1606 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colorings. J. Graph Theory 67(1), 69–82 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). doi:10.1007/978-3-319-21275-3

    Book  MATH  Google Scholar 

  11. Damaschke, P., Molokov, L.: The union of minimal hitting sets: parameterized combinatorial bounds and counting. J. Discrete Algorithms 7(4), 391–401 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Diestel, R.: Graph Theory. Springer, Berlin (2005). (Electronic Edition)

    MATH  Google Scholar 

  13. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1997)

    MATH  Google Scholar 

  14. Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707–719 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

    MATH  Google Scholar 

  16. Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38(6), 2330–2355 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  18. Haas, R., Seyffarth, K.: The \(k\)-dominating graph. Graphs Comb. 30(3), 609–617 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  19. Haddadan, A., Ito, T., Mouawad, A.E., Nishimura, N., Ono, H., Suzuki, A., Tebbal, Y.: The complexity of dominating set reconfiguration. In: Proceedings of the 14th Algorithms and Data Structures Symposium (to appear) (2015)

  20. Hearn, R.A., Demaine, E.D.: 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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Impagliazzo, R., Paturi, R.: The complexity of k-SAT. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pp. 237–240 (1999)

  22. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  23. Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12–14), 1054–1065 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ito, T., Kamiński, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discrete Appl. Math. 160(15), 2199–2207 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  25. Ito, T., Kamiński, M., Ono, H.: Fixed-parameter tractability of token jumping on planar graphs. In: Algorithms and Computation, Lecture Notes in Computer Science, Springer International Publishing, pp. 208–219 (2014)

  26. Ito, T., Kamiński, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 8402, pp. 341–351. Springer International Publishing (2014)

  27. Johnson, M., Kratsch, D., Kratsch, S., Patel, V., Paulusma, D.: Finding shortest paths between graph colourings. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 221–233 (2014)

  28. Kamiński, M., Medvedev, P., Milanič, M.: Shortest paths between shortest paths. Theor. Comput. Sci. 412(39), 5205–5210 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  29. Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997–1008 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  30. Kratsch, S., Pilipczuk, M., Rai, A., Raman, V.: Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Trans. Comput. Theory 7(1), 4:1–4:18 (2014)

    MathSciNet  MATH  Google Scholar 

  31. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M., Saurabh, S.: Reconfiguration on sparse graphs. In: Proceedings of the Algorithms and Data Structures Symposium (to appear) (2015)

  33. Misra, N., Narayanaswamy, N., Raman, V., Shankar, B.S.: Solving min ones 2-SAT as fast as vertex cover. Theor. Comput. Sci. 506, 115–121 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  34. Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V.: Shortest reconfiguration paths in the solution space of Boolean formulas. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, vol. 9134, pp. 985–996 (2015)

  35. Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. In: Proceedings of the 25th International Symposium on Algorithms and Computation, pp. 452–463 (2014)

  36. Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 246–257 (2014)

  37. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

  38. Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446–458 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  39. Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets. In: Proceedings of the 20th International Computing and Combinatorics Conference, pp. 405–416 (2014)

  40. Thomassé, S.: A \(4k^2\) kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1–32:8 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  41. van den Heuvel, J.: The complexity of change. Surv. Comb. 409, 127–160 (2013)

    MathSciNet  MATH  Google Scholar 

  42. Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth. CoRR (2014). ArXiv:1405.0847

Download references

Acknowledgments

The second author wishes to thank Marcin Kamiński for suggesting the examination of reconfiguration in the parameterized setting.

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, Bergen, Norway

    Amer E. Mouawad

  2. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada

    Naomi Nishimura

  3. The Institute of Mathematical Sciences, Chennai, India

    Venkatesh Raman

  4. Google Waterloo, 151 Charles Street West, Suite 200, Kitchener, ON, N2G 1H6, Canada

    Narges Simjour

  5. Graduate School of Information Sciences, Tohoku University, Sendai, Japan

    Akira Suzuki

  6. CREST, JST, Saitama, Japan

    Akira Suzuki

Authors
  1. Amer E. Mouawad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Naomi Nishimura
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Venkatesh Raman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Narges Simjour
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Akira Suzuki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amer E. Mouawad.

Additional information

A preliminary version of this paper appeared in the Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013).

Research of the first, second, and fourth authors is supported by the Natural Science and Engineering Research Council of Canada. Research of the fifth author is supported by JSPS Grant-in-Aid for Scientific Research, Grant Number 26730001.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mouawad, A.E., Nishimura, N., Raman, V. et al. On the Parameterized Complexity of Reconfiguration Problems. Algorithmica 78, 274–297 (2017). https://doi.org/10.1007/s00453-016-0159-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0159-2

Keywords

Search

Navigation