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

doi:10.1007/s11704-022-2200-8

Front. Comput. Sci.

2023, Vol. 17

Issue (4) : 174405 https://doi.org/10.1007/s11704-022-2200-8

RESEARCH ARTICLE

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

Jia LI¹, Wenjun LI², Yongjie YANG³, Xueying YANG²(

)

¹. School of Information Engineering, Hunan Industry Polytechnic, Changsha 410036, China
². Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410015, China
³. Chair of Economic Theory, Saarland University, Saarbrücken 66123, Germany

Download: PDF(8338 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In the minimum degree vertex deletion problem, we are given a graph, a distinguished vertex in the graph, and an integer $κ$ , and the question is whether we can delete at most $κ$ 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 $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.

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

Corresponding Author(s): Xueying YANG

Just Accepted Date: 09 September 2022 Issue Date: 02 December 2022

Cite this article:

Jia LI,Wenjun LI,Yongjie YANG, et al. On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs[J]. Front. Comput. Sci., 2023, 17(4): 174405.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2200-8
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I4/174405

	Split graphs					Planar graphs
	General	$K 1, 6$ -free	$K 1, 5$ -free	$K 1, 4$ -free	$K 1, 3$ -free	Planar graphs
MaxDVD	$W$ [2]-hard ( $κ$ , Thm. 2)	$NP$ -hard (Thm. 6)			$P$ (Thm. 7)	$NP$ -hard (Thm. 10) (planar & bipartite)
	$O ? (2 κ ˉ)$ (Thm. 5)
	$FPT_$ ( $\| C \|$ , Thm. 3, Cor. 3),
	{ $O ? (2 \| I \|)$ } (Thm. 4)
MinDVD	$W$ [2]-hard ( $κ$ , Cor. 1)	$NP$ -hard (Thm. 8)	open		$P$ (Thm. 9)	$P$ (Thm. 11, Cor. 4)
	$O ? (2 κ ˉ)$ (Thm. 5)
	$O ? (2 \| C \|)$ (Cor. 2)
	$FPT_$ ( $\| I \|$ , Thms. 1, 3, Cor. 3)

Tab.1 A summary of our results. Underlined

FPT

-results mean that they are based on the ILP technique, and the corresponding problems do not admit polynomial kernels unless the polynomial hierarchy collapses to the third level. In addition,

C

and

I

are, respectively, the clique and the independent set in a split partition

(C, I)

κ

is the number of vertices allowed to be deleted, and

κ ˉ

is the number of remaining vertices. In addition, "

P

" stands for "polynomial-time solvable"

1	S, Mishra A, Pananjady N Devi . On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion. Journal of Discrete Algorithms, 2015, 33: 71–80
2	M R, Fellows J, Guo H, Moser R Niedermeier . A generalization of Nemhauser and Trotter’s local optimization theorem. Journal of Computer and System Sciences, 2011, 77( 6): 1141–1158
3	A, Clauset C, Moore M Newman . Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453( 7191): 98–101
4	N, Betzler J Uhlmann . Parameterized complexity of candidate control in elections and related digraph problems. Theoretical Computer Science, 2009, 410( 52): 5425–5442
5	N, Betzler H L, Bodlaender R, Bredereck R, Niedermeier J Uhlmann . On making a distinguished vertex of minimum degree by vertex deletion. Algorithmica, 2014, 68( 3): 715–738
6	N, Betzler R, Bredereck R, Niedermeier J Uhlmann . On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics, 2012, 160( 1−2): 53–60
7	R, Ganian F, Klute S Ordyniak . On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica, 2021, 83( 1): 297–336
8	A, Dessmark K, Jansen A Lingas . The maximum k-dependent and f-dependent set problem. In: Proceedings of the 4th International Symposium on Algorithms and Computation. 1993, 88−97
9	S, Foldes P L Hammer . Split graphs having Dilworth number two. Canadian Journal of Mathematics, 1977, 29( 3): 666–672
10	R Merris . Split graphs. European Journal of Combinatorics, 2003, 24( 4): 413–430
11	P, Renjith N Sadagopan . Hamiltonian path in K1, t -free split graphs- a dichotomy. In: Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics. 2018, 30−44
12	Y, Yang Y R, Shrestha W, Li J Guo . On the kernelization of split graph problems. Theoretical Computer Science, 2018, 734: 72–82
13	S, Földes P L Hammer . Split graphs. In: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing. 1977, 311−315
14	J, Guo R Niedermeier . 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	W, Luo J, Wang Q, Feng J, Guo J Chen . Improved linear problem kernel for planar connected dominating set. Theoretical Computer Science, 2013, 511: 2−12
16	G, Tan Q, Feng B, Zhuo N, Huang J Wang . New kernels for several problems on planar graphs. Theoretical Computer Science, 2020, 806: 587–594
17	J, Wang Y, Yang J, Guo J Chen . Planar graph vertex partition for linear problem kernels. Journal of Computer and System Sciences, 2013, 79( 5): 609–621
18	M Xiao . 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	M R, Garey D S Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979
20	M, Cygan F V, Fomin L, Kowalik D, Lokshtanov D, Marx M, Pilipczuk M, Pilipczuk S Saurabh . Parameterized Algorithms. Cham: Springer, 2015
21	D B West . Introduction to Graph Theory. Upper Saddle River: Prentice-Hall, 2000
22	T F Gonzalez . Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 1985, 38: 293–306
23	R G, Downey M R, Fellows U Stege . Parameterized complexity: a framework for systematically confronting computational intractability. In: Proceedings of Contemporary Trends in Discrete Mathematics. 1999, 49−99
24	A, Frank É Tardos . An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica, 1987, 7( 1): 49–65
25	R Kannan . Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 1987, 12( 3): 415–440
26	H W Jr Lenstra . Integer programming with a fixed number of variables. Mathematics of Operations Research, 1983, 8( 4): 538–548
27	B Courcelle . 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	D S Hochbaum . Approximating clique and biclique problems. Journal of Algorithms, 1998, 29( 1): 174–200
29	M, Dom D, Lokshtanov S Saurabh . 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	V, Garnero I, Sau D M Thilikos . A linear kernel for planar red-blue dominating set. Discrete Applied Mathematics, 2017, 217: 536–547
32	D R, Lick A T White . k-degenerate graphs. Canadian Journal of Mathematics, 1970, 22( 5): 1082–1096

[1]

FCS-22200-OF-JL_suppl_1

Download

[1]	Yongjie YANG, Dinko DIMITROV. Group control for procedural rules: parameterized complexity and consecutive domains[J]. Front. Comput. Sci., 2024, 18(3): 183402-.

Viewed

Full text

Abstract

Cited

Shared

Discussed