×

zbMATH — the first resource for mathematics

PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs. (English) Zbl 1382.05037
Summary: For a set \(\mathcal{H}\) of graphs, a graph \(G\) is \(\mathcal{H}\)-free if \(G\) does not contain any subgraph isomorphic to some graph in \(\mathcal{H}\). In this paper, we study the minimum \(\mathcal{H}\)-free node deletion problem (\(\text{Min}\mathcal{H}\text{FND}\)) and the maximum \(\mathcal{H}\)-free node set problem (\(\text{Max}\mathcal{H}\text{FND}\)), which include a lot of extensively-studied problems such as the minimum \(k\)-path vertex cover problem, the dissociation number problem, and the minimum degree bounded node deletion problem. For a large class of \(\mathcal{H}\), PTASs are given for \(\text{Min}\mathcal{H}\text{FND}\) and \(\text{Max}\mathcal{H}\text{FND}\) on disk graphs whose heterogeneity is bounded by a constant, where the heterogeneity of a disk graph is the ratio of the maximum radius to the minimum radius of disks.

MSC:
05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Ann. Discrete Math., 25, 27-46, (1985) · Zbl 0545.90074
[2] Bazgan, C.; Escoffier, B.; Paschos, V. T., Completeness in standard and differential approximation classes: poly-(D)APX- and (D)PTAS-completeness, Theor. Comput. Sci., 339, 272-292, (2005) · Zbl 1068.68063
[3] Betzler, N.; Bredereck, R.; Niedermeier. J. Uhlmann, R., On bounded-degree vertex deletion parameterized by treewidth, Discrete Appl. Math., 160, 53-60, (2012) · Zbl 1236.05064
[4] A. Björklund, T. Husfeldt, P. Kaski, A.M. Koivisto, Narrow sieves for parameterized paths and packings, arXiv:1007.1161. · Zbl 1370.68321
[5] Brešar, B.; Jakovac, M.; Katrenič, J.; Semanišin, G.; Taranenko, A., On the vertex \(k\)-path cover, Discrete Appl. Math., 161, 1943-1949, (2013) · Zbl 1286.05076
[6] Brešar, B.; Kardoš, F.; Katrenič, J.; Semanišin, G., Minimum \(k\)-path vertex cover, Discrete Appl. Math., 159, 1189-1195, (2011) · Zbl 1223.05224
[7] Brešar, B.; Krivoš-Belluš, R.; Semanišin, G.; Šparl, P., On the weighted \(k\)-path vertex cover problem, Discrete Appl. Math., 177, 14-18, (2014) · Zbl 1297.05103
[8] T.M. Chan, S. Har-Peled, Approximation algorithms for maximum independent set of pseudo-disks, in: SCG’09, 2009, pp. 333-340. · Zbl 1388.68285
[9] M. Chang, L. Chen, L. Hung, Y. Liu, P. Rossmanith, S. Sikdar, An \(O^\ast(1 . 465 8^n)\)-time exact algorithm for the maximum bounded-degree-1 set problem, in: Proceedings of the 31st Workshop on Combinatorial Mathematics and Computation Theory, 2014, pp. 9-18.
[10] Chang, M.; Chen, L.; Hung, L.; Rossmanith, P.; Su, P., Fixed-parameter algorithms for vertex cover \(P_3\), Discrete Optim., 19, 12-22, (2016) · Zbl 1387.05248
[11] Fujito, T., A unified approximation algorithm for node-deletion problems, Discrete Appl. Math., 86, 213-231, (1998) · Zbl 0906.68106
[12] T. Fujito, Approximating bounded degree deletion via matroid matching, in: CIAC’17, 2017, pp. 234-246. · Zbl 06751065
[13] Ghosh, E.; Kolay, S.; Kumar, M.; Misra, P.; Panolan, F.; Rai, A.; Ramanujan, M. S., Faster parameterized algorithms for deletion to split graphs, Algorithmica, 71, 4, 989-1006, (2015) · Zbl 1325.68108
[14] M. Gibson, I.A. Pirwani, Algorithms for dominating set in disk graphs: breaking the \(l o g(n)\) Barrier, ESA10, Part I, 2010, pp. 243-254. · Zbl 1287.05149
[15] Jakovac, M., The \(k\)-path vertex cover of rooted product graphs, Discrete Appl. Math., 187, 111-119, (2015) · Zbl 1315.05120
[16] Jakovac, M.; Taranenko, A., On the \(k\)-path vertex cover of some graph products, Discrete Math., 313, 94-100, (2013) · Zbl 1264.05102
[17] Kardoš, F.; Katrenič, J.; Schiermeyer, I., On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci., 412, 7009-7017, (2011) · Zbl 1227.68034
[18] Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625, (1979) · Zbl 0423.05039
[19] Kumar, M.; Mishra, S.; Devi, N. S.; Saurabh, S., Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, Theoret. Comput. Sci., 526, 90-96, (2014) · Zbl 1418.68245
[20] Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 219-230, (1980) · Zbl 0436.68029
[21] Li, Y.; Tu, J., A 2-approximation algorithm for the vertex cover \(P_4\) problem in cubic graphs, Int. J. Comput. Math., 91, 10, 2103-2108, (2014) · Zbl 1303.05199
[22] Li, X.; Zhang, Z.; Huang, X., Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover, Discrete Appl. Math., 205, 101-108, (2016) · Zbl 1333.05168
[23] Liu, X.; Lu, H.; Wang, W.; Wu, W., PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs, J. Global Optim., 56, 449-458, (2013) · Zbl 1275.90118
[24] C. Lund, M. Yannakakis, The approximation of maximum subgraph problems, in: ICALP1993, 1993, pp. 40-51. · Zbl 1422.68087
[25] Miller, G. L.; Teng, S.; Thurston, W.; Vavasis, S. A., Separators for sphere-packings and nearest neigbhor graphs, J. ACM, 44, 1-29, (1997) · Zbl 0883.68100
[26] Mustafa, N. H.; Ray, S., Improved results on geometric hitting set problems, Discrete Comput. Geom., 44, 883-895, (2010) · Zbl 1207.68420
[27] Novotny, M., Design and analysis of a generalized canvas protocol, (Proceedings of WISTP, LNCS, vol. 6033, (2010)), 106-121
[28] Okun, M.; Barak, A., A new approach for approximating node deletion problems, Inform. Process. Lett., 88, 231-236, (2003) · Zbl 1178.68685
[29] Thai, M.; Wang, F.; Liu, D.; Zhu, S.; Du, D.-Z., Connected dominating sets in wireless networks with different transmission ranges, IEEE Trans. Mob. Comput., 6:7, 721-730, (2007)
[30] Tu, J., A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Inform. Process. Lett., 115, 96-99, (2015) · Zbl 1305.05223
[31] Tu, J.; Yang, F., The vertex cover \(P_3\) problem in cubic graphs, Inform. Process. Lett., 113, 481-485, (2013) · Zbl 1358.05234
[32] Tu, J.; Zhou, W., A factor 2 approximation algorithm for the vertex cover \(P_3\) problem, Inform. Process. Lett., 111, 683-686, (2011) · Zbl 1260.68304
[33] Tu, J.; Zhou, W., A primal-dual approximation algorithm for the vertex cover \(P_3\) problem, Theoret. Comput. Sci., 412, 7044-7048, (2011) · Zbl 1228.68033
[34] Wang, L.; Du, W.; Zhang, Z.; Zhang, X., A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks, J. Comb. Optim., 33, 106-122, (2017) · Zbl 1366.90204
[35] Wang, L.; Zhang, X.; Zhang, Z.; Broersma, H., A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs, Theoret. Comput. Sci., 571, 58-66, (2015) · Zbl 1312.68234
[36] Wu, B., A measure and conquer approach for the parameterized bounded degree-one vertex deletion, (COCOON 2015, LNCS, vol. 9198, (2015)), 469-480 · Zbl 1347.68357
[37] Xiao, M.; Kou, S., Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs, (FAW 2015, LNCS, vol. 9130, (2015)), 282-293 · Zbl 1408.05129
[38] Yannakakis, M., Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 2, 310-327, (1981) · Zbl 0468.05044
[39] 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
[40] Zhang, Y.; Shi, Y.; Zhang, Z., Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem, Theoret. Comput. Sci., 535, 54-58, (2014) · Zbl 1417.68167
[41] Zhang, Z.; Wu, W.; Fan, L.; Du, D., Minimum vertex cover in ball graphs through local search, J. Global Optim., 29, 663-671, (2014) · Zbl 1301.90093
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.