×

zbMATH — the first resource for mathematics

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. (English) Zbl 07001169
Summary: This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum \(s\)-\(t\) separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

MSC:
90C Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] van Bevern, R.; Fluschnik, T.; Mertzios, G. B.; Molter, H.; Sorge, M.; Suchý, O., Finding secluded places of special interest in graphs, (Proc. 11th IPEC, LIPIcs, vol. 63, (2017), Schloss Dagstuhl), 5:1-5:16 · Zbl 1398.68408
[2] Chechik, S.; Johnson, M. P.; Parter, M.; Peleg, D., Secluded connectivity problems, Algorithmica, 79, 3, 708-741, (2017) · Zbl 1380.68307
[3] Ito, H.; Iwama, K.; Osumi, T., Linear-time enumeration of isolated cliques, (Proc. 13th ESA, LNCS, vol. 3669, (2005), Springer), 119-130 · Zbl 1162.68497
[4] Gaertler, M., Clustering, (Brandes, U.; Erlebach, T., Network Analysis: Methodological Foundations [Outcome of a Dagstuhl Seminar, 13-16 April 2004], LNCS, vol. 3418, (2004), Springer), 178-215 · Zbl 1118.68324
[5] Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Isolation concepts for clique enumeration: Comparison and computational experiments, Theoret. Comput. Sci., 410, 52, 5384-5397, (2009) · Zbl 1192.68484
[6] Hüffner, F.; Komusiewicz, C.; Sorge, M., Finding highly connected subgraphs, (Proc. 41st SOFSEM, LNCS, vol. 8939, (2015), Springer), 254-265 · Zbl 1432.68358
[7] Komusiewicz, C.; Hüffner, F.; Moser, H.; Niedermeier, R., Isolation concepts for efficiently enumerating dense subgraphs, Theoret. Comput. Sci., 410, 38-40, 3640-3654, (2009) · Zbl 1171.68030
[8] Fomin, F. V.; Golovach, P. A.; Karpov, N.; Kulikov, A. S., Parameterized complexity of secluded connectivity problems, Theory Comput. Syst., 61, 3, 795-819, (2017) · Zbl 1378.68075
[9] Marx, D., Parameterized graph separation problems, Theoret. Comput. Sci., 351, 3, 394-406, (2006) · Zbl 1086.68104
[10] Fomin, F.; Golovach, P.; Korhonen, J., On the parameterized complexity of cutting a few vertices from a graph, (Proc. 38th MFCS, LNCS, vol. 8087, (2013), Springer), 421-432 · Zbl 1398.68231
[11] Bui, T. N.; Jones, C., Finding good approximate vertex and edge partitions is NP-hard, Inform. Process. Lett., 42, 3, 153-159, (1992) · Zbl 0764.68061
[12] Downey, R.; Estivill-Castro, V.; Fellows, M.; Prieto, E.; Rosamond, F., Cutting up is hard to do: the parameterized complexity of \(k\)-Cut and related problems, Electron. Notes Theor. Comput. Sci., 78, 209-222, (2003) · Zbl 1270.68112
[13] Bruglieri, M.; Ehrgott, M.; Hamacher, H. W.; Maffioli, F., An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Discrete Appl. Math., 154, 9, 1344-1357, (2006) · Zbl 1131.90048
[14] Cai, L.; Chan, S. M.; Chan, S. O., Random separation: A new method for solving fixed-cardinality optimization problems, (Proc. 2nd IWPEC, (2006), Springer), 239-250 · Zbl 1154.68568
[15] Cai, L., Parameterized complexity of cardinality constrained optimization problems, Comput. J., 51, 1, 102-121, (2008)
[16] Komusiewicz, C.; Sorge, M., An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, Discrete Appl. Math., 193, 145-161, (2015) · Zbl 1317.05107
[17] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science, (2013), Springer · Zbl 1358.68006
[18] Flum, J.; Grohe, M., Parameterized Complexity Theory, (2006), Springer
[19] Niedermeier, R., Invitation to Fixed-Parameter Algorithms, (2006), Oxford University Press · Zbl 1095.68038
[20] Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms, (2015), Springer · Zbl 1334.90001
[21] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2010), Springer) · Zbl 1204.05001
[22] West, D. B., Introduction to Graph Theory, (2000), Prentice Hall
[23] Kleinberg, J. M.; Tardos, É., Algorithm Design, (2006), Addison-Wesley
[24] Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85, 1, 12-75, (1990) · Zbl 0722.03008
[25] Marx, D.; O’Sullivan, B.; Razgon, I., Finding small separators in linear time via treewidth reduction, ACM Trans. Algorithms, 9, 4, 30:1-30:35, (2013) · Zbl 1301.05337
[26] Naor, M.; Schulman, L. J.; Srinivasan, A., Splitters and near-optimal derandomization, (Proceedings of IEEE 36th Annual Foundations of Computer Science, (1995), IEEE Computer Society), 182-191 · Zbl 0938.68932
[27] Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; Pilipczuk, M., A \(c^k n\) 5-approximation algorithm for treewidth, SIAM J. Comput., 45, 317-378, (2016) · Zbl 1333.05282
[28] Lokshtanov, D.; Misra, N.; Philip, G.; Ramanujan, M.; Saurabh, S., Hardness of \(r\)-dominating set on graphs of diameter (\(r + 1\)), (Proc. 8th IPEC, LNCS, vol. 8246, (2013), Springer), 255-267 · Zbl 1406.68042
[29] Dom, M.; Lokshtanov, D.; Saurabh, S., Kernelization lower bounds through colors and IDs, ACM Trans. Algorithms, 11, 2, 13, (2014) · Zbl 1398.68226
[30] van Bevern, R.; Moser, H.; Niedermeier, R., Approximation and tidying—a problem kernel for \(s\)-Plex cluster vertex deletion, Algorithmica, 62, 3-4, 930-950, (2012) · Zbl 1236.68100
[31] Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 1, 196-217, (2010) · Zbl 1205.68263
[32] Fellows, M.; Guo, J.; Moser, H.; Niedermeier, R., A complexity dichotomy for finding disjoint solutions of vertex deletion problems, ACM Trans. Comput. Theory, 2, 2, 5, (2011) · Zbl 1322.68101
[33] Lewis, J.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 2, 219-230, (1980) · Zbl 0436.68029
[34] Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. Process. Lett., 58, 4, 171-176, (1996) · Zbl 0875.68702
[35] van Bevern, R., (Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications, Foundations of Computing, vol. 1, (2014), Universittsverlag der TU Berlin)
[36] van Bevern, R., Towards optimal and expressive kernelization for \(d\)-Hitting Set, Algorithmica, 70, 1, 129-147, (2014) · Zbl 1314.68167
[37] Fafianie, S.; Kratsch, S., A shortcut to (sun)flowers: Kernels in logarithmic space or linear time, (Proc. 40th MFCS, LNCS, vol. 9235, (2015), Springer), 299-310 · Zbl 06482817
[38] Giannopoulou, A. C.; Lokshtanov, D.; Saurabh, S.; Suchý, O., Tree deletion set has a polynomial kernel (but no OPT\({}^{O(1)}\) approximation), SIAM J. Discrete Math., 30, 3, 1371-1384, (2016) · Zbl 1341.05239
[39] Seidman, S., Network structure and minimum degree, Social Networks, 5, 3, 269-287, (1983)
[40] Thomassé, S., A \(4 k^2\) kernel for feedback vertex set, ACM Trans. Algorithms, 6, 2, (2010)
[41] Fomin, F.; Lokshtanov, D.; Misra, N.; Saurabh, S., Planar F-Deletion: Approximation, kernelization and optimal FPT algorithms, (Proc. 56th FOCS, (2012), IEEE Computer Society), 470-479
[42] Bafna, V.; Berman, P.; Fujito, T., A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J. Discrete Math., 12, 3, 289-297, (1999) · Zbl 0932.68054
[43] Fellows, M.; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 1, 53-61, (2009) · Zbl 1161.68038
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.