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

In this paper, we consider the following two problems: (i) Deletion Blocker(alpha) 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 subset of V with vertical bar S vertical bar <= k such that alpha(G-S) <= alpha(G) - d, that is the independence number of G decreases by at least d after having removed the vertices from S; (ii) Transversal(alpha) 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 vertical bar S vertical bar = k such that for every maximum independent set I we have vertical bar I boolean AND S vertical bar >= 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). (c) 2024 The Authors. Published by Elsevier B.V.