Jiehua Chen
email: jiehua.chen@tu-berlin.de

CHRISTIAN KOMUSIEWICZ ‡ Rolf Niedermeier
email: rolf.niedermeier@tu-berlin.de

Manuel Sorge
email: manuel.sorge@tu-berlin.de

OND ŘEJ SUCH Ý § Mathias Weller
email: mathias.weller@lirmm.fr

POLYNOMIAL-TIME DATA REDUCTION FOR THE SUBSET INTERCONNECTION DESIGN PROBLEM †

Keywords: NP-hard problem, fixed-parameter tractability, kernelization, combinatorial algorithms, preprocessing, hypergraph support AMS subject classifications. 05C65, 68Q25, 68R10, 68W05

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 , . . . , Vm ⊆ V , and asks for a minimum-cardinality edge set E such that for the graph

We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve the possibility to construct 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.

Subset Interconnection Design is a fundamental problem concerning hypergraph and graph structures that has many applications. Indeed, Subset Interconnection Design has been studied in the context of designing vacuum systems [START_REF] Du | On complexity of subset interconnection designs[END_REF][START_REF] Du | Matroids and subset interconnection design[END_REF], scalable overlay networks [START_REF] Chockler | Constructing scalable overlays for pub-sub with many topics[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF][START_REF] Onus | Minimum maximum-degree publish-subscribe overlay network design[END_REF], reconfigurable interconnection networks [START_REF] Fan | Interconnection graph problem[END_REF][START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF], and, in variants, in the context of inferring a most likely social network [START_REF] Angluin | Inferring social networks from outbreaks[END_REF], determining winners of combinatorial auctions [START_REF] Conitzer | Combinatorial auctions with structured item graphs[END_REF] as well as drawing hypergraphs [START_REF] Brandes | Path-based supports for hypergraphs[END_REF][START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF][START_REF] Klemz | Minimum tree supports for hypergraphs and low-concurrency euler diagrams[END_REF][START_REF] Korach | The clustering matroid and the optimal clustering tree[END_REF]. The respective research communities seem largely unaware of each other's work, for instance leading to multiple NP-hardness proofs. To the best of our knowledge, the problem was first defined by Du [START_REF] Du | An optimization problem on graphs[END_REF] and the first NPhardness proof was presented by Du and Miller [START_REF] Du | Matroids and subset interconnection design[END_REF]. SID has been independently studied under the names Minimum Topic-Connected Overlay by the "scalable overlay networks community" [START_REF] Chockler | Constructing scalable overlays for pub-sub with many topics[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF][START_REF] Onus | Minimum maximum-degree publish-subscribe overlay network design[END_REF], Subset Interconnection Design by the "vacuum systems community" [START_REF] Du | On complexity of subset interconnection designs[END_REF][START_REF] Du | A special case for subset interconnection designs[END_REF], and Interconnection Graph Problem by the "reconfigurable interconnection systems community" [START_REF] Fan | Interconnection graph problem[END_REF][START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF]. The term "topic-connected" in Minimum Topic-Connected Overlay refers to the desired property of overlay networks that agents interested in some particular topic should be able to inform each other about updates concerning this topic without involving other agents [START_REF] Onus | Minimum maximum-degree publish-subscribe overlay network design[END_REF]. The "social network inference community" [START_REF] Angluin | Inferring social networks from outbreaks[END_REF], additionally imposing edge costs, refers to this more general problem as Network Inference. The "graph drawing community" [START_REF] Brandes | Blocks of hypergraphs -Applied to hypergraphs and outerplanarity[END_REF][START_REF] Brandes | Path-based supports for hypergraphs[END_REF][START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF][START_REF] Kaufmann | Subdivision drawings of hypergraphs[END_REF] refers to a solution as support and is mainly concerned with finding solutions with certain structure, for example, planar solutions. In further literature, solutions are also called host graphs [START_REF] Bujtás | Color-bounded hypergraphs, V: Host graphs and subdivisions[END_REF] and spanning graphs [START_REF] Král | Mixed hypercacti[END_REF].

Our main focus is on analyzing the influence of three problem-specific parameters on the computational complexity of SID. The parameters are "size d := max F ∈F |F | of the largest hyperedge", "number m := |F | of hyperedges in the given hypergraph H", and "feedback edge number φ := kn + 1 of the solution" which is a measure of sparseness. Here, k is the number of edges of the constructed solution and n is the number |V | of vertices in the input hypergraph H. We perform a parameterized complexity analysis with respect to these parameters showing that small parameters yield efficient algorithms. Our core working machinery is the development of numerous polynomial-time data reduction rules, thereby extending previous work.

Previous Work. As mentioned above, SID has been independently studied in different communities. Several NP-hardness proofs have appeared [START_REF] Chockler | Constructing scalable overlays for pub-sub with many topics[END_REF][START_REF] Du | Matroids and subset interconnection design[END_REF][START_REF] Fan | Interconnection graph problem[END_REF]. NPhardness even holds for hypergraphs with d = 3 [START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF], while d ≤ 2 allows for polynomial-time solvability [START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF] because then the input hypergraph is itself an optimal solution. If the hypergraph is closed under intersections, that is, every intersection of hyperedges is also a hyperedge, then SID also becomes polynomial-time solvable [4, Lemma 1]. Polynomial-time approximability has also been intensely studied, providing various logarithmic-factor approximation algorithms [START_REF] Angluin | Inferring social networks from outbreaks[END_REF][START_REF] Chockler | Constructing scalable overlays for pub-sub with many topics[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF] and inapproximability results (implying that logarithmic-factor approximation algorithms are likely to be optimal) [START_REF] Angluin | Inferring social networks from outbreaks[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF]. The currently best exact algorithm for SID has a running time of O(n 2k /4 k + n 2 ) [START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF]. In addition, in a series of papers it has been shown that SID can be solved in polynomial time if 2 ≤ m ≤ 4 [START_REF] Du | An optimization problem on graphs[END_REF][START_REF] Tang | An optimality condition for minimum feasible graphs[END_REF][START_REF] Xu | On the minimum feasible graph for four sets[END_REF].

Much research focused on finding solutions of special structure [START_REF] Brandes | Blocks of hypergraphs -Applied to hypergraphs and outerplanarity[END_REF][START_REF] Brandes | Path-based supports for hypergraphs[END_REF][START_REF] Buchin | On planar supports for hypergraphs[END_REF][START_REF] Conitzer | Combinatorial auctions with structured item graphs[END_REF][START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF][START_REF] Kaufmann | Subdivision drawings of hypergraphs[END_REF]. For example, it has been shown that it is possible to test in linear time whether there is a solution that is a tree, a path, or a cycle [START_REF] Buchin | On planar supports for hypergraphs[END_REF][START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF]. Conversely, it is NPhard to test for planar solutions [START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF] or 2-outerplanar solutions [START_REF] Buchin | On planar supports for hypergraphs[END_REF]. A variant of SID where the edges incur costs and where the solution is restricted to be a tree has been studied in the context of communication network design [START_REF] Korach | The clustering matroid and the optimal clustering tree[END_REF]; this variant can be solved in O(n 2 (m + log(n))) time [START_REF] Klemz | Minimum tree supports for hypergraphs and low-concurrency euler diagrams[END_REF]. Finally, in the context of overlay networks, it is of specific interest to construct solutions with small maximum and small average vertex degree [START_REF] Chockler | Constructing scalable overlays for pub-sub with many topics[END_REF][START_REF] Onus | Minimum maximum-degree publish-subscribe overlay network design[END_REF]; the latter is achieved by SID.

Our Contribution. We start by revealing an incorrectness in two (very similar) plausible data reduction rules used in previous work [START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF] by constructing a counterexample that shows their failure (Section 3). Based on this, we provide both refined and completely new data reduction rules and prove their correctness and effectiveness. Many of our data reduction rules also work in a parameter-independent fashion, that is, they do not require knowledge of the parameter value which is just used for the mathematical analysis.

Generalizing previous work [START_REF] Du | An optimization problem on graphs[END_REF][START_REF] Tang | An optimality condition for minimum feasible graphs[END_REF][START_REF] Xu | On the minimum feasible graph for four sets[END_REF], we then show that SID can be solved in linear time if the input hypergraph contains only a constant number m of hyperedges (Section 4). This implies that SID is fixed-parameter tractable with respect to the parameter m.

For hyperedges of size d ≤ 4 we show that SID can be reduced in polynomial time to an equivalent instance of O(φ) vertices1 , known as "polynomial-size problem kernel" in parameterized algorithmics (Section 5.1). Making use of the developed data reduction rules, we further show that, for arbitrary d, SID can be solved in d 18dφ • poly(|H|) time (Section 5.2). Here |H| denotes F ∈F |F |. Our result implies that SID with small hyperedges becomes tractable if the solution is required to be almost a tree, generalizing the polynomial-time algorithm for trees [START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF].

Preliminaries.

Graphs and Hypergraphs. Given an undirected graph

G = (V, E) with vertex set V and edge set E, we use E(G) to denote the edge set E of G. We denote by G[V ′ ] the subgraph (V ′ , {e ⊆ V ′ | e ∈ E}) of G induced by V ′ . We also use G -V ′ as a shorthand for G[V \ V ′ ].
A feedback edge set of a graph G is a set of edges whose removal makes G a forest. The feedback edge number φ of G is the size of any minimum feedback edge set. If G is connected, then the feedback edge number is

|E| -|V | + 1.
Let V be a finite set and let F be a family of subsets of V . We call H = (V, F ) a hypergraph with vertex set V and hyperedge set F . Unless stated otherwise, we assume all hypergraphs to not contain singleton hyperedges, empty hyperedges, or multiple copies of the same hyperedge since they are not meaningful for SID, and searching for and removing them can be done in linear time. We use n to denote |V | and |H| to denote F ∈F |F |. We call v ∈ V and F ∈ F incident if v ∈ F . We denote by F (v) the set of all hyperedges that are incident with v, that is,

F (v) := {F ∈ F | v ∈ F }. If u, v ∈ V and F (u) ⊇ F (v)
, then we say that u covers v. Vertices that cover each other are called twins; a maximal set of twins is called twin class. The subhypergraph induced by V ′ is the hypergraph

H[V ′ ] := (V ′ , F ′ ) where F ′ = {F ⊆ V ′ | F ∈ F }.
By removing a vertex v from H, we mean taking the hypergraph H ′ = (V \ {v}, F ′ ), where F ′ is obtained from {F \{v} | F ∈ F }) by removing the empty set and singleton sets. A hyperwalk between vertices u and v is an alternating sequence of vertices and hyperedges starting in u and ending in v such that succeeding elements are incident. A hypergraph is connected if there is a hyperwalk between every pair of vertices.

The covering graph of hypergraph

H = (V, F ) is the directed graph G C = (V, {(u, v) | F (u) ⊇ F (v)}).
In other words, G C contains an arc (u, v) if and only if u covers v. Note that G C is transitive. Some of our reduction rules construct the covering graph of H as a subroutine. The following lemma bounds the running time for this step.

Lemma 2.1.

Given a hypergraph H = (V, F ) one can construct the covering graph G C in O(n • |H|) time. Proof. Initialize G C as (V, V × V ). Then, for each F ∈ F , remove the arcs in (V \ F ) × F from G C in O(n • |F |) time. Clearly, if (u, v
) is an arc of the resulting directed graph G C , then there is no hyperedge containing v but not u or, equivalently,

F (u) ⊇ F (v). If G C does not contain the arc (u, v), then, by the construction of G C , there is a hyperedge F ∈ F such that v ∈ F but u / ∈ F . Thus, G C contains exactly the edges (u, v) such that u covers v.
Parameterized Complexity. The concept of parameterized complexity was pioneered by Downey and Fellows [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] (see also the textbooks [START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]). A parameterized problem is a language L ⊆ Σ * × Σ * , where Σ is an alphabet. The second component is called the parameter of the problem. Typically, the parameter is a nonnegative integer. A parameterized problem L is fixed-parameter tractable if there is an algorithm that decides whether (x, k) ∈ L in f (k) • |x| O(1) time, where f is an arbitrary computable function depending only on k. A core tool in the development of fixedparameter algorithms is polynomial-time preprocessing by data reduction [START_REF] Guo | Invitation to data reduction and problem kernelization[END_REF]. Here, the goal is to transform a given problem instance (x, k) in polynomial time into an equivalent instance (x ′ , k ′ ) with parameter k ′ ≤ f (k) such that the size of (x ′ , k ′ ) is upper-bounded by g(k), where g and f are functions only depending on k. If this is the case, we call the instance (x ′ , k ′ ) a (problem) kernel of size g(k).

Data reduction is usually presented as a series of reduction rules. These are polynomial-time algorithms that take as input an instance of some decision problem and produce another instance of the same problem as output. A reduction rule is correct if for each input instance I, the corresponding output instance of the rule is a yes-instance if and only if I is a yes-instance. We call an instance I of a parameterized problem reduced with respect to a reduction rule if the reduction rule does not apply to I. That is, carrying out the reduction rule yields an unchanged instance.

Fundamental Observations on

Twins in Optimal Solutions. In this section, we show that a previously proposed data reduction rule for SID is incorrect. We also show some properties of SID's optimal solutions and some data reduction rules that are used in our algorithms. A very natural approach to identify edges of optimal solutions is to look for vertices u and v such that v covers u, that is, F (v) ⊇ F (u). The following shows that degree-one vertices of the solution are adjacent to vertices that cover them.

Observation 1.

If the hypergraph H = (V, F ) has a solution G such that some u ∈ V has only one neighbor v in G, then v covers u. Proof. Let F ∈ F be a hyperedge with u ∈ F . Since G[F ] is connected, u has degree at least one in G[F ]. Since v is the only neighbor of u in G it follows that v ∈ F .
It is thus tempting to devise a data reduction rule that adds an edge between such vertices: creating a degree-one vertex should be optimal since every vertex needs at least one incident edge. Indeed, such a reduction rule was proposed for vertex pairs u, v that are twins, that is, they are in the same hyperedges [START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF], or where one covers the other [START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF]. The variant of these reduction rules that applies less often reads as follows.

Rule 1. If hypergraph H = (V, F ) contains twins u and v, that is, F (u) = F (v), then remove u from H and decrease k by one.

Unfortunately, this rule is not correct, as a counterexample shows. Lemma 3.1. There is a yes-instance (H = (V, F ), k) containing twins u and v such that Rule 1 applied to u and v yields a no-instance.

Proof. Let x ≥ 3 be an arbitrary integer. Consider the hypergraph H = (V, F ), with vertex set V = {u, v, a 1 , . . . , a x , b 1 , . . . , b x } and hyperedge set F which is the union of the following sets of hyperedges:

F 1 = {{a i , b i } | i ∈ {1, . . . , x}}, F 2 = {{u, v, a i , b i } | i ∈ {1, . . . , x}}, F 3 = {{u, v, a i , b i , a j } | i, j ∈ {1, . . . , x}, i = j}, and F 4 = {{u, v, a i , b i , b j } | i, j ∈ {1, . . . , x}, i = j}.
Note that the graph G = (V, E) with E := F 1 ∪ {{a i , u}, {b i , v} | i ∈ {1, . . . , x}} is a solution for H containing 3x edges. Hence, (H, 3x) is a yes-instance. Now, let (H ′ = (V ′ , F ′ ), 3x -1) be an instance that results from (H, 3x) by applying Rule 1 to u and v, that is, removing u from H and decreasing the solution size bound k by one. An example showing parts of the hypergraph H ′ for x = 3 is given in Figure 2. Then, V ′ = V \ {u} and F ′ consists of the following hyperedges:

F 1 = {{a i , b i } | i ∈ {1, . . . , x}}, F ′ 2 = {{v, a i , b i } | i ∈ {1, . . . , x}}, F ′ 3 = {{v, a i , b i , a j } | i, j ∈ {1, . . . , x}, i = j}, and
F ′ 4 = {{v, a i , b i , b j } | i, j ∈ {1, . . . , x}, i = j}.
We show that every solution for H ′ has at least 3x edges and, thus, that (H ′ , 3x-1) is a no-instance. First, every solution for H ′ contains the x edges corresponding to the size-two hyperedges of F 1 . Furthermore, due to the hyperedges in F ′ 2 , for each i ∈ {1, . . . , x}, every solution contains {v, a i } or {v, b i }. By the symmetry between a i and b i in the hypergraph H ′ , assume without loss of generality that an optimal solution contains the edge {v, b i } for all i ∈ {1, . . . , x} (the set of these edges plus F 1 is shown in Figure 2). Now, let G ′ = (V ′ , E ′ ) be such a solution for

H ′ . Let A 1 = {a i | {v, a i } /
∈ E ′ } be the set of a i s that are not adjacent to v in G ′ and let A 2 denote the set of the remaining a i s. If A 1 = ∅, then G ′ contains at least 3x edges. We show that if A 1 = ∅, then the graph G ′ also has at least 3x edges. Assume that G ′ is optimal and that every optimal solution has at least y > 0 vertices in A 1 . For every hyperedge F = {v, a i , b i , a j } with a j ∈ A 1 and i ∈ {1, . . . , x} \ {j}, G ′ has an edge between a j and {v, a i , b i }, since G ′ [F ] is connected. Note that if G ′ contains the edge {b i , a j }, then we can replace this edge by {v, a j }: Since j = i, there is only one hyperedge, namely F , that contains both b i and a j . Clearly, G ′ [F ] can also be made connected by adding {v, a j } instead. This implies an optimal solution with y -1 vertices in A 1 , contradicting our choice of y. Hence, G ′ contains no edges {b i , a j } with i = j. Consequently, in order to make each hyperedge {v, a i , b i , a j } ∈ F ′ 3 with a j ∈ A 1 connected, there is an edge between a i and a j .

Hence, G ′ has y • (xy) edges between A 1 and A 2 , y 2 edges between vertices in A 1 and xy further edges between v and A 2 . Altogether the total number of edges in G ′ is thus at least

2x + y • (x -y) + y 2 + x -y = 3x + y • (2x -y -3) 2 ≥ 3x + y • (x -3) 2 ≥ 3x.
This implies that (H ′ , 3x -1) is a no-instance.

As one can see from the proof, the main reason for the incorrectness of Rule 1 is the incorrect assumption that there is an optimal solution which adds an edge between twins. However, with some additional conditions, rules similar to Rule 1 are correct (Rules 2 to 4, 6, and 8 below). First, if a vertex u is adjacent to some vertex v covering u in an optimal solution, then there is an optimal solution that shifts all other edges incident with u to v. Lemma 3.2. Let u, v be two vertices in a hypergraph H with v covering u. If H has an optimal solution G containing the edge {u, v}, then H also has an optimal solution with u being adjacent only to v.

Proof. Assume that u has degree at least two in G, that is, u has some neighbor w = v. Then, obtain a modified graph G ′ by replacing the edge {u, w} by the edge {v, w}. The modified graph G ′ has the same number of edges as G. Furthermore, the two endpoints of the removed edge {u, w} are still connected in each hyperedge that contains them: Since v covers u, such a hyperedge also contains v which is in G ′ a common neighbor of u and w. Hence, G ′ is also an optimal solution.

The above lemma immediately implies the following reduction rule. Rule 2. If hypergraph H = (V, F ) contains vertices u, v such that v covers u and if there is an optimal solution G containing the edge {u, v}, then remove u from H and decrease k by one.

Of course, it is not clear how to efficiently determine whether such an optimal solution exists. We later exhibit hypergraph structures that enforce this and then use Rule 2 as a subroutine.

Lemma 3.3. Rule 2 is correct.

Proof. If there is a solution of size at most k for H, then the condition of the rule together with Lemma 3.2 imply that there is a solution G of size at most k in which u has degree one and is adjacent to v. Then, G -{u} is a solution of size at most k -1 for H with u removed. Conversely, if there is a solution G ′ of size at most k -1 for H with u removed then adding the edge {u, v} gives a solution of size at most k for H since all hyperedges F containing u also contain v and the corresponding subhyperedges F \ {u} induce connected subgraphs of G ′ .

Note that the correctness of Rule 2 together with Lemma 3.1 implies that there are instances in which a twin class is an independent set in any optimal solution.

In the counterexample to Rule 1, there are only two twins and they are contained in hyperedges of size five, that is, the size-five hyperedges containing these two vertices have three other "unrelated" vertices. In the following, we show that this is tight, that is, if each hyperedge containing u also contains at most two vertices that do not cover u, then Rule 1 is correct.

Rule 3. If there are q+1 vertices u and v 1 , . . . , v q in the hypergraph H = (V, F ), q being a positive integer, such that each v i covers u and if for each hyperedge F ∈ F (u), |F | ≤ q + 3 holds, then remove u from H and decrease k by one.

See Figure 3 for a hypergraph to which Rule 3 applies with q = 3. Another example is the hypergraph H defined in Lemma 3.1 without the hyperedges in F 3 ∪F 4 . Then q = 1 and all hyperedges are of size at most four.

Lemma 3.4. Rule 3 is correct and can be applied exhaustively in O(n•|H|) time.

Proof. Let H = (V, F ) be a hypergraph, Q be the vertex set {v 1 , . . . , v q } ⊆ V , and u be a vertex in V such that Rule 3 applies. Further, let N denote the set of neighbors of u in an optimal solution G. If N ∩ Q = ∅, then the correctness follows from the correctness of Rule 2. Hence, we assume that N ∩ Q = ∅.

Case 1: N contains a neighbor w of some v ∈ Q in G. Let G ′ be the result of removing the edge {u, w} from G and adding {u, v}. If there is some hyperedge

F such that G ′ [F ] is disconnected, then u, w ∈ F . Since v covers u, also v ∈ F . Then, there is a path between u and w via v in G ′ [F ], implying that G ′ [F ] is connected. Case 2: N contains no neighbor of any v ∈ Q. Then, for each F ∈ F (u), |F ∩ N | ≤ 1 since otherwise, |F | ≤ q + 3 implies that F = {u} ∪ Q ∪ (F ∩ N ) and then G[F ]
does not contain a path between u and any vertex in Q. Thus, G ′ := G-{u} is a solution for the hypergraph H ′ that results from H by removing u. Note that G ′ has at least one edge less than G. Since all hyperedges of H that contain u are supersets of Q, adding u with the edge {v 1 , u} to G ′ results in a solution for H, which is optimal since

|E(G ′ )| + 1 ≤ |E(G)|.
It remains to prove the running time bound. For a vertex u, let Q be the set of vertices covering u. It is not hard to see that if Rule 3 applies to any subset of Q, then it also applies to Q. Reversing all arcs in the covering graph G C of H allows us to compute |Q| in constant time per vertex. Thus, assuming that the size of a hyperedge can be computed in constant time, Rule 3 can be applied exhaustively to

H = (V, F ) in O(n • |H| + n • u∈V |F (u)|) = O(n • |H|) time.
As a corollary of Lemma 3.4, we also obtain correctness of the following rule since it is a special case of Rule 3. This rule will be useful in Section 5.

Rule 4. If there are two vertices u and v such that v covers u and |F | ≤ 4 for each hyperedge F ∈ F (u), then remove u from H and decrease k by one.

Note that the condition |F | ≤ 4 in Rule 4 is also tight in the sense that if u is incident with hyperedges of size at least five, then Rule 4 is not correct as shown by Lemma 3.1.

Data Reduction for

Instances with Few Hyperedges. In this section, we show that SID is fixed-parameter tractable with respect to the number m of hyperedges. A previous fixed-parameter tractability result for this parameter [START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF]Theorem 8] relied on Rule 1 and is therefore incorrect. 2 The intuition behind Rule 1 is that it is optimal to connect a twin class by a spanning tree and to subsequently represent this twin class by a single vertex. This approach results in an instance with at most 2 m vertices which would imply fixed-parameter tractability. As the counterexample in Lemma 3.1 shows, a twin class can be disconnected in the subgraph induced by every optimal solution. Thus, in order to restore the fixed-parameter tractability result, we need a slightly more involved rule whose correctness proof makes use of the following upper bound on the number of edges needed in the solution.

Lemma 4.1. Every input instance of SID with k ≥ 2 m 2 +n-1 is a yes-instance. Proof. We show how to construct a solution G with less than 2 m 2 + n edges. The main idea is to first partition the vertex set into two subsets V ′ and V \ V ′ . We then construct a solution G ′ for the hypergraph H ′ resulting from H by removing the vertices in V \ V ′ . Finally, we obtain a solution for H by adding each time one edge connecting each vertex in V \ V ′ to the graph G ′ .

Recall that a twin class is a maximal set of vertices that mutually cover each other. Let V ′ consist of exactly one vertex from each twin class of H. Clearly,

|V ′ | ≤ 2 m
where m is the number of hyperedges. Let H ′ be the hypergraph resulting from removing all vertices that are not in V ′ from H. Obviously, a complete graph G ′ for V ′ is a solution for hypergraph H ′ . This solution has 2 m 2 edges. We now extend G ′ to a solution G for H as follows. Add each vertex v ∈ V \ V ′ to G ′ . Furthermore, add an edge incident to v and its twin in V ′ (recall that at least one vertex of each twin class is in V ′ ). Let G be the resulting graph. Since there is at least one twin class,

|V \ V ′ | ≤ n -1 and hence G contains at most 2 m 2 + n -1 edges.
Graph G is a solution for H since for each hyperedge

F ∈ F , the subgraph G[F ] is connected: G[V ′ ∩ F ] is a complete graph and each vertex in F \ V ′ is adjacent to its twin in F ∩ V ′ . Thus, G[F ] is connected.
The upper bound provided by Lemma 4.1 grows exponentially in the number of hyperedges. It would be interesting to replace this exponential dependence by a polynomial function. However, this is not possible in general; there are instances that require a solution with at least 2 Ω(m) + n edges, see Appendix A.

Lemma 4.1 directly yields the correctness of the following reduction rule. Rule 5. If k ≥ 2 m 2 + n -1, then answer "yes". Our aim is now to shrink the size each of the 2 m twin classes to be bounded by a function of m. For this, the following rule removes vertices from large twin classes.

Rule 6. Let (H, k) be an instance that is reduced with respect to Rule 5. If there is a twin class T in H with |T | > 4 m +7•2 m +1, then remove an arbitrary vertex v ∈ T from H and decrease k by one.

To prove the correctness of Rule 6, we show that there is a solution G that has the following property concerning its low-degree vertices. In the following, by degree-ℓ vertices we refer to vertices of degree exactly ℓ.

Lemma 4.2. Let H = (V, F ) be a connected hypergraph and |V | ≥ 3. Then, there is a solution G = (V, E) such that for each twin class T of H, graph G has 1. at most one vertex t ∈ T that has degree-one neighbors, and 2. at most one degree-two vertex t ′ ∈ T . Proof. Let G be a solution for H. We show how to transform G into a solution G * which fulfills both properties of the lemma. First, suppose that there is a nonempty set T = {T 1 , . . . , T q } of twin classes of H such that at least two vertices of each T i have degree-one neighbors in G. Now, modify G as follows. Pick an arbitrary vertex t i from each T i such that t i has a degree-one neighbor and label t i as the one vertex in twin class T i that will have degree-one neighbors in the modified solution G * .

Then, as long as T is nonempty, pick an arbitrary T i and an arbitrary vertex t ′ ∈ T i \ {t i }. Let X be the set of degree-one neighbors of t ′ in G. Note that t i / ∈ X as, otherwise, t i and its neighbor would form a connected component of size two in G. This contradicts the fact that G is a solution because by definition H is connected and contains at least three vertices. We remove all edges between X and t ′ and make all vertices in X adjacent to t i . Let G ′ be the resulting graph. Observe that G ′ has the same number of edges as G. Moreover, G ′ is also a solution: The vertices of X were not part of any shortest path between two vertices in V \ X. Hence, G[V \ X] is a solution for the hypergraph obtained from H by removing each vertex in X. In particular, for each F ∈ F containing t i , vertex t i is connected to all other vertices in G[F \ X]. Therefore, adding each vertex in X as a degree-one neighbor to t i (which results in the graph G ′ ) produces a solution for H.

The above shows the correctness of the first modification step. After this step we update the set T by performing the modification step, again for some arbitrary twin class of H that contains at least two vertices with degree-one neighbors in G ′ . We repeat this process until T is empty. In order to show that we can obtain a solution G * in which T is empty, we need to show that we only have to perform a finite number of modification steps. To this end, note that in each step the degree of the labeled vertex t i ∈ T i increases and only the degree of t ′ decreases. Since t ′ is a twin of t i , the degree of all other labeled vertices stays the same. Hence the number of modification steps is finite. Summarizing, there is a solution that fulfills Property 1 of the lemma.

We now show that such a solution can be further modified such that it also fulfills Property 2. Let G be a solution that fulfills Property 1 and let T = {T 1 , . . . , T q } denote the twin classes for which there are at least two degree-two vertices in G. For each T i do the following. Since the first property is satisfied, T i contains at least one degree-two vertex u such that its two neighbors a and b have degree at least two, respectively. Then, remove the two edges incident with u, make a and b adjacent, and make u adjacent to either the one vertex in T i that has degree-one neighbors, or, if such a vertex does not exist, another degree-two vertex in T i . See Figure 4 for an illustration of this modification step. Note that the neighbors of t i and u do not have to be contained in Note that since neither a nor b are degree-one vertices and by the choice of v, the above modification does not result in a solution in which a twin class has more than one vertex that is a neighbor of degree-one vertices. Consequently, the modification can be applied to all T i 's without losing the first property. Hence, there is a solution fulfilling both properties.

With the above lemma at hand, we can show the correctness of Rule 6. The proof idea is as follows. Using Lemma 4.2, we show that only O(2 m ) vertices of every twin class T have degree at least three but at least one low-degree neighbor. Consequently, for sufficiently large |T | we can assume that one vertex of T has degree one in G: Otherwise, there are many degree-(≥ 3) vertices in G that have only degree-(≥ 3) neighbors in G. This, however, pushes the number of edges in G above the guarantee given by Rule 5.

Lemma 4.3. Rule 6 is correct. Proof. Let (H, k) denote the original instance and (H ′ , k -1) an instance resulting from one application of Rule 6. We show that both instances are equivalent. It is easy to see that if (H ′ , k -1) is a yes-instance, then (H, k) is also a yes-instance: Let G ′ be the solution for H ′ . Pick one vertex u ∈ T \ {v}, make v adjacent to u, and call the resulting graph G. Then, G has one more edge than G ′ . Moreover, G is also a solution since for each

F ∈ F containing v, the subgraph G ′ [F \ {v}] is connected. This implies that G[F ] is also connected (since F \ {v} contains u).
For the other direction of the equivalence, suppose that G is a solution for H. Since H is reduced with respect to Rule 5, graph G has k < 2 m 2 + n edges. Let twin class T and vertex v be as described in Rule 6. To show that (H ′ , k -1) is also a yes-instance, we show that, since |T | > 4 m + 7 • 2 m + 1, hypergraph H has also a solution with k edges where vertex v has degree one. Herein, we assume that H and thus also G are connected. The case for disconnected input hypergraphs follows easily.

First, we show that there are at most 4 m + 7 • 2 m vertices whose degree in G is at least three. Obviously, this upper-bounds the number of vertices with degree at least three in the twin class T as well. We consider two subsets of this vertex set: by X we denote the vertices of degree at least three that have only neighbors of degree at least three in G, and by Y we denote the other vertices of degree at least three. Note that Lemma 4.2 implies that Y has at most (1 + 2) • 2 m = 3 • 2 m vertices: First, the number of twin classes is at most 2 m . Second, in G each twin class has at most one vertex that has degree-one neighbors. Finally, in G each twin class has at most one degree-two vertex. Hence, there are at most 2 • 2 m neighbors of degree-two vertices.

It remains to upper-bound the size of X. We do this by deriving a lower bound on the number of edges in G and then show that, for large X, this lower bound exceeds k, contradicting the fact that (H, k) is a yes-instance. To this end, let Z = V \ (X ∪ Y ) denote the set of vertices that have degree one or two in G. We partition the edges of G into two subsets E X∪Y , which contains edges with both endpoints on vertices of degree at least three, and E Y ∪Z which contains all other edges. Since we assume that G is connected, |E Y ∪Z | ≥ |Z| -1. The number of edges in E X∪Y is at least 3|X|/2 since all vertices in X have degree at least three and only neighbors in

X ∪ Y . If |X| ≥ 2 • 2 m 2 + 3 • 2 m , then |E X∪Y | ≥ 3|X| 2 = |X| + |X| 2 ≥ |X| + |Y | + 2 m 2 ,
where the last inequality holds because |Y | ≤ 3 • 2 m . Hence, the number of edges in G is

|E X∪Y | + |E Y ∪Z | ≥ |X| + |Y | + 2 m 2 + |Z| -1 = n + 2 m 2 -1.
This contradicts the assumption that (H, k) is a yes-instance, since k < n + 2 m 2 -1 after application of Rule 5. Hence, we have

|X| < 2 • ( 2 m 2 + 3 • 2 m ) = 4 m + 5 • 2 m
. Now we can upper-bound the number of vertices in the twin class T that have degree at least two. In addition to the vertices of X, class T can contain at most one vertex that is a neighbor of degree-one vertices, at most 2 • 2 m vertices that are neighbors of degree-two vertices, and at most one degree-two vertex. Therefore, if T contains more than 4 m + 7 • 2 m + 1 vertices, then at least one of them is a degree-one vertex in G. Without loss of generality, we can assume that this is v. The running time of the kernelization algorithm can be upper-bounded as follows. Clearly, Rule 5 runs in O(|H|) time. In order to apply Rule 6, we first compute a partition of V into the twin classes. This can be done as follows. We start with one set containing V and then consider an arbitrary hyperedge F ∈ F . The vertices that are in F are in a different twin class than the vertices that are not in F . Hence, using F we partition V into two subsets. We repeat the partitioning for all hyperedges, each time using the current hyperedge to update the partition. The partitioning can be done in O(|F |) time [START_REF] Habib | Partition refinement techniques: An interesting algorithmic tool kit[END_REF]Lemma 1]. This process thus takes O(|H|) time. Its output is a partition of V into all different twin classes. For each twin class, we check whether Rule 6 can be applied. Instead of applying the rule right away, we label the vertices of the twin classes that will be removed and decrease k by the overall number of labeled vertices. After all twin classes have been processed, we remove all labeled vertices from each F ∈ F , again in linear time. Thus, the overall running time is O(|H|). (c+1)8 m ≤ (c 2 8 2m ) (c+1)8 m = 2 O(m8 m ) such sets, we get the 2 O(m8 m ) bound for the running time of this part of the algorithm.

Data Reduction Rules for Sparse Solutions.

In this section, we present a set of reduction rules that identify and remove parts of the instance which either produce tree-like induced subgraphs or long induced paths in the solution. We analyze the power of these data reduction rules by showing that, for maximum hyperedge size d ≤ 4, they yield a problem kernel for the parameter feedback edge number φ and that, for general d, they can be used to obtain fixed-parameter tractability for the combined parameter (d, φ). The reason for obtaining a weaker result for d > 4 is that Rule 1 is indeed correct if d ≤ 4 but not in general (see Rule 4). Applying this rule removes a certain class of vertices from the input graph that seem to be hard to identify for d > 4.

Although k appears in our data reduction rules, they are applicable regardless of the value of k. Hence, the data reduction rules can be applied also to the optimization version of SID. instance with d ≤ 4 in O(n • m 3 ) time by using Rule 4 (Section 3) and an additional reduction rule (Rule 7 below). Informally, the parameter φ upper-bounds the number of vertices that are in cycles and have degree at least three. Using Rule 4 we can remove vertices that have degree one in solutions. Hence, to reduce the overall number of vertices to O(φ), we also have to remove vertices that are in long induced paths in the solution. This is the purpose of Rule 7. This rule is also needed in Section 5.2 which deals with the case d ≥ 5. Therefore, we formulate the rule in a more general way than needed for the special case d ≤ 4.

A Problem

Rule 7. Let (H = (V, F ), k) be an instance of SID. If H contains a vertex set P := {p 0 , . . . , p 2d } with incident hyperedge set F P := p∈P F (p) such that 1. no p i ∈ P covers any p j ∈ P with j = i, 2. for each F ∈ F P we have F ∩ P = {p i , . . . , p j } for some 0 ≤ i ≤ j ≤ 2d, 3. for each F ∈ F P with F ∩ {p 0 , p 2d } = ∅, and for every vertex v ∈ F \ P , there is a vertex p ∈ P that covers v, and 4. there is no hyperedge F ∈ F P such that F ∩ P = {p i } for any 0 < i < 2d, then do the following.

For every F ∈ F P with F ∩{p 0 , p 2d } = ∅, remove all vertices in F \ P from H and decrease k by their number. Furthermore, remove the vertices p 2 , . . . , p 2d-2 from H and decrease k by 2d -2.

Intuitively, Conditions 1 and 2 plus the fact that the hyperedges have size at most d enforce that there is a solution G for such a hypergraph that makes G[P ] a long induced path with endpoints p 0 and p 2d . Below, we use P I := {p 1 , . . . , p 2d-1 } to denote the set of inner vertices of this path structure. Condition 3 ensures that in the solution in which G[P ] is a path all vertices that are in hyperedges with only vertices of P I can be made degree-one neighbors of some vertex of P I .

Two examples of hypergraphs to which Rule 7 applies are shown in Figure 5 with values d = 3 and d = 6, respectively.

In order to prove the correctness and running time of the rule, we first make some observations on the structure of the subhypergraph that consists of the hyperedge set F P . The first observation is about the structure of the hyperedges along the presumed path containing P .

Observation 2. Let H be a hypergraph and P ⊆ V satisfying the conditions of Rule 7. For every p i ∈ P I there is a hyperedge F + i such that p i-1 / ∈ F + i and {p i , p i+1 } ⊆ F + i and also a hyperedge F - i such that {p i-1 , p i } ⊆ F - i and p i+1 / ∈ F - i . Moreover, there is a hyperedge F - 0 such that F - 0 ∩ P = {p 0 } and a hyperedge F + 2d such that F + 2d ∩ P = {p 2d }.

Proof. Consider some i ∈ {1, . . . , 2d -1}. By Condition 1 of Rule 7, there is some hyperedge containing p i but not p i-1 . Now, by Condition 4, this hyperedge contains at least one further vertex from P , and by Condition 2 it thus contains p i+1 . Hence, there is a hyperedge F + i containing p i and p i+1 that does not contain p i-1 . The existence of F - i follows from a symmetric argument. Finally, Condition 1 implies the existence of F - 0 and F + 2d . For the second observation we consider the hyperedges that only intersect with the set of inner vertices P I . To this end, let F I = {F ∈ F P | F ∩ P ⊆ P I } be the hyperedges of F P that contain neither p 0 nor p 2d and let W := F ∈FI F be the union of all vertices that are incident with some hyperedge in F I . Due to Observation 2, F I is not empty and W ∩ P = P \ {p 0 , p 2d }. Each vertex v in W \ P is covered by some vertex of P \ {p 0 , p 2d }: By the definition of W , there is a hyperedge F ∈ F I with F ∩ {p 0 , p 2d } = ∅ that is incident with v. By Condition 3, v is covered by some p i ∈ P . Since F ∩ {p 0 , p 2d } = ∅, we have p i = p 0 and p i = p 2d . Altogether, W thus has the following property.

Observation 3. For each v ∈ W either v ∈ P I or there is a p i ∈ P I such that p i covers v.

Informally, the above two observations imply that the subhypergraph H[W ] has a solution in which P I is an induced path and all other vertices of W have degree one. The final observation is used to show that this solution for H[W ] is also optimal. It is based on the fact that any solution for a connected input hypergraph is a connected graph.

Observation 4. Let H = (V, F ) be a hypergraph and let G be a solution for H.

If the subhypergraph H[V ′ ] induced by a vertex subset V ′ ⊆ V is connected, then |E(G[V ′ ])| ≥ |V ′ | -1.
Using these observations, we can now show the correctness of the rule. Lemma 5.1. Rule 7 is correct. Proof. Let H, P and F P be as described in Rule 7 and, as above, let P I = {p 1 , . . . , p 2d-1 }, F I = {F ∈ F P | F ∩ P ⊆ P I } and W = F ∈FI F . Consider an arbitrary optimal solution G ′ and let G be the graph obtained from G ′ by removing all edges in G ′ [W ] and then adding the edges {p i , p i+1 } for i ∈ {1, . . . , 2d -2}, and, for every v ∈ W \ P adding one edge {v, p i } where p i covers v. We prove that G is an optimal solution.

First, we show that G is a solution, that is, G[F ] is connected for all F ∈ F . For this, let F ∈ F and

F W = F ∩ W . Observe that if |F W | < 2, then G[F ] is connected. Hence, assume |F W | ≥ 2 and let u, v ∈ F W such that {u, v} ∈ E(G ′ ). We show that u and v are connected in G[F W ]. This directly implies that G[F ] is connected, since any path in G ′ [F ]
using {u, v} can then use the path between u and v in G[F W ] instead. By Observation 3, we have F W ∩ P ⊇ {p i , p j } for some 1 ≤ i ≤ j ≤ 2d -1, and Condition 2 yields F W ∩ P ⊇ {p i , p i+1 , . . . , p j }. Without loss of generality, we may assume that either u = p i or {u, p i } ∈ E(G). Similarly, we may assume that either v = p j or {v, p j } ∈ E(G). Hence, it suffices to show that G[{p i , . . . , p j }] is connected. This is directly implied by the construction of G. Thus, there is a path between u and v and G is a solution.

We now prove the optimality of G. For this, we first show that the induced subhypergraph H[W ] = (W, F I ) is connected, which implies a lower bound on the number of edges in G ′ [W ]. Let u, v ∈ W . We construct a hyperwalk between u and v using only hyperedges of F I . By Observation 3, it suffices to show that there is a hyperwalk between any p i , p i+1 , 1 ≤ i ≤ 2d -2. Assume without loss of generality that i ≤ d. By Observation 2 there is some hyperedge F ∈ F with p i , p i+1 ∈ F and p We have thus shown that there is an optimal solution G where each vertex v ∈ W \ P is adjacent to a vertex in P that covers v. Combining this with Rule 2 we conclude that removing any vertex in W \ P from the hypergraph and decreasing k by one results in an equivalent instance. Hence, in the following we assume that W ⊆ P , and hence W = {p 1 , . . . , p 2d-1 }. It remains to show that the remaining modifications for p 2 , . . . , p 2d-2 are correct.

Let (H, k) be the original instance and (H ′ , k ′ ) the instance resulting from an application of Rule 7 to (H, k). Note that k ′ = k -2d + 2 since we assume that the vertex set W = {p 1 , . . . , p 2d-1 } and after the application of Rule 7, only the vertices p i with 2 ≤ i ≤ 2d -2 are removed. Let P * denote the set of the removed vertices. We prove that the instances are equivalent.

First, let G be a solution with at most k edges for H as constructed in the first part of the proof. We show that we can obtain a solution for H ′ with at most k ′ edges from G. Consider a hyperedge F ∈ F such that G[F \ P * ] is disconnected. Clearly, F ∩P * = ∅ and F \P * = ∅. Because of Condition 2 and |F | ≤ d, the set F \P * then contains exactly one of p 1 and p 2d-1 . Without loss of generality, let p 1 ∈ F . Remove each edge {v, p i } in G[F ] with i ∈ {2, . . . , d} and add {v, p 1 }. Let G * be the graph obtained by iterating the replacements as long as possible. We obtain a solution for H ′ by taking G * [V \ P * ]: We have that G * [F \ P * ] is connected because any path in G[F ] between two vertices in F \ P * that used {v, p i } can now use {v, p 1 } instead. Since 2d -2 edges are incident with P * in G * , it follows that G * [V \ P * ] has at most k ′ edges. Hence, if (H, k) is a yes-instance, then also (H ′ , k ′ ) is a yes-instance.

For the converse, let G ′ be an optimal solution for H ′ with at most k ′ edges. We claim that adding the edges {p i , p i+1 } for i ∈ {1, . . . , 2d -2} yields a solution G for H. Clearly, it suffices to consider hyperedges F that intersect

P * . Condition 2 implies that G[F ∩ P * ] is connected. Hence, if F ⊆ P * , then G[F ] is connected. Otherwise, G ′ [F \P * ] is connected since G ′ is a solution. By Condition 2, either p 1 ∈ F or p 2d-1 ∈ F . Since F ∩P * is connected to p 1 or to p 2d-1 in G, this implies that G[F ] is connected.
Note that G contains at most k edges since it contains exactly 2d-2 edges more than G ′ . Hence, if (H ′ , k ′ ) is a yes-instance, then also (H, k) is a yes-instance and the rule is correct.

We now show the running time of Rule 7. Lemma 5.2. It is possible to apply Rule 7 or to decide that it does not apply to the hypergraph in O(m 3 d 3 ) time.

Proof. First, recall Observation 2. In order to find an application of Rule 7 we will consecutively find hyperedges that correspond to the definitions of F - i and F + i . The algorithm is as follows.

We start by building the covering graph of H. Then, we construct an auxiliary hypergraph H * = (V * , F * ) as follows: Start with the hypergraph H and while there is a vertex in the covering graph that has an incoming arc, remove this vertex from H. Note that V * does not contain any pair of vertices u and v such that u covers v. The running time for constructing H * is dominated by the O(n

• |H|) = O(m 2 • d 2 ) time
needed for constructing the covering graph.

Intuitively, we successively discover the vertices in p 1 , . . . , p 2d-1 from Rule 7 that are contained in the F - i and F + i , giving rise to successively new hyperedges F - i , F + i . By considering only V * , the F - i and F + i form a very regular structure, and when p i is fixed, then there is little choice for p i+1 . Hence, we can basically guess p 1 and greedily determine the successive p i , i > 1, until either sufficiently many are found, or there are no choices left. Subsequently, we make this approach more formal.

We guess, trying all possibilities, which of the sets F in F * is the set F + 1 ∩ V * . Let us assume that our guess was correct. We then check for vertices v having the following property:

Property (a): there is a hyperedge F ′ ∈ F * such that F ∩ F ′ = {v}. Discard the guess of F if there are more than two or less than two vertices with Property (a). Otherwise, for both choices to denote one of these vertices by p 1 , proceed as follows.

Set i := 1 and repeat the following as long as F \ {p 1 , . . . , p i } = ∅. Check whether there are vertices v in F \ {p 1 , . . . , p i } with Property (b): there is a hyperedge F ′ ∈ F * such that F ′ contains v and p i , and F ′ ∩ F ⊆ {p 1 , . . . , p i , v}. If there is exactly one vertex v in F \ {p 1 , . . . , p i } with Property (b), then denote this vertex p i+1 and set i := i + 1. Otherwise discard the guess of p 1 . Now, set i = |F | and repeat the following as long as i < 2d -1. Check for each vertex v in V * \ {p 1 , . . . , p i } whether it has Property (c): there is a hyperedge

F ′ ∈ F * such that F ′ con- tains v, F ′ ∩ {p 1 , . . . , p i } = {p i } and for every u ∈ F ′ \ {v, p i },
and every hyperedge F ′′ ∈ F * containing u and p i we have that F ′′ contains v. If there is exactly one vertex with Property (c), then denote this vertex v as p i+1 and set i := i + 1. Otherwise discard the guess of p 1 .

Finally, let

L = {F ′ ∈ F * | F ′ ⊆ {p 1 , . . . , p 2d-1 } ∧ (p 1 ∈ F ′ )} \ {p 1 , . . . , p 2d-1 } and similarly R = {F ′ ∈ F * | F ′ ⊆ {p 1 , . . . , p 2d-1 } ∧(p 2d-1 ∈ F ′ )} \ {p 1 , . . . , p 2d-1 }.
Let p 0 be an arbitrary vertex in L and p 2d an arbitrary vertex in R. We now check whether p 0 , . . . , p 2d satisfies the conditions of Rule 7 in the original input hypergraph H. We claim that if there is an application of Rule 7, then the above algorithm finds it.

Denote the vertices in P in the application of the rule by p ′ 0 , . . . , p ′ 2d . Let F + i and F - i be as in Observation 2 and denote

F ′ + i = F + i ∩ V * and F ′ - i = F - i ∩ V * , respectively. If p ′ 0 , . . . , p ′
2d satisfies the assumptions of Rule 7 and Next, for i ∈ {|F |, . . . , 2d -2}, p ′ i+1 has Property (c), and for any other vertex taking u = p ′ i+1 (which must be contained in any F ′ ) and F ′′ = F ′ - i+1 shows that it does not have Property (c). Finally, it remains to note that every hyperedge which contains p ′ 1 = p 1 and p ′ 0 also contains the whole set L and, in particular, p 0 (similarly, R contains p 2d ). Hence, also p 0 , p ′

F (u) = F (p ′ i ), then also p ′ 0 , . . . , p ′ i-1 , u, p ′ i+1 , . . . , p ′ 2d satisfies
(2d + 1) • m 2 • d 2 + m • d 2 )) = O(m 3 d 3 ).
The description of Rule 7 is quite technical and therefore it seems difficult to obtain an efficient implementation of the rule. This impression is reinforced by the large, although polynomial, running time bound for applying the rule. Nevertheless, it should be possible to apply Rule 7 efficiently. First, the algorithm given above and its analysis is rather simplistic. More sophisticated approaches should yield improvements to the theoretical bounds. Since algorithm engineering is not the main focus of this article and for the sake of clarity, we opted to describe a simple version of the algorithm instead. Second, using a few tricks in searching for hyperedges and vertices that satisfy the desired properties should yield a considerable speed-up in practice. For example, to test for Property (b), it suffices to consider hyperedges F ′ that are incident with the vertices p i-d , . . . , p i . Also further properties of the hypergraphs at hand could be taken into account. For example, in some instances of the overlay network application, most of the subscribers consume less than five feeds [START_REF] Liu | Client behavior and feed characteristics of RSS, a publish-subscribe system for web micronews[END_REF], meaning that the vertices corresponding to the subscribers are contained in at most five hyperedges. For these vertices, testing for Property (b) is then possible in O(d 2 ) time.

We now derive an upper bound on the number of vertices in instances that are reduced with respect to Rule 4 and Rule 7. As Rule 4 reduces all vertices that have degree one in any solution, the upper bound on the overall number of vertices will be obtained by bounding the number of vertices with degree at least two in the solution. As mentioned above, we will use Rule 7 in Section 5.2, where we also need to bound the number of vertices with degree at least two. Hence we use the following notation. Definition 5.3 ([27]). The 2-core of a graph G is the uniquely defined induced subgraph of G that has the maximum number of vertices such that each vertex has degree at least two.

The application of Rule 7 alone does not necessarily yield a bounded-size 2-core in a solution. Instead, the application of Rule 4 for d ≤ 4 (and of a different rule for d ≥ 5) "prepares the hypergraph" such that application of Rule 7 yields a size bound on the 2-core of an optimal solution G. We define the notion of being prepared as follows.

Definition 5.4. We say that a hypergraph H = (V, F ) is cleared if there is an optimal solution G for H such that each vertex of degree at least two is in the 2-core of G and, furthermore, for each P := {p 0 , . . . , p 2d } with P ⊆ V and F ′ := p∈P F (p) that satisfy Conditions 1, 2, and 3 of Rule 7, it holds that H and P also satisfy Condition 4.

The intuition behind the definition is as follows. The first part of the definition guarantees that the solution for a cleared hypergraph consists of the 2-core plus possibly some degree-one vertices attached to this 2-core. The second part of the definition guarantees that any hypergraph with long paths in the 2-core of its solution can be reduced further by applying Rule 7.

For d ≤ 4 it is sufficient to apply Rule 4 in order to clear a hypergraph. Lemma 5.5. Let H = (V, F ) be a hypergraph with d ≤ 4 that is reduced with respect to Rule 4. Then, H is cleared.

Proof. The reducedness of H directly implies that there is a solution without any degree-one vertices, hence, the first property of being cleared is satisfied. For the second property, consider P and F as in Rule 7 and assume that there is a hyperedge F ∈ F such that F ∩ P = {p i } for some 1 < i < 2d. Then, by Condition 3 we have F (p i ) ⊇ F (u) for each u ∈ F \ P and, hence, Rule 4 applies, a contradiction.

We now bound the size of reduced instances. We also use this bound in Section 5.2 and, hence, prove it in a slightly more general form than needed for d ≤ 4.

Lemma 5.6. Let (H, k) be a yes-instance of SID such that H is connected, cleared, and reduced with respect to Rule 7. Then, there is a solution G = (V, E) for (H, k) such that the 2-core of G has at most max{(9d-1)(φ-1), (3d-1)φ} vertices and, hence, at most 9d • φ edges.

Proof. Among all optimal solutions G for (H, k) such that each vertex of degree at least two is in the 2-core of G, choose G such that it contains the maximum number of degree-one vertices. Now consider the 2-core G ′ of G. Note that G and G ′ have the same feedback edge number φ. We show a bound on the number of vertices in G ′ which then gives a bound on the number of edges in G ′ .

Let V ≥3 denote the vertices with degree at least three in G ′ and V 2 the degreetwo vertices in G ′ . We first bound the number of components in G ′ [V 2 ]. If V ≥3 = ∅, then, clearly, we have at most one component. Otherwise, consider the graph G * with loops and parallel edges obtained from G ′ by replacing each maximal path with inner vertices in V 2 by a single edge. The number of edges in G * is an upper bound on the number of components in G

′ [V 2 ]. The number of edges in G * is |V ≥3 | -1 + φ = v∈V ≥3 deg G (v)/2 ≥ 3|V ≥3 |/2.
The above relation implies that |V ≥3 | ≤ 2φ -2. Thus, the number of edges in G * and the number of components in G ′ [V 2 ] is at most max{1, 3φ -3}.

We now show that each connected component of G ′ [V 2 ] contains fewer than 3d vertices. Consider a connected component C of G ′ [V 2 ] with c+1 ≥ 3d vertices. Since C is a path, its vertices admit an ordering p 0 , p 1 , . . . , p c with {p i , p j } ∈ E ⇐⇒ j = i + 1 for all 0 ≤ i ≤ j ≤ c. Let P := {p 0 , p 1 , . . . , p 2d } and let F ′ := p∈P F (p). We show that Rule 7 applies to H, contradicting its reducedness.

First, assume that Condition 2 of Rule 7 does not hold for some F ∈ F ′ . That is, there are 0 ≤ i < j < ℓ ≤ 2d such that p i , p ℓ ∈ F and p

j / ∈ F . Since c + 1 ≥ |P | + d, a shortest p i -p ℓ -path in G -{p j } contains at least d + 1 > |F | vertices. Thus, G[F ] is not connected, contradicting G being a solution for (H, k). Hence, Condition 2 of Rule 7 is satisfied.
Now, Condition 1 of Rule 7 can be seen as follows. Assume that there is a pair p i , p j , i < j, of vertices in C such that p j covers p i . By the above, all hyperedges that contain p i and p j also contain {p i+1 , . . . , p j-1 }. Hence, p i+1 also covers p i . Since p i and p i+1 are adjacent in G, this implies that a new solution can be obtained by making all neighbors (except p i+1 ) of p i adjacent to p i+1 instead. The new graph is also a solution, and has one additional degree-one vertex. This contradicts our choice of G. Hence, Condition 1 of Rule 7 holds.

Let F ∈ F with F ∩ {p 0 , p 2d } = ∅ and note that G[F ] is connected. Since H is cleared, and since there is some p j ∈ F ∩ P , we know that G[F ] consists entirely of vertices in P plus some degree-one vertices. Each degree-one vertex v is covered by its neighbor p ∈ P in G. Thus Condition 3 of Rule 7 holds.

Finally, Condition 4 of Rule 7 follows since H is cleared. Thus, Rule 7 applies, a contradiction.

By the above, each connected component in G ′ -V ≥3 has less than 3d vertices. Hence, |V 2 | ≤ (3d -1) max{3φ -3, 1}. Altogether, this implies

|V 2 | + |V ≥3 | ≤ (3d -1) max{3φ -3, 1} + 2φ -2 = max{(9d -1)(φ -1), (3d -1)φ}.
By definition of φ this means that the 2-core of G has at most 9d • φ edges.

For d ≤ 4, after applying Rule 4 the size bound on the 2-core immediately gives a bound on the overall instance size.

Theorem 5.7. An instance of Subset Interconnection Design with maximum hyperedge size d ≤ 4 can be reduced to an equivalent one with at most max{35(φ-1), 11φ} vertices in O(n • m 3 ) time.

Proof. The kernelization algorithm exhaustively applies Rule 4 and Rule 7. Reducedness with respect to Rule 4 ensures that there are no degree-one vertices in any optimal solution and, by Lemma 5.5, that the hypergraph is cleared. Consequently, being reduced with respect to Rule 7 implies that any solution contains at most max{(9d -1)(φ -1), (3d -1)φ} vertices of degree at least two. Altogether this implies the bound on the number of vertices.

For the running time, we apply Rule 4 exhaustively, then apply Rule 7 exhaustively, and repeat until neither applies anymore. Since each application of one of the rules deletes at least one vertex, we iterate at most n times. Applying the running time bounds given by Lemmata 3.4 and 5.2 we obtain the overall running time bound.

5.2.

A Fixed-Parameter Algorithm for φ and d. Our polynomial-time data reduction in the last section does not generalize to arbitrary d. The reason is that the condition |F | ≤ 4 is necessary for the correctness of Rule 4 or, equivalently, that Rule 1 is incorrect if d > 5. However, using an additional reduction rule (Rule 8 below), we obtain the same vertex-bound on the 2-core of a solution. However, many degreeone vertices may still remain and it seems unclear how to remove them for d ≥ 5. Nevertheless, using the fact that the 2-core of a solution has bounded size we obtain a branching algorithm with running time O

(d 18dφ • d • n • m + n • m 3 • d 2 )
. The algorithm first applies Rule 7 and Rule 8 to simplify the structure of the solution that we are looking for. Then, we apply a branching rule that branches into O(d 2 ) cases and finds at least one of the edges in the 2-core of a solution. If the branching rule does not apply, then an optimal solution can be found in polynomial time.

First, to obtain the bound on the 2-core, we replace Rule 4 with Rule 8 to clear the input hypergraph and to make Lemma 5.6 applicable.

Rule 8. Let H = (V, F ) be a hypergraph, F ∈ F , and F = {u, u 1 , . . . , u ℓ } such that u covers each u i . Then, remove the vertices u 1 , . . . , u ℓ from H and decrease k by ℓ. Proof. We first show the correctness of the rule. We show that there is an optimal solution G such that G[F ] is a star with center vertex u. Let G ′ be any optimal solution for H and assume that there are two adjacent vertices in F none of which is u. Note that we may choose two such adjacent vertices u i , u j such that {u, u j } ⊆ N G ′ (u i ); this is possible because otherwise G ′ [F ] is not connected. Remove the edge {u i , u j } from G ′ and add {u, u j } to obtain G. We prove that the graph G is a solution.

Consider any hyperedge F ′ ∈ F and any path P ′ between two vertices in G ′ [F ′ ]. If P ′ contains the edge {u i , u j }, then we may replace it by {u i , u}, {u, u j } to obtain the walk P in G. Since u covers both u i and u j the path P is contained in G[F ′ ]. Thus, G[F ′ ] is connected for each F ′ ∈ F meaning that G is an optimal solution. By repeating the replacement of edges described above, we may arrange that G[F ] is a star. Now, note that Rule 8 is basically a series of applications of Rule 2. Clearly, Rule 2 applies to u 1 , so one can safely remove u 1 and set k := k -1. Afterwards, Rule 2 still applies to u 2 , so one can remove u 2 and decrease k once more. This can be repeated until all u i 's are removed from H.

The running time of the rule can be seen as follows. First, we construct the covering graph G C for H in O(n • m • d) time using Lemma 2.1. Then, for each hyperedge F ∈ F we check whether there is a vertex u such that there are arcs (u, v) in G C for every v ∈ F \ {u}. If so, then we remove each vertex in F \ {u}. This costs O(m • d 2 ) time. It is easy to check that this procedure finds an application of Rule 8 if there is one.

For d ≥ 5, we can now use Rule 8 to clear hypergraphs. Lemma 5.9. Let H = (V, F ) be a hypergraph that is reduced with respect to Rule 8. Then, H is cleared.

Proof. We first prove the first statement of being cleared, namely, that there is an optimal solution G for H such that each vertex not in the 2-core of G has degree one. We use the notion of "pending trees". Let G be a graph. If G[V ′ ] is the 2-core of G, then a pending tree of G is a connected component of G[V \ V ′ ] plus its unique neighbor in V ′ .

Pick an optimal solution G and consider its pending trees and their vertex sets C 1 , . . . , C c . For each pending tree C i there is a unique vertex x both in C i and in the 2-core of G. Denote x =: root(C i ). If the 2-core of G is empty, then there is only one pending tree C 1 and we choose root(C 1 ) to be an arbitrary vertex of degree one instead. Next, consider optimal solutions that contain the maximum number of degree-one vertices. Among these optimal solutions, choose G such that val(G) :=

c i=1 v∈Ci deg G (v)=1 dist(root(C i ), v)
is minimum, where dist(u, v) is the length of a shortest path between u and v in G.

Assume now that there is a pending tree with vertex set C ⊆ V such that G[C] contains at least one vertex with degree at least two in G[C]. Choose u ∈ C with degree at least two such that a shortest path between u and root(C) has maximum length. Consider the neighbors of u in G. Let v be the neighbor of u on the shortest path from u to root(C). All the neighbors of u different from v must be of degree one due to the choice of u according to the maximum length path to root(C). Let us call them u 1 , . . . , u ℓ . By Observation 1, F (u) ⊇ F (u i ) for all i ∈ {1, . . . , ℓ}. Consider some u i . Since H is reduced with respect to Rule 8, there is no subset U of the degree-one neighbors of u and no hyperedge F ∈ F such that F = U ∪ {u, u i }. Hence, each hyperedge incident with u i also contains some vertex other than u and its degree-one neighbors. We conclude that each hyperedge F ∈ F that contains u i also contains v since, otherwise G[F ] is not connected. Thus, the graph G ′ obtained from G by removing the edge {u i , u} and adding the edge {u i , v} is an optimal solution. However, the distance of u i to root(C) is smaller in G ′ than in G. Hence, either u i is from our data reduction rules seems foremost of theoretical interest. In practice, it seems unlikely that the data reduction rules apply often because of the large twin classes they require which are of size exponential in m. An interesting task for future research is thus to improve the bounds on the twin classes. However, we conjecture that an upper bound polynomial in m on the size of the whole remaining instance, that is, a polynomial-size problem kernel, cannot be achieved.

Of more practical value seem to be Rule 7 as well as Rules 2 to 4, 6, and 8 which repair the incorrect Rule 1 from the literature [START_REF] Fan | Algorithms and implementation for interconnection graph problem[END_REF][START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF]. Indeed, a case study of when Rule 1 applies, but none of the repaired rules do, would be useful and could lead to further relevant data reduction rules.

We showed that finding tree-like solutions in hypergraphs with small hyperedges is tractable. Here, algorithm engineering is needed to improve the running times and to merge our reduction rules with existing solution strategies. On the theoretical side, we did not resolve yet whether Subset Interconnection Design is fixed-parameter tractable with respect to the feedback edge number φ of the solution alone. A possible line of attack would be to first find out whether, in our results, we can replace the parameter d (maximum hyperedge size) by the smaller parameter "maximum overlap number", that is, the maximum size of an intersection between any two input hyperedges. It would also be interesting to significantly improve on the straightforward exponential upper bound 2 O(n 2 ) when solving Subset Interconnection Design parameterized by the number n of vertices.

More generally, it seems also promising to consider data reduction for variants of Subset Interconnection Design that ask to minimize the maximum degree instead of the average degree (see Onus and Richa [START_REF] Onus | Minimum maximum-degree publish-subscribe overlay network design[END_REF]), and the various variants occurring in hypergraph drawing [START_REF] Brandes | Blocks of hypergraphs -Applied to hypergraphs and outerplanarity[END_REF][START_REF] Brandes | Path-based supports for hypergraphs[END_REF][START_REF] Johnson | Hypergraph planarity and the complexity of drawing Venn diagrams[END_REF][START_REF] Kaufmann | Subdivision drawings of hypergraphs[END_REF]. It is furthermore of practical interest to deal with edge weights for the constructed network [START_REF] Korach | The clustering matroid and the optimal clustering tree[END_REF]; our methods only cover the unweighted case. Given the numerous applications, an in-depth investigation of all relevant parameters motivated by real-world instances, that is, performing a datadriven parameter analysis for real-world instances, is promising from a practical and from a theoretical side.

Figure 1 :

 1 Figure 1: Two hypergraphs with optimal solutions. Vertices are drawn as white circles, hyperedges by grouping their incident vertices together inside a closed curve filled semi-transparently, and solution edges are drawn as thick lines.

3 vFigure 2 :

 32 Figure 2: An example showing parts of the hypergraph H ′ in the proof of Lemma 3.1, herein x = 3. Left: some hyperedges from H ′ . Right: the 2x edges that can be assumed to be in an optimal solution for H ′ .

Figure 3 :

 3 Figure 3: A hypergraph to which Rule 3 applies.

Figure 4 :

 4 Figure 4: A possible situation before (left) and after the second modification step (right) in the proof of Lemma 4.2. The gray region represents a twin class.

  T i . Nevertheless, for each hyperedge F the connected component of a and b is connected to the one of t i (if it exists) in G[F ], which we now exploit to show the correctness of the modification step. Let G ′ be the modified graph and let v denote the new neighbor of u in G ′ . Clearly, G ′ has the same number of edges as G. To show that G ′ is also a solution, we consider each F ∈ F that contains u and at least one of a and b and show that G ′ [F ] is connected. Case 1: Exactly one of a and b is in F . Then, u has degree one in G[F ], and thus G[F ] -{u} is connected. In particular, the twin v of u has a path to all vertices in G[F ] -{u}. Hence, "reinserting" u and making it adjacent to v results in a connected graph isomorphic to G ′ [F ]. Case 2: Both a and b are in F . Since G[F ] is connected, the graph G ′′ that is obtained from G[F ] by removing u and making a and b adjacent is also connected. Again, this means that the twin v of u (in T i ) has in G ′′ a path to all other vertices. As above, "reinserting" u and making it adjacent to v yields a connected graph isomorphic to G ′ [F ].

  It now only remains to combine the above results to obtain a problem kernel for SID parameterized by the number m of hyperedges. Moreover, this kernel can be computed in linear time, thus yielding linear-time fixed-parameter tractability. Theorem 4.4. An instance of Subset Interconnection Design can be reduced to an equivalent one of size at most O(8 m • m) in O(|H|) time.Proof. The kernelization algorithm first applies Rule 5 and then exhaustively applies Rule 6. After this, the size of each twin class in H is at most O(4 m ). Hence, the instance has size O(8 m •m): The input hypergraph H has at most 2 m twin classes, each containing O(4 m ) vertices. Therefore, the total number n of vertices is O(8 m ). The overall instance size follows.

Corollary 4 . 5 . 2 ≤ c 2 8

 4528 Subset Interconnection Design can be solved in 2 O(m8 m ) + O(|H|) time. Proof. By Theorem 4.4 we can obtain in O(|H|) time an equivalent instance with at most c8 m vertices for some constant c (c can be selected as 2 for m ≥ 3). Hence, by Theorem 4.1, we can assume that k < 2 m 2 +n-1 ≤ 4 m +c8 m ≤ (c+1)8 m . Now we try all subsets of k edges out of the at most c8 m 2m possible edges on at most c8 m vertices. For each of them we test, whether it is a solution in O(mk) = O(m8 m ) time. Since there are at most c 2 8 2m k ≤ c 2 8 2m

  Kernel for the Parameter Feedback Edge Number φ for d ≤ 4. We now describe how we can remove all but O(φ) vertices from a SID

Figure 5 :

 5 Figure 5: Two hypergraphs to which Rule 7 applies along with optimal solutions.

- 1 /

 1 ∈ F for each i ∈ {1, . . . , 2d-1}. Condition 2 states that F ∩P = {p i , . . . , p j } and since |F | ≤ d we have j ≤ i + d -1 < 2d. Hence, F ∈ F I and H[W ] is connected. The fact that hypergraph H[W ] is connected and Observation 4 imply that G ′ [W ] contains at least |W |-1 edges. The graph G[W ] also contains |W |-1 edges. Since W contains all vertices p i for 1 ≤ i ≤ 2d -1, by the construction of graph G ′ , graphs G ′ and G share all edges not contained in G[W ]. Hence, G is optimal.

  the assumptions of Rule 7 and, hence, we can assume p ′ 0 , . . . , p ′ 2d ∈ V * . Consider the branch in which F = F ′ + 1 . The sets F ′ - 1 and F ′ + |F | witness the Property (a) for p ′ 1 and p ′ |F | , respectively, and no other vertex can satisfy Property (a) by Conditions 4 and 2. Hence, we may assume p 1 = p ′ 1 . For each i ∈ {1, . . . , |F | -1}, the set F ′ - i+1 witnesses the Property (b) for p ′ i+1 and no other vertex in F has Property (b).

  1 , . . . , p ′ 2d-1 , p 2d satisfy the assumptions of Rule 7, and the algorithm finds an application. As to the running time, there are |F * | ≤ m possible choices of F , any of the Properties (a)-(c) can be tested for all vertices in O(m 2 • d 2 ) time by first selecting F ′ and F ′′ and then v and u inside them. As successfully testing a condition implies finding one more vertex of p ′ 0 , . . . , p ′ 2d , we test the conditions at most 2d + 1 times in each branch. The sets L and R can be found in O(m•d) time. Finally, the assumptions of Rule 7 for a given sequence p 0 , . . . , p 2d can be tested in O(m • d 2 ) time. Hence the total running time is O(m • (

Lemma 5 . 8 .

 58 Rule 8 is correct and one application takes O(n • m • d) time.

Recall that φ denotes the feedback edge number of an optimal solution G, that is, the minimum number of edges whose removal makes G acyclic.

The theorem of Hosoda et al.[START_REF] Hosoda | On the approximability and hardness of minimum topic connected overlay and its special instances[END_REF] actually states that an optimal solution can be computed in polynomial time if m ≤ f (n) where f is some specific function. This is equivalent to fixed-parameter tractability: if m ≤ f (n), then one can apply the polynomial-time algorithm, otherwise m > f (n) implies that the instance size depends only on m.

Acknowledgments. We thank Peter Damaschke (Chalmers University, Göteborg) for stimulating discussions and for pointing us to the Subset Interconnection Design problem. We are grateful to Falk Hüffner for pointing us to the Minimum Topic-Connected Overlay problem. We also thank the anonymous reviewers of SIDMA for their helpful comments in improving our paper.

† JC was supported by Studienstiftung des Deutschen Volkes. MS and MW were supported by Deutsche Forschungsgemeinschaft, projects DAPA (NI 369/12) and DARE (NI 369/11). OS was partly supported by Deutsche Forschungsgemeinschaft, project AREG (NI 369/9), and by the Czech Science Foundation, project 14-13017P. The main part of the work of OS and MW was done while they were affiliated with TU Berlin.

the only degree-one neighbor of u in G, contradicting the choice of G according to the maximum number of degree-one vertices, or G ′ exhibits a smaller val(G ′ ) contradicting the choice of G according to the minimum val(G). Hence, there are no pending trees C that contain degree-two vertices and the first statement of the cleared-definition now follows.

It remains to prove the implications of the conditions from Rule 7. Let H, P := {p 0 , . . . , p 2d } with P ⊆ V and F ′ := p∈P F (p) satisfy the Conditions 1 to 3 of Rule 7. If there is a hyperedge F ∈ F such that F ∩ P = {p i } for some 0 < i < 2d, then we have F (u) ⊆ F (p i ) for every u ∈ F \ {p i } by Condition 3, and Rule 8 applies to p i , u 1 , . . . , u ℓ , where {p i , u 1 , . . . , u ℓ } = F . Hence, if H is reduced with respect to Rule 8, then Condition 4 is satisfied. Now, Lemma 5.6 is applicable to hypergraphs that are reduced with respect to Rule 8, that is, we can reduce any input instance in polynomial time to one such that there is a solution with at most 9d•φ edges in the 2-core. Based on this fact, we devise a branching algorithm for the parameter (d, φ). This algorithm creates a search tree where at each node of the search tree the current instance consists of a hypergraph H, a partial solution G, and an integer k ′ . The task is to find a solution G ′ such that G ′ is a supergraph of G, all edges of G are within the 2-core of G ′ , and the 2-core of G ′ has at most k ′ edges more than G. In order to obtain a search tree whose size depends only on d and φ, we ensure that the search tree has depth at most 9d • φ and that the algorithm branches into at most d 2 cases in each step. In the following, we assume that G and H are reduced with respect to Rule 8. Branching Rule 1. Let F be a hyperedge of H such that, with F 0 ⊆ F denoting the vertices of F whose degree in G is zero, G[F ] is disconnected and cannot be made connected by, for each u ∈ F 0 , adding an edge between u and some vertex v ∈ F \ F 0 that covers u. Then, branch into all possibilities to add an edge to G[F ], decrementing k ′ by one.

Lemma 5.10. Branching Rule 1 is correct, that is, the original instance is a yes-instance if and only if at least one of the created instances is a yes-instance.

Proof. "⇐": Any solution for a yes-instance created by the branching is also a solution for the original instance.

"⇒": We show that there is an optimal solution G ′ of the original instance such that the 2-core of G ′ contains an edge that is in

Recall that we assume H to be reduced with respect to Rule 8. Hence, H is cleared and we can assume that all edges of G ′ [F ] that are not in the 2-core of G ′ are incident with degree-one vertices in G ′ . Assume towards a contradiction that all edges in G ′ [F ] that are not in G[F ] are not in the 2-core of G ′ . Thus, they are incident with degreeone vertices in G ′ . Hence, all vertices in

v covers u and, thus, the condition of Branching Rule 1 is not satisfied.

Next, we show that, if Branching Rule 1 does not apply, meaning that its preconditions are not fulfilled for any choice of hyperedge F , then we can solve the instance by greedily assigning the remaining vertices.

Lemma 5.11. Let H be a hypergraph and let G be a graph such that there is a solution for H that is a supergraph of G and Branching Rule 1 does not apply to H and G. Then, an optimal solution for H can be computed in O(n

Proof. Let H = (V, F ), let V 0 be the set of degree-zero vertices in G, and let G ′ be obtained from G by adding exactly one edge {u, v} to G for each u ∈ V 0 where v ∈ V \ V 0 is an arbitrary vertex covering u. Note that G ′ can be computed in O(n•d•m) time, by first computing the covering graph of H using Lemma 2.1 and then iterating over each vertex and adding the appropriate edges. We now show that G ′ is an optimal solution.

We first show that for each hyperedge F ∈ F , the graph G ′ [F ] is connected. Let F 0 = F ∩ V 0 for a hyperedge F ∈ F . Since Branching Rule 1 does not apply to the instance, G[F ] can be made connected by adding an edge for each u ∈ F 0 between u and some vertex w ∈ F \ F 0 that covers u. Thus, because each u ∈ F 0 gets at most one incident edge in this way, G[F \ F 0 ] is connected. Since, for each u ∈ F 0 , its neighbor v in G ′ covers u and we know that v ∈ F \ F 0 , also G ′ [F ] is connected.

It remains to show that G ′ is optimal. Note that G ′ has exactly |V 0 | more edges than G. Let G * be any solution that is a supergraph of G. Now merge in G * all vertices in V \ V 0 into one vertex. The resulting graph contains at least |V 0 | edges, since G * is connected. Hence, G * has |V 0 | edges which are incident with vertices from V 0 . Thus, at least |V 0 | edges have to be added to G ′ to obtain a solution.

Combining all of the above, we arrive at the main result of this section. Theorem 5.12. Subset Interconnection Design can be solved in

Proof. Let H = (V, F ) be the input hypergraph. The branching algorithm works as follows. It starts by exhaustively applying Rule 8, then exhaustively applying Rule 7 and repeating until neither applies anymore. Since each application removes at least one vertex the applications of Rule 8 take O(n

time by Lemma 5.2 and the fact that each application removes at least 2d -2 > d vertices. Note that the running time contribution of Rule 7 dominates the one of Rule 8. Now, Lemma 5.9 and Lemma 5.6 imply that there is a solution whose 2-core has at most 9d•φ edges for a yes-instance. Hence, it is correct to initially search for a solution of H that is a supergraph of the edgeless graph on V and has at most k ′ := 9d • φ edges in the 2-core. Then, we apply Branching Rule 1 as often as possible. Each application creates at most d 2 branches, and in each recursive branch the value of k ′ is decreased by one. The correctness of this branching follows by Lemma 5.10. Note that if k ′ < 0, then we can safely abort the search at the current search tree node, since there is no solution satisfying its constraints. Finally, if Branching Rule 1 does not apply, we can compute an optimal solution satisfying the constraints of the search tree node in O(n • d • m) time (by Lemma 5.11).

To check whether Branching Rule 1 applies, we maintain the covering graph throughout the search tree. At each node, we iterate over each edge F , add the edges between vertices in F and arbitrary covering vertices to G, and check whether the result is connected. This needs O(m

Conclusion.

We contributed to a better understanding of a natural NP-hard network construction problem which has been previously studied in many application contexts (also independently from each other and under different names). In doing so, we revealed an incorrectness in previous work, refined the complexity analysis of the problem, and, in particular, provided a thorough investigation concerning its amenability to efficient preprocessing.

The linear-time algorithm for a constant number m of hyperedges that follows Appendix A. A Family of Instances Requiring a Solution with at least 2 Ω(m) + n Edges.

In this section we show that the bound given by Theorem 4.1 and used in Section 4 is optimal in the sense that it cannot be improved to a bound polynomial in m.

To this end, we construct a hypergraph H with m = 2q+1 hyperedges F 1 , . . . , F 2q+1 , where q ≥ 2, such that each vertex is in exactly q hyperedges and each intersection of any q hyperedges consists of exactly one vertex. Therefore we have n = 2q+1 q vertices v 1 , . . . , v n , and each of them can be described by a vector in {0, 1} 2q+1 with exactly q one-entries. Hence, a hyperedge F i consists of those vertices whose vector description has a one-entry in the ith position and q -1 one-entries in the other m positions. This sums up to 2q q-1 . Hence, each hyperedge has exactly 2q q-1 vertices. This completes the construction. Note that any solution for hypergraph H must contain at least 2q q-1 -1 edges if restricted to some hyperedge. Suppose that graph G is a solution for H. If each edge in G is contained in exactly one induced subgraph G[F i ] for some hyperedge F i , then G would need (2q + 1)•( 2q q-1 -1) edges. In fact, each edge {v x , v y } in G can be contained in at most q -1 subgraphs G[F i ], 1 ≤ i ≤ m (these correspond to the positions where both v x and v y have one-entries in their vector representations). Therefore, each solution contains at least k opt ≥ 2q+1 q-1 • 2q q-1 -1 edges. Now we compare this to the number of vertices. We have

q • (2q + 1)! q! • (q + 1)! -(q -1) • (2q + 1)! q! • (q + 1)! -2q + 1 q -1 = 1 q -1 (2q + 1)! q! • (q + 1)! -2q + 1 q -1 = 1 q -1 2q + 1 q -2q + 1 q -1 = 2q + 1 (q -1)(q + 1) 2q q -2q + 1 q -1 ≥ 2q + 1 (q -1)(q + 1)

• 2 2q-1 √ q -5 > 2 2q (q + 1) √ q -5.

The last but one inequality holds due to the Stirling's approximation and q ≥ 2. Thus, k opt ≥ 2 Ω(q) + n = 2 Ω(m) + n.