On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs

Abstract

In the minimum degree vertex deletion problem, we are given a graph, a distinguished vertex in the graph, and an integer \kappa, and the question is whether we can delete at most \kappa vertices from the graph so that the distinguished vertex has the unique minimum degree. The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree. It is known that both problems are \mathsf{\text{NP}}-hard and fixed-parameter intractable with respect to some natural parameters. In this paper, we study the (parameterized) complexity of these two problems restricted to split graphs, p-degenerate graphs, and planar graphs. Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.

Graphical abstract

Keywords

minimum degree / maximum degree / vertex deletion / split graphs / planar graphs / parameterized complexity

References

[1] Mishra S, Pananjady A, Devi N . On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion. Journal of Discrete Algorithms, 2015, 33: 71–80

[2] Fellows M R, Guo J, Moser H, Niedermeier R . A generalization of Nemhauser and Trotter’s local optimization theorem. Journal of Computer and System Sciences, 2011, 77( 6): 1141–1158

[3] Clauset A, Moore C, Newman M . Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453( 7191): 98–101

[4] Betzler N, Uhlmann J . Parameterized complexity of candidate control in elections and related digraph problems. Theoretical Computer Science, 2009, 410( 52): 5425–5442

[5] Betzler N, Bodlaender H L, Bredereck R, Niedermeier R, Uhlmann J . On making a distinguished vertex of minimum degree by vertex deletion. Algorithmica, 2014, 68( 3): 715–738

[6] Betzler N, Bredereck R, Niedermeier R, Uhlmann J . On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics, 2012, 160( 1−2): 53–60

[7] Ganian R, Klute F, Ordyniak S . On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica, 2021, 83( 1): 297–336

[8] Dessmark A, Jansen K, Lingas A. The maximum k-dependent and f-dependent set problem. In: Proceedings of the 4th International Symposium on Algorithms and Computation. 1993, 88−97

[9] Foldes S, Hammer P L . Split graphs having Dilworth number two. Canadian Journal of Mathematics, 1977, 29( 3): 666–672

[10] Merris R . Split graphs. European Journal of Combinatorics, 2003, 24( 4): 413–430

[11] Renjith P, Sadagopan N. Hamiltonian path in K_{1, t} -free split graphs- a dichotomy. In: Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics. 2018, 30−44

[12] Yang Y, Shrestha Y R, Li W, Guo J . On the kernelization of split graph problems. Theoretical Computer Science, 2018, 734: 72–82

[13] Földes S, Hammer P L. Split graphs. In: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing. 1977, 311−315

[14] Guo J, Niedermeier R. Linear problem kernels for NP-hard problems on planar graphs. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming. 2017, 375−386

[15] Luo W, Wang J, Feng Q, Guo J, Chen J. Improved linear problem kernel for planar connected dominating set. Theoretical Computer Science, 2013, 511: 2−12

[16] Tan G, Feng Q, Zhuo B, Huang N, Wang J . New kernels for several problems on planar graphs. Theoretical Computer Science, 2020, 806: 587–594

[17] Wang J, Yang Y, Guo J, Chen J . Planar graph vertex partition for linear problem kernels. Journal of Computer and System Sciences, 2013, 79( 5): 609–621

[18] Xiao M. A new linear kernel for undirected planar feedback vertex set: smaller and simpler. In: Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management. 2014, 288−298

[19] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979

[20] Cygan M, Fomin F V, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parameterized Algorithms. Cham: Springer, 2015

[21] West D B. Introduction to Graph Theory. Upper Saddle River: Prentice-Hall, 2000

[22] Gonzalez T F . Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 1985, 38: 293–306

[23] Downey R G, Fellows M R, Stege U. Parameterized complexity: a framework for systematically confronting computational intractability. In: Proceedings of Contemporary Trends in Discrete Mathematics. 1999, 49−99

[24] Frank A, Tardos É . An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica, 1987, 7( 1): 49–65

[25] Kannan R . Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 1987, 12( 3): 415–440

[26] Lenstra H W Jr . Integer programming with a fixed number of variables. Mathematics of Operations Research, 1983, 8( 4): 538–548

[27] Courcelle B. Graph rewriting: an algebraic and logic approach. In: Van Leeuwen J, ed. Formal Models and Semantics: A Volume in Handbook of Theoretical Computer Science. Amsterdam: Elsevier, 1990, 193, 195−242

[28] Hochbaum D S . Approximating clique and biclique problems. Journal of Algorithms, 1998, 29( 1): 174–200

[29] Dom M, Lokshtanov D, Saurabh S . Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 2014, 11( 2): 13

[30] Alber J, Bodlaender H L, Fernau H, Niedermeier R. Fixed parameter algorithms for planar dominating set and related problems. In: Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. 2000, 97−110

[31] Garnero V, Sau I, Thilikos D M . A linear kernel for planar red-blue dominating set. Discrete Applied Mathematics, 2017, 217: 536–547

[32] Lick D R, White A T . k-degenerate graphs. Canadian Journal of Mathematics, 1970, 22( 5): 1082–1096

RIGHTS & PERMISSIONS

Higher Education Press