Reducing Graph Parameters by Contractions and Deletions
BP2STS
Published in:
 Algorithmica.  Springer Nature.  2023
English
We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter $$\pi $$by at least d? We show that this problem is NPhard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed $$d=1$$and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for Hfree graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NPhard in $$(C_3+P_1)$$free graphs even for fixed $$d=1$$. When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023).

Faculty
 Faculté des sciences et de médecine

Department
 Département d'informatique

Language


Classification

Computer science and technology

License

CC BY

Open access status

hybrid

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/325718
Statistics
Document views: 21
File downloads:
 s0045302301141z.pdf: 48