On blockers and transversals of maximum independent sets in co-comparability graphs.

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). [ABSTRACT FROM AUTHOR]