Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
BP2-STS
- Lucke, Felicia Université de Fribourg
- Mann, Felix Université de Fribourg
- 29.05.2022
Published in:
- Combinatorial Algorithms / Bazgan, Cristina ; Fernau, Henning. - Springer International Publishing. - 2022, p. 412-424
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 π 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 also 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 on 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 (C3 +P1)-free graphs even for fixed d = 1. Our results answer several open questions stated in [Diner et al., Theoretical Computer Science, 746, p. 49-72 (2012)].
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- Rights reserved
- Open access status
- green
- Identifiers
-
- DOI 10.1007/978-3-031-06678-8_30
- ISSN 0302-9743
- ISBN 9783031066771
- Persistent URL
- https://folia.unifr.ch/unifr/documents/322641
Statistics
Document views: 40
File downloads:
- final_version_0.pdf: 179