We study the existence and construction of sparse supports for hypergraphs derived from subgraphs of a graph $G$. For a hypergraph $(X,\mathcal{ H})$, a support $Q$ is a graph on $X$ s.t. $Q[H]$, the graph induced on vertices in $H$ is connected for every $H\in\mathcal{ H}$. We consider \emph{ primal}, \emph{ dual}, and \emph{ intersection} hypergraphs defined by subgraphs of a graph $G$ that are \emph{ non-piercing}, (i.e., each subgraph is connected, their pairwise differences remain connected). If $G$ is outerplanar, we show that the primal, dual and intersection hypergraphs admit supports that are outerplanar. For a bounded treewidth graph $G$, we show that if the subgraphs are non-piercing, then there exist supports for the primal and dual hypergraphs of treewidth $O(2^{ tw(G)})$ and $O(2^{ 4tw(G)})$ respectively, and a support of treewidth $2^{ O(2^{ tw(G)})}$ for the intersection hypergraph. We also show that for the primal and dual hypergraphs, the exponential blow-up of treewidth is sometimes essential. All our results are algorithmic and yield polynomial-time algorithms (when the treewidth is bounded). The existence and construction of sparse supports is a crucial step in the design and analysis of PTASs and/or sub-exponential time algorithms for several packing and covering problems.
Categories: math.CO cs.DM