×

Vertex cover at distance on \(H\)-free graphs. (English) Zbl 07495026

Flocchini, Paola (ed.) et al., Combinatorial algorithms. 32nd international workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12757, 237-251 (2021).
Summary: The question of characterizing graphs \(H\) such that the Vertex Cover problem is solvable in polynomial time in the class of \(H\)-free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distance-based generalization of vertex cover called distance-\(k\) vertex cover, for any positive integer \(k\). In this problem the task is to determine, given a graph \(G\) and an integer \(\ell \), whether \(G\) contains a set of at most \(\ell\) vertices such that each edge of \(G\) is at distance at most \(k\) from a vertex in the set. We show that for all \(k \ge 1\) and all graphs \(H\), the distance-\(k\) vertex cover problem is solvable in polynomial time in the class of \(H\)-free graphs if \(H\) is an induced subgraph of \(P_{2k+2} + sP_{\max \{k,2\}}\) for some \(s \ge 0\), and NP-complete otherwise.
For the entire collection see [Zbl 1482.68020].

MSC:

68Rxx Discrete mathematics in relation to computer science
68Wxx Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3-13. Gor’kov. Gos. Univ., Gorki (1982)
[2] Alekseev, VE, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Appl. Math., 135, 1-3, 3-16 (2004) · Zbl 0931.05078 · doi:10.1016/S0166-218X(02)00290-1
[3] Alvarado, JD; Dantas, S.; Rautenbach, D., Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs, Discrete Appl. Math., 194, 154-159 (2015) · Zbl 1319.05097 · doi:10.1016/j.dam.2015.05.010
[4] Bacsó, G., Marx, D., Tuza, Z.: \(H\)-free graphs, independent sets, and subexponential-time algorithms. In: 11th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz International Proceedings o Inform., vol. 63, pp. Art. No. 3, 12, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2017) · Zbl 1398.05191
[5] Brandstädt, A., Mosca, R.: Maximum weight independent set for \(\ell\) claw-free graphs in polynomial time. Discrete Appl. Math. 237, 57-64 (2018). doi:10.1016/j.dam.2017.11.029 · Zbl 1380.05147
[6] Brešar, B.; Jakovac, M.; Katrenič, J.; Semanišin, G.; Taranenko, A., On the vertex \(k\)-path cover, Discrete Appl. Math., 161, 13-14, 1943-1949 (2013) · Zbl 1286.05076 · doi:10.1016/j.dam.2013.02.024
[7] Brešar, B.; Kardoš, F.; Katrenič, J.; Semanišin, G., Minimum \(k\)-path vertex cover, Discrete Appl. Math., 159, 12, 1189-1195 (2011) · Zbl 1223.05224 · doi:10.1016/j.dam.2011.04.008
[8] Busch, AH; Dragan, FF; Sritharan, R.; Wu, W.; Daescu, O., New min-max theorems for weakly chordal and dually chordal graphs, Combinatorial Optimization and Applications, 207-218 (2010), Heidelberg: Springer, Heidelberg · Zbl 1311.05159 · doi:10.1007/978-3-642-17461-2_17
[9] Camby, E.; Schaudt, O., A new characterization of \(P_k\)-free graphs, Algorithmica, 75, 1, 205-217 (2015) · Zbl 1339.05281 · doi:10.1007/s00453-015-9989-6
[10] Canales, S.; Hernández, G.; Martins, M.; Matos, I., Distance domination, guarding and covering of maximal outerplanar graphs, Discrete Appl. Math., 181, 41-49 (2015) · Zbl 1304.05022 · doi:10.1016/j.dam.2014.08.040
[11] Chang, GJ; Nemhauser, GL, The \(k\)-domination and \(k\)-stability problems on sun-free chordal graphs, SIAM J. Algebraic Discrete Methods, 5, 3, 332-345 (1984) · Zbl 0576.05054 · doi:10.1137/0605034
[12] Corneil, DG; Lerchs, H.; Burlingham, LS, Complement reducible graphs, Discrete Appl. Math., 3, 3, 163-174 (1981) · Zbl 0463.05057 · doi:10.1016/0166-218X(81)90013-5
[13] Courcelle, B.; Makowsky, JA; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150 (2000) · Zbl 1009.68102 · doi:10.1007/s002249910009
[14] Dvořák, Z., On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs, J. Graph Theory, 91, 2, 162-173 (2019) · Zbl 1418.05100 · doi:10.1002/jgt.22426
[15] Eto, H.; Guo, F.; Miyano, E., Distance-\(d\) independent set problems for bipartite and chordal graphs, J. Combin. Optimizat., 27, 1, 88-99 (2013) · Zbl 1302.68139 · doi:10.1007/s10878-012-9594-4
[16] Gartland, P., Lokshtanov, D.: Independent set on \(P_k\)-free graphs in quasi-polynomial time. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 613-624, IEEE (2020). doi:10.1109/FOCS46700.2020.00063
[17] Grzesik, A., Klimošová, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1257-1271, SIAM, Philadelphia, PA (2019). doi:10.1137/1.9781611975482.77 · Zbl 1431.68047
[18] Horton, J.D., López-Ortiz, A.: On the number of distributed measurement points for network tomography. In: Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, IMC 2003, Miami Beach, FL, USA, October 27-29, 2003, pp. 204-209, ACM (2003)
[19] Jaffke, L.; Kwon, OJ; Strømme, TJF; Telle, JA, Mim-width III. Graph powers and generalized distance domination problems, Theoret. Comput. Sci., 796, 216-236 (2019) · Zbl 1442.05157 · doi:10.1016/j.tcs.2019.09.012
[20] Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations, Proceedings of the Symposium IBM Thomas Journal Watson Research Center, Yorktown Heights, N.Y., 1972, pp. 85-103 (1972) · Zbl 1467.68065
[21] Katsikarelis, I., Lampis, M., Paschos, V.T.: Structurally parameterized \(d\)-scattered set. In: Brandstädt, A., Köhler, E., Meer, K. (eds.) Graph-Theoretic Concepts in Computer Science, LNCS, vol. 11159, pp. 292-305, Springer, Cham (2018). doi:10.1007/978-3-030-00256-5_24 · Zbl 1519.05103
[22] Lee, E.: Partitioning a graph into small pieces with applications to path transversal. Math. Program. (1), 1-19 (2018). doi:10.1007/s10107-018-1255-7 · Zbl 1452.68137
[23] Lemańska, M., On the minimum vertex \(k\)-path cover of trees, Util. Math., 100, 299-307 (2016) · Zbl 1354.05109
[24] Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570-581. ACM, New York (2014). doi:10.1137/1.9781611973402.43 · Zbl 1422.68126
[25] Luce, RD, Connectivity and generalized cliques in sociometric group structure, Psychometrika, 15, 169-190 (1950) · doi:10.1007/BF02289199
[26] Marx, D.; Pilipczuk, M.; Bansal, N.; Finocchi, I., Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams, Algorithms - ESA 2015, 865-877 (2015), Heidelberg: Springer, Heidelberg · Zbl 1422.68253 · doi:10.1007/978-3-662-48350-3_72
[27] Meir, A.; Moon, JW, Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 1, 225-233 (1975) · Zbl 0315.05102 · doi:10.2140/pjm.1975.61.225
[28] Minty, GJ, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 28, 3, 284-304 (1980) · Zbl 0434.05043 · doi:10.1016/0095-8956(80)90074-X
[29] Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13(2), 161-173 (1979)
[30] Montealegre, P.; Todinca, I.; Heggernes, P., On distance-d independent set and other problems in graphs with “few” minimal separators, Graph-Theoretic Concepts in Computer Science, 183-194 (2016), Heidelberg: Springer, Heidelberg · Zbl 1417.05227 · doi:10.1007/978-3-662-53536-3_16
[31] Pilipczuk, M., Siebertz, S.: Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs. Eur. J. Combin. 94, 103309, 19 (2021). doi:10.1016/j.ejc.2021.103309 · Zbl 1506.05162
[32] Poljak, S., A note on stable sets and colorings of graphs, Comment. Math. Univ. Carolinae, 15, 307-309 (1974) · Zbl 0284.05105
[33] Sasaki, M., Zhao, L., Nagamochi, H.: Security-aware beacon based network monitoring. In: 2008 11th IEEE Singapore International Conference on Communication Systems, pp. 527-531. IEEE (2008)
[34] Sbihi, N., Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math., 29, 1, 53-76 (1980) · Zbl 0444.05049 · doi:10.1016/0012-365X(90)90287-R
[35] Stockmeyer, LJ; Vazirani, VV, NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett., 15, 1, 14-19 (1982) · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1
[36] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 3, 364-372 (1980) · Zbl 0455.05047 · doi:10.1137/0138030
[37] Zhang, Z.; Li, X.; Shi, Y.; Nie, H.; Zhu, Y., PTAS for minimum \(k\)-path vertex cover in ball graph, Inform. Process. Lett., 119, 9-13 (2017) · Zbl 1401.68365 · doi:10.1016/j.ipl.2016.11.003
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.