Abstract
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in S) such that the result is again an independent set. We also consider the more restricted model where v and w have to be adjacent.
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
Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics 44, 257–262 (2013)
Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27(1), 132–143 (2014)
Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50), 5215–5226 (2009)
Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Math. 308(5-6), 913–919 (2008)
Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. European J. of Combinatorics 30(7), 1593–1606 (2009)
Ito, T., Kawamura, K., Ono, H., Zhou, X.: Reconfiguration of list L(2, 1)-labelings in a graph. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 34–43. Springer, Heidelberg (2012)
Ito, T., Kamiński, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 375–386. Springer, Heidelberg (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. Theoret. Comput. Sci. 412(12-14), 1054–1065 (2011)
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)
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)
Kamiński, M., Medvedev, P., Milanič, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9–15 (2012)
Bonsma, P.: Rerouting shortest paths in planar graphs. In: D’Souza, D., Kavitha, T., Radhakrishnan, J. (eds.) FSTTCS. LIPIcs, vol. 18, pp. 337–349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
Bonsma, P.: The complexity of rerouting shortest paths. Theor. Comput. Sci. 510, 1–12 (2013)
Kamiński, M., Medvedev, P., Milanič, M.: Shortest paths between shortest paths. Theor. Comput. Sci. 412(39), 5205–5210 (2011)
Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets. CoRR abs/1401.5714 (2014)
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)
van den Heuvel, J.: The complexity of change. Surveys in Combinatorics, 127–160 (2013)
Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. In: Webb, B.S. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 327, pp. 153–171. Cambridge University Press (2005)
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B 28(3), 284–304 (1980)
Sbihi, N.: Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Discrete Mathematics 29(1), 53–76 (1980)
Nakamura, D., Tamura, A.: A revision of Minty’s algorithm for finding a maximum weight stable set of a claw-free graph. Journal of the Operations Research Society of Japan 44(2), 194–204 (2001)
Schrijver, A.: Combinatorial optimization: Polyhedra and efficiency, vol. 24. Springer (2003)
Nobili, P., Sassano, A.: A reduction algorithm for the weighted stable set problem in claw-free graphs. Discrete Applied Mathematics (2013)
Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an O(n 3)-algorithm for the weighted stable set problem. In: SODA, pp. 630–646. SIAM (2011)
Bonsma, P., Kamiński, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. CoRR abs/1403.0359 (2014)
Diestel, R.: Graph Theory. Electronic Edition. Springer-Verlag (2005)
Bonsma, P.: Independent set reconfiguration in cographs. CoRR abs/1402.1587 (2014); Extended abstract accepted for WG 2014
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bonsma, P., Kamiński, M., Wrochna, M. (2014). Reconfiguring Independent Sets in Claw-Free Graphs. In: Ravi, R., Gørtz, I.L. (eds) Algorithm Theory – SWAT 2014. SWAT 2014. Lecture Notes in Computer Science, vol 8503. Springer, Cham. https://doi.org/10.1007/978-3-319-08404-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-08404-6_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08403-9
Online ISBN: 978-3-319-08404-6
eBook Packages: Computer ScienceComputer Science (R0)