Algorithms and Complexity of Hedge Cluster Deletion Problems

A hedge graph is a graph whose edge set has been partitioned into groups called hedges. Here we consider a generalization of the well-known $\text{textsc}ClusterDeletion$ problem, named $\text{textsc}HedgeClusterDeletion$. The task is to compute the minimum number of hedges of a hedge graph so that their removal results in a graph that is isomorphic to a disjoint union of cliques. We identify NP-completeness and polynomial-time solutions based on vertex-disjoint 3-vertex-paths as subgraphs. Regarding its approximability, we show that it is NP-hard to approximate $\text{textsc}HedgeClusterDeletion$ within factor $2^{O({\log }^{1-\epsilon }r)}$ for any $\epsilon >0$, where $r$ is the number of hedges in a given hedge graph. While $\text{textsc}HedgeClusterDeletion$ is fixed-parameter tractable with respect to the solution size (i.e., the number of removal hedges), we prove that it does not admit a polynomial kernel, unless NP $\subseteq$ coNP/poly. Moreover, we consider the hedge underlying structure. We give a polynomial-time algorithm with constant approximation ratio for $\text{textsc}HedgeClusterDeletion$ whenever each triangle of the input graph is covered by at most two hedges. On the way to this result, an interesting ingredient that we solved efficiently is a variant of the $\text{textsc}VertexCover$ problem in which apart from the desired vertex set that covers the edge set, a given set of vertex-constraints should also be included in the solution. Moreover, as a possible workaround for the existence of efficient exact algorithms, we propose the hedge intersection graph which is the intersection graph spanned by the hedges. Towards this direction, we give a polynomial-time algorithm for $\text{textsc}HedgeClusterDeletion$ whenever the hedge intersection graph is acyclic.