The complexity of dominating set reconfiguration. (English) Zbl 1359.68133
Summary: Suppose that we are given two dominating sets \(D_s\) and \(D_t\) of a graph \(G\) whose cardinalities are at most a given threshold \(k\). Then, we are asked whether there exists a sequence of dominating sets of \(G\) between \(D_s\) and \(D_t\) such that each dominating set in the sequence is of cardinality at most \(k\) and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by \(O(n)\), where \(n\) is the number of vertices in the input graph.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Bertossi, A. A., Dominating sets for split and bipartite graphs, Inform. Process. Lett., 19, 37-40 (1984) · Zbl 0539.68058 |
| [2] | Bonamy, M.; Johnson, M.; Lignos, I.; Patel, V.; Paulusma, D., Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J. Comb. Optim., 27, 132-143 (2014) · Zbl 1284.05089 |
| [3] | Bonsma, P., Independent set reconfiguration in cographs, (Proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science. Proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014. Proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science. Proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, Lecture Notes in Computer Science, vol. 8747 (2014)), 105-116 · Zbl 1417.05149 |
| [4] | Bonsma, P.; Cereceda, L., Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret. Comput. Sci., 410, 5215-5226 (2009) · Zbl 1177.05112 |
| [5] | Bonsma, P.; Kamiński, M.; Wrochna, M., Reconfiguring independent sets in claw-free graphs, (Proc. of the 14th Scandinavian Symposium and Workshops on Algorithm Theory. Proc. of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014. Proc. of the 14th Scandinavian Symposium and Workshops on Algorithm Theory. Proc. of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, Lecture Notes in Computer Science, vol. 8503 (2014)), 86-97 · Zbl 1417.05199 |
| [6] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes: A Survey (1999), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 0919.05001 |
| [7] | Cereceda, L.; van den Heuvel, J.; Johnson, M., Finding paths between 3-colourings, J. Graph Theory, 67, 69-82 (2011) · Zbl 1216.05154 |
| [8] | Demaine, E. D.; Demaine, M. L.; Fox-Epstein, E.; Hoang, D. A.; Ito, T.; Ono, H.; Otachi, Y.; Uehara, R.; Yamada, T., Linear-time algorithm for sliding tokens on trees, Theoret. Comput. Sci., 600, 132-142 (2015) · Zbl 1329.68135 |
| [9] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [10] | Gopalan, P.; Kolaitis, P. G.; Maneva, E. N.; Papadimitriou, C. H., The connectivity of Boolean satisfiability: computational and structural dichotomies, SIAM J. Comput., 38, 2330-2355 (2009) · Zbl 1201.03024 |
| [11] | Haas, R.; Seyffarth, K., The \(k\)-dominating graph, Graphs Combin., 30, 609-617 (2014) · Zbl 1294.05122 |
| [12] | Haddadan, A.; Ito, T.; Mouawad, A. E.; Nishimura, N.; Ono, H.; Suzuki, A.; Tebbal, Y., The complexity of dominating set reconfiguration, (Proc. of the 14th Algorithms and Data Structures Symposium. Proc. of the 14th Algorithms and Data Structures Symposium, WADS 2015. Proc. of the 14th Algorithms and Data Structures Symposium. Proc. of the 14th Algorithms and Data Structures Symposium, WADS 2015, Lecture Notes in Computer Science, vol. 9214 (2015)), 398-409 · Zbl 1451.68131 |
| [13] | Hatanaka, T.; Ito, T.; Zhou, X., The list coloring reconfiguration problem for bounded pathwidth graphs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E98-A, 1168-1178 (2015) |
| [14] | Hearn, R. A.; Demaine, E. D., PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, Theoret. Comput. Sci., 343, 72-96 (2005) · Zbl 1079.68040 |
| [15] | van den Heuvel, J., The complexity of change, (Surveys in Combinatorics 2013. Surveys in Combinatorics 2013, London Mathematical Society Lecture Notes Series, vol. 409 (2013)) · Zbl 1307.05005 |
| [16] | 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, 1054-1065 (2011) · Zbl 1207.68166 |
| [17] | Ito, T.; Nooka, H.; Zhou, X., Reconfiguration of vertex covers in a graph, IEICE Trans. Inf. Syst., E99-D, 598-606 (2016) |
| [18] | Ito, T.; Ono, H.; Otachi, Y., Reconfiguration of cliques in a graph, (Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation. Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015. Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation. Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015, Lecture Notes in Computer Science, vol. 9076 (2015)), 212-223 · Zbl 1462.05280 |
| [19] | Kamiński, M.; Medvedev, P.; Milanič, M., Complexity of independent set reconfigurability problems, Theoret. Comput. Sci., 439, 9-15 (2012) · Zbl 1246.05121 |
| [20] | Makino, K.; Tamaki, S.; Yamamoto, M., An exact algorithm for the Boolean connectivity problem for \(k\)-CNF, Theoret. Comput. Sci., 412, 4613-4618 (2011) · Zbl 1221.68104 |
| [21] | Mouawad, A. E.; Nishimura, N.; Pathak, V.; Raman, V., Shortest reconfiguration paths in the solution space of Boolean formulas, (Proc. of the 42nd International Colloquium on Automata, Languages, and Programming. Proc. of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015. Proc. of the 42nd International Colloquium on Automata, Languages, and Programming. Proc. of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Lecture Notes in Computer Science, vol. 9134 (2015)), 985-996 · Zbl 1374.68246 |
| [22] | Mouawad, A. E.; Nishimura, N.; Raman, V., Vertex cover reconfiguration and beyond, (Proc. of the 25th International Symposium on Algorithms and Computation. Proc. of the 25th International Symposium on Algorithms and Computation, ISAAC 2014. Proc. of the 25th International Symposium on Algorithms and Computation. Proc. of the 25th International Symposium on Algorithms and Computation, ISAAC 2014, Lecture Notes in Computer Science, vol. 8889 (2014)), 452-463 · Zbl 1432.68164 |
| [23] | Mouawad, A. E.; Nishimura, N.; Raman, V.; Simjour, N.; Suzuki, A., On the parameterized complexity of reconfiguration problems, (Proc. of the 8th International Symposium on Parameterized and Exact Computation. Proc. of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013. Proc. of the 8th International Symposium on Parameterized and Exact Computation. Proc. of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013, Lecture Notes in Computer Science, vol. 8246 (2013)), 281-294 · Zbl 1350.68155 |
| [24] | Suzuki, A.; Mouawad, A. E.; Nishimura, N., Reconfiguration of dominating sets, (Proc. of the 20th International Computing and Combinatorics Conference. Proc. of the 20th International Computing and Combinatorics Conference, COCOON 2014. Proc. of the 20th International Computing and Combinatorics Conference. Proc. of the 20th International Computing and Combinatorics Conference, COCOON 2014, Lecture Notes in Computer Science, vol. 8591 (2014)), 405-416 · Zbl 1425.05126 |
| [25] | Wrochna, M., Reconfiguration in bounded bandwidth and treedepth (2014) |
| [26] | van der Zanden, T. C., Parameterized complexity of graph constraint logic, (Proc. of the 10th International Symposium on Parameterized and Exact Computation. Proc. of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Proc. of the 10th International Symposium on Parameterized and Exact Computation. Proc. of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Leibniz International Proceedings in Informatics, vol. 43 (2015)), 282-293 · Zbl 1378.68097 |
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.
