Vertex cover reconfiguration and beyond. (English) Zbl 1432.68164
Ahn, Hee-Kap (ed.) et al., Algorithms and computation. 25th international symposium, ISAAC 2014, Jeonju, Korea, December 15–17, 2014. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 8889, 452-463 (2014).
Summary: In the Vertex Cover Reconfiguration (VCR) problem, given graph \(G = (V, E)\), positive integers \(k\) and \(\ell \), and two vertex covers \(S\) and \(T\) of \(G\) of size at most \(k\), we determine whether \(S\) can be transformed into \(T\) by a sequence of at most \(\ell \) vertex additions or removals such that each operation results in a vertex cover of size at most \(k\). Motivated by recent results establishing the \(\mathbf {W[1]}\)-hardness of VCR when parameterized by \(\ell \), we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains \(\mathbf {W[1]}\)-hard on bipartite graphs, is \(\mathbf {NP}\)-hard but fixed-parameter tractable on graphs of bounded degree, and is solvable in time polynomial in \(|V(G)|\) on even-hole-free graphs and cactus graphs. We prove \(\mathbf {W[1]}\)-hardness and fixed-parameter tractability via two new problems of independent interest.
For the entire collection see [Zbl 1318.68007].
For the entire collection see [Zbl 1318.68007].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Proc. of the Sixth Workshop on Algorithm Engineering and Experiments, pp. 62-69 (2004) |
| [2] | Bonsma, P.; Rovan, B.; Sassone, V.; Widmayer, P., The complexity of rerouting shortest paths, Mathematical Foundations of Computer Science 2012, 222-233 (2012), Heidelberg: Springer, Heidelberg · Zbl 1365.68273 · doi:10.1007/978-3-642-32589-2_22 |
| [3] | Cereceda, L.; van den Heuvel, J.; Johnson, M., Connectedness of the graph of vertex-colourings, Discrete Mathematics, 308, 56, 913-919 (2008) · Zbl 1133.05053 · doi:10.1016/j.disc.2007.07.028 |
| [4] | Diestel, R.: Graph Theory. Electronic Edition. Springer (2005) · Zbl 1074.05001 |
| [5] | Downey, RG; Fellows, MR, Parameterized complexity (1997), New York: Springer, New York |
| [6] | Fellows, MR; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038 · doi:10.1016/j.tcs.2008.09.065 |
| [7] | Fellows, M.R., Rosamond, F.A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? In: Proc. of the 21st International Joint Conference on Artifical Intelligence, pp. 486-491 (2009) · Zbl 1244.68070 |
| [8] | Garey, MR; Johnson, DS; Stockmeyer, LJ, Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, 3, 237-267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 |
| [9] | Gopalan, P.; Kolaitis, PG; Maneva, EN; Papadimitriou, CH, The connectivity of boolean satisfiability: computational and structural dichotomies, SIAM J. Comput., 38, 6, 2330-2355 (2009) · Zbl 1201.03024 · doi:10.1137/07070440X |
| [10] | Hearn, RA; Demaine, ED, 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) · Zbl 1079.68040 · doi:10.1016/j.tcs.2005.05.008 |
| [11] | Ito, T.; Demaine, ED; Harvey, NJA; Papadimitriou, CH; Sideri, M.; Uehara, R.; Uno, Y., On the complexity of reconfiguration problems, Theor. Comput. Sci., 412, 12-14, 1054-1065 (2011) · Zbl 1207.68166 · doi:10.1016/j.tcs.2010.12.005 |
| [12] | Kamiński, M.; Medvedev, P.; Milanič, M., Complexity of independent set reconfigurability problems, Theor. Comput. Sci., 439, 9-15 (2012) · Zbl 1246.05121 · doi:10.1016/j.tcs.2012.03.004 |
| [13] | Mouawad, AE; Nishimura, N.; Raman, V.; Simjour, N.; Suzuki, A.; Gutin, G.; Szeider, S., On the parameterized complexity of reconfiguration problems, Parameterized and Exact Computation, 281-294 (2013), Heidelberg: Springer, Heidelberg · Zbl 1350.68155 · doi:10.1007/978-3-319-03898-8_24 |
| [14] | Suzuki, A.; Mouawad, AE; Nishimura, N.; Cai, Z.; Zelikovsky, A.; Bourgeois, A., Reconfiguration of dominating sets, Computing and Combinatorics, 405-416 (2014), Heidelberg: Springer, Heidelberg · Zbl 1425.05126 · doi:10.1007/978-3-319-08783-2_35 |
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.
