{"ID":2842215,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10202","arxiv_id":"2511.10202","title":"Algorithms and Complexity of Hedge Cluster Deletion Problems","abstract":"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 \\textsc{Cluster Deletion} problem, named \\textsc{Hedge Cluster Deletion}. 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 \\textsc{Hedge Cluster Deletion} within factor $2^{O(\\log^{1-ε} r)}$ for any $ε\u003e0$, where $r$ is the number of hedges in a given hedge graph. While \\textsc{Hedge Cluster Deletion} 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 \\textsc{Hedge Cluster Deletion} 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 \\textsc{Vertex Cover} 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 \\textsc{Hedge Cluster Deletion} whenever the hedge intersection graph is acyclic.","short_abstract":"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 \\textsc{Cluster Deletion} problem, named \\textsc{Hedge Cluster Deletion}. The task is to compute the minimum number of hedges of a hedge graph so that their removal results in a gr...","url_abs":"https://arxiv.org/abs/2511.10202","url_pdf":"https://arxiv.org/pdf/2511.10202v2","authors":"[\"Athanasios L. Konstantinidis\",\"Charis Papadopoulos\",\"Georgios Velissaris\"]","published":"2025-11-13T11:15:49Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}