On blockers and transversals of maximum independent sets in co-comparability graphs
BP2-STS
- Lucke, Felicia ORCID Université de Fribourg, Switzerland
- Ries, Bernard ORCID Université de Fribourg, Switzerland
- 2024
Published in:
- Discrete Applied Mathematics. - Elsevier BV. - 2024, vol. 356, p. 307-321
English
In this paper, we consider the following two problems: (i) Deletion Blocker(α) where we are given an undirected graph G = (V, E) and two integers k, d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with |S| ≤ k such that α(G−S) ≤ α(G)−d, that is the independence number of G decreases by at least d after having removed the vertices from S; (ii) Transversal(α) where we are given an undirected graph G = (V, E) and two integers k, d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with |S| ≤ k such that for every maximum independent set I we have |I ∩ S| ≥ d. We show that both problems are polynomial-time solvable in the class of co-comparability graphs by reducing them to the well-known Vertex Cut problem. Our results generalise a result of Chang et al. (2001) and a recent result of Hoang et al. (2023).
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Mathematics
- License
- CC BY
- Open access status
- hybrid
- Identifiers
-
- DOI 10.1016/j.dam.2024.06.020
- ISSN 0166-218X
- Persistent URL
- https://folia.unifr.ch/unifr/documents/328987
Statistics
Document views: 15
File downloads:
- co-comparability.pdf: 69