On blockers and transversals of maximum independent sets in cocomparability graphs
BP2STS
Published in:
 Discrete Applied Mathematics.  Elsevier BV.  2024, vol. 356, p. 307321
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 polynomialtime solvable in the class of cocomparability graphs by reducing them to the wellknown 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


Classification

Mathematics

License

CC BY

Open access status

hybrid

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/328987
Statistics
Document views: 12
File downloads: