Back
s00453-023-01141-z
Journal article

Reducing Graph Parameters by Contractions and Deletions

BP2-STS

  • 09.07.2023
Published in:
  • Algorithmica. - Springer Nature. - 2023
Blocker problems
Edge contraction
Vertex deletion
Edge deletion
Chromatic number
Independence number
Clique number
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 NP-hard 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 H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard 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
  • English
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: 33 File downloads:
  • s00453-023-01141-z.pdf: 127