Conference paper (in proceedings)
Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
BP2STS
Published in:
 Combinatorial Algorithms / Bazgan, Cristina ; Fernau, Henning.  Springer International Publishing.  2022, p. 412424
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 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 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 Hfree graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NPhard 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. 4972 (2012)].

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science and technology

License

Rights reserved

Open access status

green

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/322641
Statistics
Document views: 14
File downloads: