Polynomial-Time Data Reduction for the Subset Interconnection Design Problem

Source abstract

The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set $V$ and a collection of subsets $V_1, V_2, \ldots, V_m \subseteq V$, and asks for a minimum-cardinality edge set $E$ such that for the graph $G=(V,E)$ all induced subgraphs $G[V_1], G[V_2], \ldots, G[V_m]$ are connected. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve the possibility of constructing optimal solutions. Our contribution is threefold: First, we show the incorrectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number $m$ of subsets, implying fixed-parameter tractability for the parameter $m$. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design.