Convert to Clique Method on Grid Hypergraphs
Nili Guttmann‐Beck, Levin, Avi, Noam Malter, Michal Stern · HAL (Le Centre pour la Communication Scientifique Directe) · 2025
Let $H= \langle V, \mathcal{S} \rangle$ be a hypergraph, where $V$ is a set of vertices and $\mathcal{S} = \{S_1,\ldots,S_m\} $ is a set of clusters $S_i \subseteq V$ such that $ \cup_{i=1}^m S_i = V$. The Clustered Spanning Tree by Trees problem determines whether a spanning tree exists on the complete graph on $V$, ensuring that each cluster induces a subtree. This paper focuses on grid hypergraphs, characterized by an intersection graph forming a grid, where no feasible solution exists.We present the Convert to Clique method, where we choose a vertex that is contained in two clusters and insert it into all the other clusters. This method always generates a hypergraph with a feasible solution tree. In the case of grid hypergraphs, we prove that the Convert to Clique method guarantees a minimum number of insertions to gain feasibility.