×

Independent set reconfiguration in cographs and their generalizations. (English) Zbl 1346.05209

Summary: We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets \(I\) and \(J\) of a graph \(G\), both of size at least \(k\), is it possible to transform \(I\) into \(J\) by adding and removing vertices one-by-one, while maintaining an independent set of size at least \(k\) throughout? This problem is known to be PSPACE-hard in general. For the case that \(G\) is a cograph on \(n\) vertices, we show that it can be solved in time \(O(n^2)\), and that the length of a shortest reconfiguration sequence from \(I\) to \(J\) is bounded by \(4n-2k\) (if it exists). More generally, we show that if \(\mathcal G\) is a graph class for which (i) TAR-Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in \(\mathcal G\) using disjoint union and complete join operations. Chordal graphs and claw-free graphs are given as examples of such a class \(\mathcal G\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C39 Dynamic programming
Full Text: DOI

References:

[1] M.Bonamy and N.Bousquet, Recoloring bounded treewidth graphs, Electron Notes Discrete Math44 (2013), 257-262.
[2] M.Bonamy and N.Bousquet. Reconfiguring independent sets in cographs. arXiv:1406.1433, June 2014.
[3] M.Bonamy, M.Johnson, I.Lignos, V.Patel, and D.Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J Combin Optim72 (2014), 132-143. · Zbl 1284.05089
[4] P.Bonsma, Rerouting shortest paths in planar graphs, in: D.D’Souza (ed.), J.Radhakrishnan (ed.), and K.Telikepalli (ed.) (Eds.), 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), vol. 18 of LIPIcs. Schloss Dagstuhl, Leibniz‐Zentrum fuer Informatik, Hyderabad, India 2012, pp. 337-349. · Zbl 1354.68110
[5] P.Bonsma, The complexity of rerouting shortest paths, Theor Comput Sci510 (2013), 1-12. · Zbl 1416.68082
[6] P.Bonsma, Independent set reconfiguration in cographs, arXiv:1402.1587, February 2014.
[7] P.Bonsma and L.Cereceda, Finding paths between graph colourings: PSPACE‐completeness and superpolynomial distances, Theor Comput Sci410(50) (2009), 5215-5226. · Zbl 1177.05112
[8] P.Bonsma, M.Kamiński, and M.Wrochna, Reconfiguring independent sets in claw‐free graphs, in: R.Ravi (ed.) and I. L.Gørtz (ed.) (Eds.), Algorithm Theory—SWAT 2014, in: Lecture Notes in Computer Science, vol. 8503, Springer, International Publishing Switzerland, Switzerland 2014, pp. 86-97. · Zbl 1417.05199
[9] P.Bonsma, A. E.Mouawad, N.Nishimura, and V.Raman, The complexity of bounded length graph recoloring and CSP reconfiguration, in: M.Cygan (ed.) and P.Heggernes (ed.) (Eds.), Parameterized and Exact Computation (IPEC 2014), in: Lecture Notes in Computer Science, vol. 8894, Springer, International Publishing Switzerland, Switzerland 2014, pp. 110-121. · Zbl 1456.68065
[10] L.Cereceda, J.van denHeuvel, and M.Johnson, Connectedness of the graph of vertex‐colourings. Discrete Appl Math308(5-6) (2008), 913-919. · Zbl 1133.05053
[11] L.Cereceda, J.van denHeuvel, and M.Johnson, Mixing 3‐colourings in bipartite graphs, Eur J Combin30(7) (2009), 1593-1606. · Zbl 1198.05040
[12] L.Cereceda, J.van denHeuvel, and M.Johnson, Finding paths between 3‐colorings, J Graph Theory67(1) (2011), 69-82. · Zbl 1216.05154
[13] D.Corneil, Y.Perl, and L.Stewart, A linear recognition algorithm for cographs, SIAM J Comput14(4) (1985), 926-934. · Zbl 0575.68065
[14] B.Courcelle and S.Olariu, Upper bounds to the clique width of graphs, Discrete Appl Math101(1-3) (2000), 77-114. · Zbl 0958.05105
[15] C.Eggermont and G. J.Woeginger, Motion planning with pulley, rope, and baskets, Theor Comput Syst53(4) (2013), 569-582. · Zbl 1277.68094
[16] F.Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J Comput1(2) (1972), 180-187. · Zbl 0227.05116
[17] P.Gopalan, P. G.Kolaitis, E.Maneva, and C. H.Papadimitriou, The connectivity of boolean satisfiability: Computational and structural dichotomies, SIAM J Comput38(6) (2009), 2330-2355. · Zbl 1201.03024
[18] R. A.Hearn and E. D.Demaine, PSPACE‐completeness of sliding‐block puzzles and other problems through the nondeterministic constraint logic model of computation, Theor Comput Sci343(1-2) (2005), 72-96. · Zbl 1079.68040
[19] T.Ito and E. D.Demaine, Approximability of the subset sum reconfiguration problem, J Combin Optim28(3) (2014), 639-654. · Zbl 1315.90036
[20] 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, Theor Comput Sci412(12-14) (2011), 1054-1065. · Zbl 1207.68166
[21] M.Johnson, D.Kratsch, S.Kratsch, V.Patel, and D.Paulusma, Finding shortest paths between graph colourings, in: M.Cygan (ed.) and P.Heggernes (ed.) (Eds.), Parameterized and Exact Computation (IPEC 2014), in: Lecture Notes in Computer Science, vol. 8894, Springer, International Publishing Switzerland, Switzerland2014, pp. 221-233. · Zbl 1341.68062
[22] M.Kamiński, P.Medvedev, and M.Milanič, Shortest paths between shortest paths, Theor Comput Sci412(39) (2011), 5205-5210. · Zbl 1225.68136
[23] M.Kamiński, P.Medvedev, and M.Milanič, Complexity of independent set reconfigurability problems, Theor Comput Sci439 (2012), 9-15. · Zbl 1246.05121
[24] G. J.Minty, On maximal independent sets of vertices in claw‐free graphs, J Combin Theory Ser B28(3) (1980), 284-304. · Zbl 0434.05043
[25] A. E.Mouawad, N.Nishimura, V.Raman, N.Simjour, and A.Suzuki, On the parameterized complexity of reconfiguration problems, in: G.Gutin (ed.) and S.Szeider (ed.) (Eds.), Parameterized and Exact Computation (IPEC 2013), in: Lecture Notes in Computer Science, vol. 8246, Springer International Publishing Switzerland, Switzerland2013, pp. 281-294. · Zbl 1350.68155
[26] N.Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math29(1) (1980), 53-76. · Zbl 0444.05049
[27] J.van denHeuvel, The complexity of change, In: Surveys in Combinatorics 2013, Cambridge University Press, Cambridge, U.K. 2013, pp. 127-160. · Zbl 1307.05005
[28] K.Vušković, Even‐hole‐free graphs: A survey, Appl Anal Discrete Math4(2) (2010), 219-240. · Zbl 1265.05518
[29] M.Wrochna, Reconfiguration in bounded bandwidth and treedepth, arXiv:1405.0847, May 2014.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.