6:10 Generalized Distance Domination Problems on mim-width

2. For every $1 \le i < j \le k$, construct a node $w_{i,j}$ and two pairs of parallel edges $u_i w_{i,j}$ and $u_j w_{i,j}$.

We then construct the subdivision $H'$ of $H$ by first subdividing each edge $p$ times. We denote the subdivision nodes for 4 edges of $H$ constructed for each pair $1 \le i < j \le k$ in Step 2 by $x_1^{(i,j)}, \dots, x_p^{(i,j)}, y_1^{(i,j)}, \dots, y_p^{(i,j)}, x_1^{(j,i)}, \dots, x_p^{(j,i)}$, and $y_1^{(j,i)}, \dots, y_p^{(j,i)}$. To simplify notation, we assume that $u_i = x_0^{(i,j)} = y_0^{(i,j)}$, $u_j = x_0^{(j,i)} = y_0^{(j,i)}$ and $w_{i,j} = x_{p+1}^{(i,j)} = y_{p+1}^{(i,j)} = x_{p+1}^{(j,i)} = y_{p+1}^{(j,i)}$.

We now construct the $H$-graph $G''$ by defining its $H$-representation $\mathcal{M} = \{M_v\}_{v \in V(G'')}$ where each $M_v$ is a connected subset of $V(H')$. (Recall that $G$ denotes the graph of the MULTICOLORED CLIQUE instance.)

1. For each $i \in [k]$ and $s \in [p]$, construct a vertex $z_s^i$ with model

$$M_{z_s^i} := \bigcup_{j \in [k], j \neq i} \left( \left\{ x_0^{(i,j)}, \dots, x_{s-1}^{(i,j)} \right\} \cup \left\{ y_0^{(i,j)}, \dots, y_{p-s}^{(i,j)} \right\} \right).$$

2. For each edge $v_s^i v_t^j \in E(G)$ for $s, t \in [p]$ and $1 \le i < j \le k$, construct a vertex $r_{s,t}^{(i,j)}$ with:

$$M_{r_{s,t}^{(i,j)}} := \left\{ x_s^{(i,j)}, \dots, x_{p+1}^{(i,j)} \right\} \cup \left\{ y_{p-s+1}^{(i,j)}, \dots, y_{p+1}^{(i,j)} \right\} \\ \cup \left\{ x_t^{(j,i)}, \dots, x_{p+1}^{(j,i)} \right\} \cup \left\{ y_{p-t+1}^{(j,i)}, \dots, y_{p+1}^{(j,i)} \right\}.$$

Throughout the following, for $i \in [k]$ and $1 \le i < j \le k$, respectively, we use the notation

$$Z(i) := \bigcup_{s \in [p]} \{z_s^i\} \quad \text{and} \quad R(i, j) := \bigcup_{s,t \in [p]} \{r_{s,t}^{(i,j)}\}.$$

We now observe the crucial property of $G''$.

**► Observation 12.1 (Claim 18 in [10]).** For every $1 \le i < j \le k$, a vertex $z_h^i \in V(G')$ (a vertex $z_h^j \in V(G'')$) is not adjacent to a vertex $r_{s,t}^{(i,j)} \in V(G')$ corresponding to the edge $v_s^i v_t^j \in E(G)$ if and only if $h = s$ ($h = t$, respectively).

**The New Gadget.** We now describe how to obtain from $G''$ a graph $G'$ that will be the graph of the instance of $\text{MAX-}(\sigma^*, \mathbb{N}_{\ge x})$ DOMINATION. We do so by adding a gadget to each set $Z(i)$ and $R(i, j)$ (for all $1 \le i < j \le k$). We first describe the gadget and then explain how to modify $H'$ to a new graph $K'$ such that $G'$ is a $K$-graph (where $K$ denotes the graph obtained from $K'$ by undoing the above described subdivisions that were made in $H$ to obtain $H'$). Let $X$ be any set of vertices of $G''$. The gadget $\mathfrak{B}(X)$ is a complete bipartite graph on $2d - 1$ vertices and bipartition $(\{\beta_{1,1}, \dots, \beta_{1,d}\}, \{\beta_{2,1}, \dots, \beta_{2,d-1}\})$. such that for $h \in [d]$, each vertex $\beta_{1,h}$ is additionally adjacent to each vertex in $X$. For $1 \le i < j \le k$, we use the notation $\mathfrak{B}(i) := \mathfrak{B}(Z(i))$ and $\mathfrak{B}(i, j) := \mathfrak{B}(R(i, j))$ and we denote their vertices by $\beta_{i, \cdot}^i$, and $\beta_{i, \cdot}^{(i,j)}$, respectively.

We obtain $K'$ by 'hardcoding' each gadget $\mathfrak{B}(\cdot)$ into $H'$. That is, for $i \in [k]$, we add the graph $\mathfrak{B}(i)$ and connect it to the remaining vertices via the edges $u_i \beta_{1,h}^i$ for $h \in [d]$. For $1 \le i < j \le k$, we proceed analogously in encoding $\mathfrak{B}(i, j)$ into $H'$. For an illustration of the graph $K$, see Figure 2. We observe that $|K| = 2d \binom{k}{2} = kd(k+1)$ and

$$\|K\| = 4 \binom{k}{2} + \binom{k}{2} \cdot (d + d(d-1)) = \frac{1}{2} k (d^2(k+1) + 4(k-1)). \quad (2)$$

We subdivide all newly introduced edges, i.e. all edges in $E(K') \setminus E(H')$ and for an edge $xy \in E(K') \setminus E(H')$, we denote the resulting vertex by $s(x, y)$. We are now ready to describe (the $K$-representation of) $G'$.
6:10 Generalized Distance Domination Problems on mim-width

2. For every $1 \le i < j \le k$, construct a node $w_{i,j}$ and two pairs of parallel edges $u_i w_{i,j}$ and $u_j w_{i,j}$.

We then construct the subdivision $H'$ of $H$ by first subdividing each edge $p$ times. We denote the subdivision nodes for 4 edges of $H$ constructed for each pair $1 \le i < j \le k$ in Step 2 by $x_1^{(i,j)}, \dots, x_p^{(i,j)}, y_1^{(i,j)}, \dots, y_p^{(i,j)}, x_1^{(j,i)}, \dots, x_p^{(j,i)}$, and $y_1^{(j,i)}, \dots, y_p^{(j,i)}$. To simplify notation, we assume that $u_i = x_0^{(i,j)} = y_0^{(i,j)}$, $u_j = x_0^{(j,i)} = y_0^{(j,i)}$ and $w_{i,j} = x_{p+1}^{(i,j)} = y_{p+1}^{(i,j)} = x_{p+1}^{(j,i)} = y_{p+1}^{(j,i)}$.

We now construct the $H$-graph $G''$ by defining its $H$-representation $\mathcal{M} = \{M_v\}_{v \in V(G'')}$ where each $M_v$ is a connected subset of $V(H')$. (Recall that $G$ denotes the graph of the MULTICOLORED CLIQUE instance.)

1. For each $i \in [k]$ and $s \in [p]$, construct a vertex $z_s^i$ with model

$$M_{z_s^i} := \bigcup_{j \in [k], j \neq i} \left( \left\{ x_0^{(i,j)}, \dots, x_{s-1}^{(i,j)} \right\} \cup \left\{ y_0^{(i,j)}, \dots, y_{p-s}^{(i,j)} \right\} \right).$$

2. For each edge $v_s^i v_t^j \in E(G)$ for $s, t \in [p]$ and $1 \le i < j \le k$, construct a vertex $r_{s,t}^{(i,j)}$ with:

$$M_{r_{s,t}^{(i,j)}} := \left\{ x_s^{(i,j)}, \dots, x_{p+1}^{(i,j)} \right\} \cup \left\{ y_{p-s+1}^{(i,j)}, \dots, y_{p+1}^{(i,j)} \right\} \\ \cup \left\{ x_t^{(j,i)}, \dots, x_{p+1}^{(j,i)} \right\} \cup \left\{ y_{p-t+1}^{(j,i)}, \dots, y_{p+1}^{(j,i)} \right\}.$$

Throughout the following, for $i \in [k]$ and $1 \le i < j \le k$, respectively, we use the notation

$$Z(i) := \bigcup_{s \in [p]} \{z_s^i\} \quad \text{and} \quad R(i, j) := \bigcup_{s,t \in [p]} \{r_{s,t}^{(i,j)}\}.$$

We now observe the crucial property of $G''$.

► **Observation 12.1** (Claim 18 in [10]). For every $1 \le i < j \le k$, a vertex $z_h^i \in V(G')$ (a vertex $z_h^j \in V(G')$) is not adjacent to a vertex $r_{s,t}^{(i,j)} \in V(G')$ corresponding to the edge $v_s^i v_t^j \in E(G)$ if and only if $h = s$ ($h = t$, respectively).

**The New Gadget.** We now describe how to obtain from $G''$ a graph $G'$ that will be the graph of the instance of $\text{MAX-}(\sigma^*, \mathbb{N}_{\ge x})$ DOMINATION. We do so by adding a gadget to each set $Z(i)$ and $R(i, j)$ (for all $1 \le i < j \le k$). We first describe the gadget and then explain how to modify $H'$ to a new graph $K'$ such that $G'$ is a $K$-graph (where $K$ denotes the graph obtained from $K'$ by undoing the above described subdivisions that were made in $H$ to obtain $H'$). Let $X$ be any set of vertices of $G''$. The gadget $\mathfrak{B}(X)$ is a complete bipartite graph on $2d - 1$ vertices and bipartition $(\{\beta_{1,1}, \dots, \beta_{1,d}\}, \{\beta_{2,1}, \dots, \beta_{2,d-1}\})$. such that for $h \in [d]$, each vertex $\beta_{1,h}$ is additionally adjacent to each vertex in $X$. For $1 \le i < j \le k$, we use the notation $\mathfrak{B}(i) := \mathfrak{B}(Z(i))$ and $\mathfrak{B}(i, j) := \mathfrak{B}(R(i, j))$ and we denote their vertices by $\beta_{i,\cdot}^i$ and $\beta_{i,\cdot}^{(i,j)}$, respectively.

We obtain $K'$ by 'hardcoding' each gadget $\mathfrak{B}(\cdot)$ into $H'$. That is, for $i \in [k]$, we add the graph $\mathfrak{B}(i)$ and connect it to the remaining vertices via the edges $u_i \beta_{1,h}^i$ for $h \in [d]$. For $1 \le i < j \le k$, we proceed analogously in encoding $\mathfrak{B}(i, j)$ into $H'$. For an illustration of the graph $K$, see Figure 2. We observe that $|K| = 2d \binom{k}{2} = kd(k+1)$ and

$$\|K\| = 4 \binom{k}{2} + \binom{k}{2} \cdot (d + d(d-1)) = \frac{1}{2}k(d^2(k+1) + 4(k-1)). \quad (2)$$

We subdivide all newly introduced edges, i.e. all edges in $E(K') \setminus E(H')$ and for an edge $xy \in E(K') \setminus E(H')$, we denote the resulting vertex by $s(x, y)$. We are now ready to describe (the $K$-representation of) $G'$.
<figure><img src="image_44.png" /><figcaption>Figure 2 The graph $K$ with respect to which the graph $G'$ constructed in the proof of Theorem 12 is a $K$-graph. In this example, we have $k = 3$ and $d = 4$.</figcaption></figure>

<figure><img src="image_45.png" /><figcaption>Figure 3 A part of the graph $G'$, where $1 \le i < j \le k$ and $d = 4$.</figcaption></figure>

1. For all $i \in [k]$ and $s \in [p]$, we add the vertices $s(u_i, \beta_{1,h}^i)$ (where $h \in [d]$) to the model of $z_s^i$. For all $1 \le i < j \le k$ and $s, t \in [p]$ with $v_s^i v_t^j \in E(G)$, we add the vertices $s(w_{(i,j)}, \beta_{1,h}^{(i,j)})$ for $h \in [d]$ to the model of $r_{s,t}^{(i,j)}$.

2. For all $i \in [k]$ and $h \in [d]$, we add a vertex $b_{1,h}^i$ with model $\{\beta_{1,h}^i, s(u_i, \beta_{1,h}^i)\} \cup \bigcup_{h' \in [d-1]} \{s(\beta_{1,h}^i, \beta_{2,h'}^i)\}$.

3. For all $i \in [k]$ and $h \in [d-1]$, we add a vertex $b_{2,h}^i$ with model $\{\beta_{2,h}^i\} \cup \bigcup_{h' \in [d]} \{s(\beta_{2,h}^i, \beta_{1,h'}^i)\}$.

4. For all $v_s^i v_t^j \in E(G)$ (where $1 \le i < j \le k$ and $s, t \in [p]$) and $h \in [d]$, we add a vertex $b_{1,h}^{(i,j)}$ with model $\{\beta_{1,h}^{(i,j)}, s(w_{(i,j)}, \beta_{1,h}^{(i,j)})\} \cup \bigcup_{h' \in [d-1]} \{s(\beta_{1,h}^{(i,j)}, \beta_{2,h'}^{(i,j)})\}$.

5. For all $v_s^i v_t^j \in E(G)$ (where $1 \le i < j \le k$ and $s, t \in [p]$) and $h \in [d-1]$, we add a vertex $b_{1,h}^{(i,j)}$ with model $\{\beta_{2,h}^{(i,j)}\} \cup \bigcup_{h' \in [d]} \{s(\beta_{2,h}^{(i,j)}, \beta_{1,h'}^{(i,j)})\}$.

One can verify that these five steps introduce the above described vertices to $G'$. For an illustration of $G'$, see Figure 3. The correctness proof of the reduction is given in the appendix; it is essentially a proof of the following claim.

**Claim 12.2 (★)**. $G$ has a multicolored clique if and only if $G'$ has a $(\sigma^*, \mathbb{N}_{\ge x})$ set of size $k' = 2d \cdot (k + \binom{k}{2})$.

We observe that $|V(G')| = \mathcal{O}(|V(G)| + d^2 \cdot k^2)$ and clearly, $G'$ can be constructed from $G$ in time polynomial in $|V(G)|$, $d$ and $k$ as well. Furthermore, by (2), $||K|| = \mathcal{O}(d^2 \cdot k^2)$ and the theorem follows. ◀

By Proposition 11, the previous theorem implies
<figure><img src="image_47.png" /><figcaption>Figure 2 The graph $K$ with respect to which the graph $G'$ constructed in the proof of Theorem 12 is a $K$-graph. In this example, we have $k = 3$ and $d = 4$.</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>Figure 3 A part of the graph $G'$, where $1 \le i < j \le k$ and $d = 4$.</figcaption></figure>

1. For all $i \in [k]$ and $s \in [p]$, we add the vertices $s(u_i, \beta_{1,h}^i)$ (where $h \in [d]$) to the model of $z_s^i$. For all $1 \le i < j \le k$ and $s, t \in [p]$ with $v_s^i v_t^j \in E(G)$, we add the vertices $s(w_{(i,j)}, \beta_{1,h}^{(i,j)})$ for $h \in [d]$ to the model of $r_{s,t}^{(i,j)}$.

2. For all $i \in [k]$ and $h \in [d]$, we add a vertex $b_{1,h}^i$ with model $\{\beta_{1,h}^i, s(u_i, \beta_{1,h}^i)\} \cup \bigcup_{h' \in [d-1]} \{s(\beta_{1,h}^i, \beta_{2,h'}^i)\}$.

3. For all $i \in [k]$ and $h \in [d-1]$, we add a vertex $b_{2,h}^i$ with model $\{\beta_{2,h}^i\} \cup \bigcup_{h' \in [d]} \{s(\beta_{2,h}^i, \beta_{1,h'}^i)\}$.

4. For all $v_s^i v_t^j \in E(G)$ (where $1 \le i < j \le k$ and $s, t \in [p]$) and $h \in [d]$, we add a vertex $b_{1,h}^{(i,j)}$ with model $\{\beta_{1,h}^{(i,j)}, s(w_{(i,j)}, \beta_{1,h}^{(i,j)})\} \cup \bigcup_{h' \in [d-1]} \{s(\beta_{1,h}^{(i,j)}, \beta_{2,h'}^{(i,j)})\}$.

5. For all $v_s^i v_t^j \in E(G)$ (where $1 \le i < j \le k$ and $s, t \in [p]$) and $h \in [d-1]$, we add a vertex $b_{1,h}^{(i,j)}$ with model $\{\beta_{2,h}^{(i,j)}\} \cup \bigcup_{h' \in [d]} \{s(\beta_{2,h}^{(i,j)}, \beta_{1,h'}^{(i,j)})\}$.

One can verify that these five steps introduce the above described vertices to $G'$. For an illustration of $G'$, see Figure 3. The correctness proof of the reduction is given in the appendix; it is essentially a proof of the following claim.

**Claim 12.2 (★)**. $G$ has a multicolored clique if and only if $G'$ has a $(\sigma^*, \mathbb{N}_{\ge x})$ set of size $k' = 2d \cdot (k + \binom{k}{2})$.

We observe that $|V(G')| = \mathcal{O}(|V(G)| + d^2 \cdot k^2)$ and clearly, $G'$ can be constructed from $G$ in time polynomial in $|V(G)|$, $d$ and $k$ as well. Furthermore, by (2), $||K|| = \mathcal{O}(d^2 \cdot k^2)$ and the theorem follows. ◀

By Proposition 11, the previous theorem implies
6:12 Generalized Distance Domination Problems on mim-width

**Corollary 13.** For any fixed $d \in \mathbb{N}$ and $x \le d+1$, the following holds. Let $\sigma^* \subseteq \mathbb{N}_{\le d}$ with $d \in \sigma^*$. Then, $\text{MAX}-(\sigma^*, \mathbb{N}_{\ge x})$ DOMINATION is W[1]-hard parameterized by linear mim-width plus solution size, and the hardness holds even if a corresponding decomposition tree is given.

We now turn to hardness of minimization problems that can be expressed in $(\sigma, \rho)$ notation. First, with a slight modification of the reduction due to Fomin et al. [10], we obtain hardness for problems such as TOTAL DOMINATING SET and DOMINATING INDUCED MATCHING.

**Theorem 14 (★)**. For $\sigma^* \subseteq \mathbb{N}^+$ with $1 \in \sigma^*$ and $\rho^* \subseteq \mathbb{N}^+$ with $\{1,2\} \subseteq \rho^*$, $\text{MIN}-(\sigma^*, \rho^*)$ DOMINATION is W[1]-hard on H-graphs parameterized by the number of edges in H plus solution size, and the hardness holds even when an H-representation of the input graph is given.

As a somewhat orthogonal result to Theorem 12, we now show hardness of several problems related to the *d*-DOMINATING SET problem, where each vertex that is not in the solution set has to be dominated by at least some fixed number of *d* neighbors in the solution.

**Theorem 15 (★)**. For any fixed $d \in \mathbb{N}_{\ge 2}$,<fnref n="5" /> the following holds. Let $\sigma^* \subseteq \mathbb{N}$ with $\{0,1,d-1\} \subseteq \sigma^*$ and $\rho^* \subseteq \mathbb{N}_{\ge d}$ with $\{d,d+1\} \subseteq \rho^*$. Then, $\text{MIN}-(\sigma^*, \rho^*)$ DOMINATION is W[1]-hard on H-graphs parameterized by the number of edges in H plus solution size, and the hardness even holds when an H-representation of the input graph is given.

Similarly to above, a combination of the previous two theorems with Proposition 11 yields the following hardness results for $(\sigma, \rho)$ minimization problems on graphs of bounded linear mim-width.

**Corollary 16.** Let $\sigma^* \subseteq \mathbb{N}$ and $\rho^* \subseteq \mathbb{N}$. Then, $\text{MIN}-(\sigma^*, \rho^*)$ DOMINATION is W[1]-hard parameterized by linear mim-width plus solution size, if one of the following holds.

(i) $\sigma^* \subseteq \mathbb{N}^+$ with $1 \in \sigma^*$ and $\rho^* \subseteq \mathbb{N}^+$ with $\{1,2\} \subseteq \rho^*$.

(ii) For some fixed $d \in \mathbb{N}_{\ge 2}$, $\{0,1,d-1\} \subseteq \sigma^*$ and $\rho^* \subseteq \mathbb{N}_{\ge d}$ with $\{d,d+1\} \subseteq \rho^*$. Furthermore, the hardness holds even if a corresponding decomposition tree is given.

7 Concluding Remarks

We have introduced the class of distance-$r$ $(\sigma, \rho)$ and LCVP problems. This generalizes well-known graph distance problems like distance-$r$ domination, distance-$r$ independence, distance-$r$ coloring and perfect $r$-codes. It also introduces many new distance problems for which the standard distance-1 version naturally captures a well-known graph property.

Using the graph parameter mim-width, we showed that all these problems are solvable in polynomial time for many interesting graph classes. These meta-algorithms will have runtimes which can likely be improved significantly for a particular problem on a particular graph class. For instance, blindly applying our results to solve DISTANCE-$r$ DOMINATING SET on permutation graphs yields an algorithm that runs in time $O(n^8)$: Permutation graphs have linear mim-width 1 (with a corresponding decomposition tree that can be computed in linear time) [3, Lemmas 2 and 5], so we can apply Corollary 7(i). However, there is an algorithm that solves DISTANCE-$r$ DOMINATING SET on permutation graphs in time $O(n^2)$ [15]; a much faster runtime.

We would like to draw attention to the most important and previously stated [13, 17, 20] open question regarding the mim-width parameter: Is there an XP approximation algorithm

<footnote n="5">⁵ Note that the analogous statement for $d=1$ follows from the reduction given in [10].</footnote>
6:12 Generalized Distance Domination Problems on mim-width

**Corollary 13.** For any fixed $d \in \mathbb{N}$ and $x \le d+1$, the following holds. Let $\sigma^* \subseteq \mathbb{N}_{\le d}$ with $d \in \sigma^*$. Then, $\text{MAX}-(\sigma^*, \mathbb{N}_{\ge x})$ **DOMINATION** is $\text{W}[1]$-hard parameterized by linear mim-width plus solution size, and the hardness holds even if a corresponding decomposition tree is given.

We now turn to hardness of minimization problems that can be expressed in $(\sigma, \rho)$ notation. First, with a slight modification of the reduction due to Fomin et al. [10], we obtain hardness for problems such as TOTAL DOMINATING SET and DOMINATING INDUCED MATCHING.

**Theorem 14 (★)**. For $\sigma^* \subseteq \mathbb{N}^+$ with $1 \in \sigma^*$ and $\rho^* \subseteq \mathbb{N}^+$ with $\{1, 2\} \subseteq \rho^*$, $\text{MIN}-(\sigma^*, \rho^*)$ **DOMINATION** is $\text{W}[1]$-hard on $H$-graphs parameterized by the number of edges in $H$ plus solution size, and the hardness holds even when an $H$-representation of the input graph is given.

As a somewhat orthogonal result to Theorem 12, we now show hardness of several problems related to the $d$-DOMINATING SET problem, where each vertex that is not in the solution set has to be dominated by at least some fixed number of $d$ neighbors in the solution.

**Theorem 15 (★)**. For any fixed $d \in \mathbb{N}_{\ge 2}$,<fnref n="5" /> the following holds. Let $\sigma^* \subseteq \mathbb{N}$ with $\{0, 1, d-1\} \subseteq \sigma^*$ and $\rho^* \subseteq \mathbb{N}_{\ge d}$ with $\{d, d+1\} \subseteq \rho^*$. Then, $\text{MIN}-(\sigma^*, \rho^*)$ **DOMINATION** is $\text{W}[1]$-hard on $H$-graphs parameterized by the number of edges in $H$ plus solution size, and the hardness even holds when an $H$-representation of the input graph is given.

Similarly to above, a combination of the previous two theorems with Proposition 11 yields the following hardness results for $(\sigma, \rho)$ minimization problems on graphs of bounded linear mim-width.

**Corollary 16.** Let $\sigma^* \subseteq \mathbb{N}$ and $\rho^* \subseteq \mathbb{N}$. Then, $\text{MIN}-(\sigma^*, \rho^*)$ **DOMINATION** is $\text{W}[1]$-hard parameterized by linear mim-width plus solution size, if one of the following holds.

(i) $\sigma^* \subseteq \mathbb{N}^+$ with $1 \in \sigma^*$ and $\rho^* \subseteq \mathbb{N}^+$ with $\{1, 2\} \subseteq \rho^*$.

(ii) For some fixed $d \in \mathbb{N}_{\ge 2}$, $\{0, 1, d-1\} \subseteq \sigma^*$ and $\rho^* \subseteq \mathbb{N}_{\ge d}$ with $\{d, d+1\} \subseteq \rho^*$. Furthermore, the hardness holds even if a corresponding decomposition tree is given.

7 Concluding Remarks

We have introduced the class of distance-$r$ $(\sigma, \rho)$ and LCVP problems. This generalizes well-known graph distance problems like distance-$r$ domination, distance-$r$ independence, distance-$r$ coloring and perfect $r$-codes. It also introduces many new distance problems for which the standard distance-1 version naturally captures a well-known graph property.

Using the graph parameter mim-width, we showed that all these problems are solvable in polynomial time for many interesting graph classes. These meta-algorithms will have runtimes which can likely be improved significantly for a particular problem on a particular graph class. For instance, blindly applying our results to solve DISTANCE-$r$ **DOMINATING SET** on permutation graphs yields an algorithm that runs in time $O(n^8)$: Permutation graphs have linear mim-width 1 (with a corresponding decomposition tree that can be computed in linear time) [3, Lemmas 2 and 5], so we can apply Corollary 7(i). However, there is an algorithm that solves DISTANCE-$r$ **DOMINATING SET** on permutation graphs in time $O(n^2)$ [15]; a much faster runtime.

We would like to draw attention to the most important and previously stated [13, 17, 20] open question regarding the mim-width parameter: Is there an XP approximation algorithm

<footnote n="5">⁵ Note that the analogous statement for $d=1$ follows from the reduction given in [10].</footnote>
for computing mim-width? An important first step could be to devise a polynomial-time algorithm deciding if a graph has mim-width 1, or even linear mim-width 1.

Regarding lower bounds, we expanded on the previous results by Fomin et al. [10] and showed that many $(\sigma, \rho)$ problems are W[1]-hard parameterized by mim-width. However, it remains open whether there exists a problem which is NP-hard in general, yet FPT by mim-width. In particular, there are currently no hardness results when $\sigma$ and $\rho$ are both finite. Even so, we conjecture that every NP-hard (distance) $(\sigma, \rho)$ problem is W[1]-hard parameterized by mim-width.

References

1. Geir Agnarsson, Peter Damaschke, and Magnús M. Halldórsson. Powers of geometric intersection graphs and dispersion algorithms. Discrete Appl. Math., 132(1-3):3–16, 2003. doi:10.1016/S0166-218X(03)00386-X.

2. Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-free graphs, independent sets, and subexponential-time algorithms. In Proc. IPEC 2016, pages 3:1–3:12, 2017.

3. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54–65, 2013. doi:10.1016/j.tcs.2013.01.011.

4. Norman Biggs. Perfect codes in graphs. J. Combin. Theory, Ser. B, 15(3):289–296, 1973. doi:10.1016/0095-8956(73)90042-7.

5. A. Brandstädt, V. Le, and J. Spinrad. Graph Classes: A Survey. SIAM, 1999. doi:10.1137/1.9780898719796.

6. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66–76, 2013. doi:10.1016/j.tcs.2013.01.009.

7. Steven Chaplick, Martin Töpfer, Jan Voborník, and Peter Zeman. On H-topological intersection graphs. In Proc. WG 2017, pages 167–179. Springer, 2017.

8. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Viallette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53–61, 2009.

9. Carsten Flotow. On powers of m-trapezoid graphs. Discrete Appl. Math., 63(2):187–192, 1995. doi:10.1016/0166-218X(95)00062-V.

10. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. In Proc. ESA 2018, pages 30:1–30:14, 2018.

11. M. A. Henning, Ortrud R. Oellermann, and Henda C. Swart. Bounds on distance domination parameters. J. Combin. Inform. Syst. Sci., 16(1):11–18, 1991.

12. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance-Domination Problems and Their Complexity on Graphs of Bounded Mim-Width. arXiv preprint, 2018. arXiv:1803.03514.

13. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In Proc. STACS 2018, pages 42:1–42:14, 2018.

14. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757–771, 2003.

15. Akul Rana, Anita Pal, and Madhumangal Pal. An efficient algorithm to solve the distance $k$-domination problem on permutation graphs. J. Discrete Math. Sci. Cryptography, 19(2):241–255, 2016.
for computing mim-width? An important first step could be to devise a polynomial-time algorithm deciding if a graph has mim-width 1, or even linear mim-width 1.

Regarding lower bounds, we expanded on the previous results by Fomin et al. [10] and showed that many $(\sigma, \rho)$ problems are W[1]-hard parameterized by mim-width. However, it remains open whether there exists a problem which is NP-hard in general, yet FPT by mim-width. In particular, there are currently no hardness results when $\sigma$ and $\rho$ are both finite. Even so, we conjecture that every NP-hard (distance) $(\sigma, \rho)$ problem is W[1]-hard parameterized by mim-width.

References

1. Geir Agnarsson, Peter Damaschke, and Magnús M. Halldórsson. Powers of geometric intersection graphs and dispersion algorithms. *Discrete Appl. Math.*, 132(1-3):3–16, 2003. doi:10.1016/S0166-218X(03)00386-X.

2. Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-free graphs, independent sets, and subexponential-time algorithms. In *Proc. IPEC 2016*, pages 3:1–3:12, 2017.

3. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. *Theor. Comput. Sci.*, 511:54–65, 2013. doi:10.1016/j.tcs.2013.01.011.

4. Norman Biggs. Perfect codes in graphs. *J. Combin. Theory, Ser. B*, 15(3):289–296, 1973. doi:10.1016/0095-8956(73)90042-7.

5. A. Brandstädt, V. Le, and J. Spinrad. *Graph Classes: A Survey*. SIAM, 1999. doi:10.1137/1.9780898719796.

6. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. *Theor. Comput. Sci.*, 511:66–76, 2013. doi:10.1016/j.tcs.2013.01.009.

7. Steven Chaplick, Martin Töpfer, Jan Voborník, and Peter Zeman. On H-topological intersection graphs. In *Proc. WG 2017*, pages 167–179. Springer, 2017.

8. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Viallette. On the parameterized complexity of multiple-interval graph problems. *Theor. Comput. Sci.*, 410(1):53–61, 2009.

9. Carsten Flotow. On powers of m-trapezoid graphs. *Discrete Appl. Math.*, 63(2):187–192, 1995. doi:10.1016/0166-218X(95)00062-V.

10. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. In *Proc. ESA 2018*, pages 30:1–30:14, 2018.

11. M. A. Henning, Ortrud R. Oellermann, and Henda C. Swart. Bounds on distance domination parameters. *J. Combin. Inform. Syst. Sci.*, 16(1):11–18, 1991.

12. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance-Domination Problems and Their Complexity on Graphs of Bounded Mim-Width. *arXiv preprint*, 2018. arXiv:1803.03514.

13. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In *Proc. STACS 2018*, pages 42:1–42:14, 2018.

14. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. *J. Comput. Syst. Sci.*, 67(4):757–771, 2003.

15. Akul Rana, Anita Pal, and Madhumangal Pal. An efficient algorithm to solve the distance $k$-domination problem on permutation graphs. *J. Discrete Math. Sci. Cryptography*, 19(2):241–255, 2016.
6:14 Generalized Distance Domination Problems on mim-width

16 Arundhati Raychaudhuri. On powers of strongly chordal and circular arc graphs. *Ars Combin.*, 34:147–160, 1992.

17 Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. *Theor. Comput. Sci.*, 615:120–125, 2016. doi:10.1016/j.tcs.2015.11.039.

18 Peter J. Slater. *R*-domination in graphs. *J. ACM*, 23(3):446–450, 1976.

19 Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. *SIAM J. Discrete Math.*, 10(4):529–550, 1997.

20 Martin Vatshelle. *New width parameters of graphs*. PhD thesis, University of Bergen, 2012.
6:14 Generalized Distance Domination Problems on mim-width

16 Arundhati Raychaudhuri. On powers of strongly chordal and circular arc graphs. *Ars Combin.*, 34:147–160, 1992.

17 Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. *Theor. Comput. Sci.*, 615:120–125, 2016. doi:10.1016/j.tcs.2015.11.039.

18 Peter J. Slater. *R*-domination in graphs. *J. ACM*, 23(3):446–450, 1976.

19 Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. *SIAM J. Discrete Math.*, 10(4):529–550, 1997.

20 Martin Vatshelle. *New width parameters of graphs*. PhD thesis, University of Bergen, 2012.
# A Parameterized Complexity View on Collapsing $k$-Cores

Junjie Luo<fnref n="1" />

Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
junjie.luo@campus.tu-berlin.de, luojunjie@amss.ac.cn

Hendrik Molter<fnref n="2" />

Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
h.molter@tu-berlin.de

Ondřej Suchý<fnref n="3" />

Department of Theoretical Computer Science, Faculty of Information Technology,
Czech Technical University in Prague, Prague, Czech Republic
ondrej.suchy@fit.cvut.cz

**Abstract**

We study the NP-hard graph problem *COLLAPSED* *k*-CORE where, given an undirected graph *G* and integers *b*, *x*, and *k*, we are asked to remove *b* vertices such that the *k*-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree *k*, has size at most *x*. *COLLAPSED* *k*-CORE was introduced by Zhang et al. [AAAI 2017] and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. *COLLAPSED* *k*-CORE is a generalization of *r*-DEGENERATE VERTEX DELETION (which is known to be NP-hard for all *r* ≥ 0) where, given an undirected graph *G* and integers *b* and *r*, we are asked to remove *b* vertices such that the remaining graph is *r*-degenerate, that is, every its subgraph has minimum degree at most *r*.

We investigate the parameterized complexity of *COLLAPSED* *k*-CORE with respect to the parameters *b*, *x*, and *k*, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of *COLLAPSED* *k*-CORE for *k* ≤ 2 and *k* ≥ 3. For the latter case it is known that for all *x* ≥ 0 *COLLAPSED* *k*-CORE is W[P]-hard when parameterized by *b*. We show that *COLLAPSED* *k*-CORE is W[1]-hard when parameterized by *b* and in FPT when parameterized by (*b* + *x*) if *k* ≤ 2. Furthermore, we show that *COLLAPSED* *k*-CORE is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** *r*-Degenerate Vertex Deletion, Feedback Vertex Set, Fixed-Parameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.7

**Related Version** A full version is available at [18], https://arxiv.org/abs/1805.12453.

<figure><img src="image_46.png" /></figure>

<footnote n="1">¹ Supported by CAS-DAAD Joint Fellowship Program for Doctoral Students of UCAS.</footnote>

<footnote n="2">² Supported by the DFG, project MATE (NI 369/17).</footnote>

<footnote n="3">³ Supported by grant 17-20065S of the Czech Science Foundation.</footnote>
# A Parameterized Complexity View on
## Collapsing *k*-Cores

Junjie Luo<fnref n="1" />

Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
junjie.luo@campus.tu-berlin.de, luojunjie@amss.ac.cn

Hendrik Molter<fnref n="2" />

Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
h.molter@tu-berlin.de

Ondřej Suchý<fnref n="3" />

Department of Theoretical Computer Science, Faculty of Information Technology,
Czech Technical University in Prague, Prague, Czech Republic
ondrej.suchy@fit.cvut.cz

**Abstract**

We study the NP-hard graph problem *COLLAPSED* *k*-CORE where, given an undirected graph *G* and integers *b*, *x*, and *k*, we are asked to remove *b* vertices such that the *k*-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree *k*, has size at most *x*. *COLLAPSED* *k*-CORE was introduced by Zhang et al. [AAAI 2017] and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. *COLLAPSED* *k*-CORE is a generalization of *r*-DEGENERATE VERTEX DELETION (which is known to be NP-hard for all *r* ≥ 0) where, given an undirected graph *G* and integers *b* and *r*, we are asked to remove *b* vertices such that the remaining graph is *r*-degenerate, that is, every its subgraph has minimum degree at most *r*.

We investigate the parameterized complexity of *COLLAPSED* *k*-CORE with respect to the parameters *b*, *x*, and *k*, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of *COLLAPSED* *k*-CORE for *k* ≤ 2 and *k* ≥ 3. For the latter case it is known that for all *x* ≥ 0 *COLLAPSED* *k*-CORE is W[P]-hard when parameterized by *b*. We show that *COLLAPSED* *k*-CORE is W[1]-hard when parameterized by *b* and in FPT when parameterized by (*b* + *x*) if *k* ≤ 2. Furthermore, we show that *COLLAPSED* *k*-CORE is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** *r*-Degenerate Vertex Deletion, Feedback Vertex Set, Fixed-Parameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.7

**Related Version** A full version is available at [18], https://arxiv.org/abs/1805.12453.

<figure><img src="image_49.png" /></figure>

<footnote n="1">¹ Supported by CAS-DAAD Joint Fellowship Program for Doctoral Students of UCAS.</footnote>

<footnote n="2">² Supported by the DFG, project MATE (NI 369/17).</footnote>

<footnote n="3">³ Supported by grant 17-20065S of the Czech Science Foundation.</footnote>
7:2 A Parameterized Complexity View on Collapsing *k*-Cores

**Acknowledgements** This research was initiated at the annual research retreat of the Algorithmics and Computational Complexity (AKT) group of TU Berlin, held in Darlingerode, Germany, from March 19 till March 23, 2018. The authors would like to thank Anne-Sophie Himmel for initial discussions leading to the results in this paper.

1 Introduction

In recent years, modelling user engagement in social networks has received substantial interest [23, 24]. A popular assumption is that a user engages in a social network platform if she has at least a certain number of contacts, say *k*, on the platform. Further, she is inclined to abandon the social network if she has less than *k* contacts [2, 7, 8, 11, 19, 25]. In compliance with this assumption, a suitable graph-theoretic model for the “stable” part of a social network is the so-called *k*-core of the social network graph, that is, the largest induced subgraph with minimum degree *k* [21].<fnref n="4" />

Now, given a stable social network, that is, a graph with minimum degree *k*, the departure of a user decreases the degree of her neighbors in the graph by one which then might be smaller than *k* for some of them. Following our assumption these users now will abandon the network, too. This causes a cascading effect of users dropping out (collapse) of the network until a new stable state is reached. From an adversarial perspective a natural question is how to maximally destabilize a competing social network platform by compelling *b* users to abandon the network. This problem was introduced as *COLLAPSED k-CORE* by Zhang et al. [25] and the decision version is formally defined as follows.

COLLAPSED *k*-CORE

**Input:** An undirected graph *G* = (*V*, *E*), and integers *b*, *x*, and *k*.

**Question:** Is there a set $S \subseteq V$ with $|S| \le b$ such that the *k*-core of $G - S$ has size at most *x*?

In the mentioned motivation, one would aim to minimize *x* for a given *b* and *k*. Alternatively, we can also interpret this problem as a measure for resilience against user drop outs of a social network by determining the smallest *b* for a given *k* and *x*.

**Related Work.** In 2017 Zhang et al. [25] showed that *COLLAPSED k-CORE* is NP-hard for any $k \ge 1$ and gave a greedy algorithm to compute suboptimal solutions for the problem. However, for $x = 0$ and any fixed $k$, solving *COLLAPSED k-CORE* is equivalent to finding *b* vertices such that after removing said vertices, the remaining graph is $(k-1)$-degenerate<fnref n="5" />. This problem is known as *r*-DEGENERATE VERTEX DELETION and it is defined as follows.

r-DEGENERATE VERTEX DELETION

**Input:** An undirected graph *G* = (*V*, *E*), and integers *b* and *r*.

**Question:** Is there a set $S \subseteq V$ with $|S| \le b$ such that $G - S$ is *r*-degenerate?

It is easy to see that *COLLAPSED k-CORE* is a generalization of *r*-DEGENERATE VERTEX DELETION. In 2010 Mathieson [20] showed that *r*-DEGENERATE VERTEX DELETION is NP-complete and W[P]-complete when parameterized by the budget *b* for all *r* ≥ 2 even if the input graph is already (*r* + 1)-degenerate and has maximum degree 2*r* + 1. In the mid-90s Abrahamson et al. [1] already claimed W[P]-completeness for *r*-DEGENERATE VERTEX DELETION with *r* = 2 when parameterized by *b* under the name DEGREE 3 SUBGRAPH

<footnote n="4">⁴ Note that the *k*-core of a graph is uniquely determined.</footnote>

<footnote n="5">⁵ A graph *G* is *r*-degenerate if every subgraph of *G* has a vertex with degree at most *r* [10].</footnote>
7:2 A Parameterized Complexity View on Collapsing k-Cores

**Acknowledgements** This research was initiated at the annual research retreat of the Algorithmics and Computational Complexity (AKT) group of TU Berlin, held in Darlingerode, Germany, from March 19 till March 23, 2018. The authors would like to thank Anne-Sophie Himmel for initial discussions leading to the results in this paper.

1 Introduction

In recent years, modelling user engagement in social networks has received substantial interest [23, 24]. A popular assumption is that a user engages in a social network platform if she has at least a certain number of contacts, say *k*, on the platform. Further, she is inclined to abandon the social network if she has less than *k* contacts [2, 7, 8, 11, 19, 25]. In compliance with this assumption, a suitable graph-theoretic model for the “stable” part of a social network is the so-called *k*-core of the social network graph, that is, the largest induced subgraph with minimum degree *k* [21].<fnref n="4" />

Now, given a stable social network, that is, a graph with minimum degree *k*, the departure of a user decreases the degree of her neighbors in the graph by one which then might be smaller than *k* for some of them. Following our assumption these users now will abandon the network, too. This causes a cascading effect of users dropping out (collapse) of the network until a new stable state is reached. From an adversarial perspective a natural question is how to maximally destabilize a competing social network platform by compelling *b* users to abandon the network. This problem was introduced as *COLLAPSED k-CORE* by Zhang et al. [25] and the decision version is formally defined as follows.

COLLAPSED *k*-CORE

**Input:** An undirected graph $G = (V, E)$, and integers $b, x$, and $k$.

**Question:** Is there a set $S \subseteq V$ with $|S| \le b$ such that the *k*-core of $G - S$ has size at most *x*?

In the mentioned motivation, one would aim to minimize *x* for a given *b* and *k*. Alternatively, we can also interpret this problem as a measure for resilience against user drop outs of a social network by determining the smallest *b* for a given *k* and *x*.

**Related Work.** In 2017 Zhang et al. [25] showed that *COLLAPSED k-CORE* is NP-hard for any $k \ge 1$ and gave a greedy algorithm to compute suboptimal solutions for the problem. However, for $x = 0$ and any fixed $k$, solving *COLLAPSED k-CORE* is equivalent to finding *b* vertices such that after removing said vertices, the remaining graph is $(k-1)$-degenerate<fnref n="5" />. This problem is known as *r*-DEGENERATE VERTEX DELETION and it is defined as follows.

r-DEGENERATE VERTEX DELETION

**Input:** An undirected graph $G = (V, E)$, and integers $b$ and $r$.

**Question:** Is there a set $S \subseteq V$ with $|S| \le b$ such that $G - S$ is *r*-degenerate?

It is easy to see that *COLLAPSED k-CORE* is a generalization of *r*-DEGENERATE VERTEX DELETION. In 2010 Mathieson [20] showed that *r*-DEGENERATE VERTEX DELETION is NP-complete and W[P]-complete when parameterized by the budget *b* for all *r* ≥ 2 even if the input graph is already (*r* + 1)-degenerate and has maximum degree 2*r* + 1. In the mid-90s Abrahamson et al. [1] already claimed W[P]-completeness for *r*-DEGENERATE VERTEX DELETION with *r* = 2 when parameterized by *b* under the name DEGREE 3 SUBGRAPH

<footnote n="4">⁴ Note that the *k*-core of a graph is uniquely determined.</footnote>

<footnote n="5">⁵ A graph *G* is *r*-degenerate if every subgraph of *G* has a vertex with degree at most *r* [10].</footnote>
**ANNIHILATOR.** For $r = 1$, the problem is equivalent to FEEDBACK VERTEX SET and for $r = 0$ it is equivalent to VERTEX COVER, both of which are known to be NP-complete and fixed-parameter tractable when parameterized by the solution size [9, 12]. The aforementioned results concerning $r$-DEGENERATE VERTEX DELETION in fact imply the hardness results shown by Zhang et al. [25] for COLLAPSED $k$-CORE.

**Our Contribution.** We complete the parameterized complexity landscape of COLLAPSED $k$-CORE with respect to the parameters $b, k$, and $x$. Specifically, we correct errors in the literature [1, 20] concerning the W[P]-completeness of $r$-DEGENERATE VERTEX DELETION when parameterized by $b$ for $r = 2$. We clarify the parameterized complexity of COLLAPSED $k$-CORE for $k \le 2$ by showing W[1]-hardness for parameter $b$ and fixed-parameter tractability for the combination of $b$ and $x$. Together with previously known results, this reveals a dichotomy in the computational complexity of COLLAPSED $k$-CORE for $k \le 2$ and $k \ge 3$.

We present two single exponential linear time FPT algorithms, one for COLLAPSED $k$-CORE with $k=1$ and one for $k=2$. In both cases the parameter is $(b+x)$. In particular, the algorithm for $k=2$ runs in $O(1.755^{x+4b} \cdot n)$ time which means that it solves FEEDBACK VERTEX SET in $O(9.487^b \cdot n)$ time (here, $b$ is the solution size of FEEDBACK VERTEX SET). Cao [5] independently developed a very similar algorithm for FEEDBACK VERTEX SET. In comparison, we additionally generalize the algorithm for COLLAPSED $k$-CORE and give a more thorough running time analysis. To the best of our knowledge, despite of its simplicity this algorithm improves many previous linear time parameterized algorithm for FEEDBACK VERTEX SET [13, 17]. However, recently a linear time computable polynomial kernel for FEEDBACK VERTEX SET was shown [14], which together with e.g. [16] yields an even faster linear time parameterized algorithm.

Furthermore, we conduct a thorough parameterized complexity analysis with respect to structural parameters of the input graph. On the positive side, we show that COLLAPSED $k$-CORE is fixed-parameter tractable when parameterized by the treewidth of the input graph and show that it presumably does not admit a polynomial kernel when parameterized by either the vertex cover number or the bandwidth of the input graph. We also show that the problem is fixed-parameter tractable when parameterized by the combination of the cliquewidth of the input graph and $b$ or $x$. Further results include W[1]-hardness when parameterized by the clique cover number of the input graph and para-NP-hardness for the domination number of the input graph.

Due to space contraints, results marked with $(\star)$ are (in parts) deferred to a full version [18].

## 2 Hardness Results from the Literature

In this section, we gather and discuss known hardness results for COLLAPSED $k$-CORE. Recall that that COLLAPSED $k$-CORE with $x = 0$ is the same problem as $r$-DEGENERATE VERTEX DELETION with $r = k - 1$. Hence, the hardness of COLLAPSED $k$-CORE was first established by Mathieson [20] who showed that $r$-DEGENERATE VERTEX DELETION is NP-complete and W[P]-complete when parameterized by the budget $b$ for all $r \ge 2$ even if the input graph is already $(r+1)$-degenerate and has maximum degree $2r+1$. However, in the proof of Mathieson [20] the reduction is incorrect for the case $r = 2$. Abrahamson et al. [1] claim W[P]-completeness for $r = 2$ but their reduction is also flawed. We provide counterexamples for both cases and show how to adjust the reduction of Mathieson [20] in a full version [18].

**► Theorem 1 (Corrected from [20]) ($\star$).** For any $r \ge 2$ $r$-DEGENERATE VERTEX DELETION is NP-hard and W[P]-complete when parameterized by $b$, even if the degeneracy of the input graph is $r+1$ and the maximum degree of the input graph is $2r+1$.
**ANNIHILATOR.** For $r = 1$, the problem is equivalent to FEEDBACK VERTEX SET and for $r = 0$ it is equivalent to VERTEX COVER, both of which are known to be NP-complete and fixed-parameter tractable when parameterized by the solution size [9, 12]. The aforementioned results concerning $r$-DEGENERATE VERTEX DELETION in fact imply the hardness results shown by Zhang et al. [25] for COLLAPSED $k$-CORE.

**Our Contribution.** We complete the parameterized complexity landscape of COLLAPSED $k$-CORE with respect to the parameters $b, k$, and $x$. Specifically, we correct errors in the literature [1, 20] concerning the W[P]-completeness of $r$-DEGENERATE VERTEX DELETION when parameterized by $b$ for $r = 2$. We clarify the parameterized complexity of COLLAPSED $k$-CORE for $k \le 2$ by showing W[1]-hardness for parameter $b$ and fixed-parameter tractability for the combination of $b$ and $x$. Together with previously known results, this reveals a dichotomy in the computational complexity of COLLAPSED $k$-CORE for $k \le 2$ and $k \ge 3$.

We present two single exponential linear time FPT algorithms, one for COLLAPSED $k$-CORE with $k=1$ and one for $k=2$. In both cases the parameter is $(b+x)$. In particular, the algorithm for $k=2$ runs in $O(1.755^{x+4b} \cdot n)$ time which means that it solves FEEDBACK VERTEX SET in $O(9.487^b \cdot n)$ time (here, $b$ is the solution size of FEEDBACK VERTEX SET). Cao [5] independently developed a very similar algorithm for FEEDBACK VERTEX SET. In comparison, we additionally generalize the algorithm for COLLAPSED $k$-CORE and give a more thorough running time analysis. To the best of our knowledge, despite of its simplicity this algorithm improves many previous linear time parameterized algorithm for FEEDBACK VERTEX SET [13, 17]. However, recently a linear time computable polynomial kernel for FEEDBACK VERTEX SET was shown [14], which together with e.g. [16] yields an even faster linear time parameterized algorithm.

Furthermore, we conduct a thorough parameterized complexity analysis with respect to structural parameters of the input graph. On the positive side, we show that COLLAPSED $k$-CORE is fixed-parameter tractable when parameterized by the treewidth of the input graph and show that it presumably does not admit a polynomial kernel when parameterized by either the vertex cover number or the bandwidth of the input graph. We also show that the problem is fixed-parameter tractable when parameterized by the combination of the cliquewidth of the input graph and $b$ or $x$. Further results include W[1]-hardness when parameterized by the clique cover number of the input graph and para-NP-hardness for the domination number of the input graph.

Due to space contraints, results marked with $(\star)$ are (in parts) deferred to a full version [18].

## 2 Hardness Results from the Literature

In this section, we gather and discuss known hardness results for COLLAPSED $k$-CORE. Recall that that COLLAPSED $k$-CORE with $x = 0$ is the same problem as $r$-DEGENERATE VERTEX DELETION with $r = k - 1$. Hence, the hardness of COLLAPSED $k$-CORE was first established by Mathieson [20] who showed that $r$-DEGENERATE VERTEX DELETION is NP-complete and W[P]-complete when parameterized by the budget $b$ for all $r \ge 2$ even if the input graph is already $(r+1)$-degenerate and has maximum degree $2r+1$. However, in the proof of Mathieson [20] the reduction is incorrect for the case $r = 2$. Abrahamson et al. [1] claim W[P]-completeness for $r = 2$ but their reduction is also flawed. We provide counterexamples for both cases and show how to adjust the reduction of Mathieson [20] in a full version [18].

**► Theorem 1 (Corrected from [20]) (★).** For any $r \ge 2$ $r$-DEGENERATE VERTEX DELETION is NP-hard and W[P]-complete when parameterized by $b$, even if the degeneracy of the input graph is $r+1$ and the maximum degree of the input graph is $2r+1$.
7:4 A Parameterized Complexity View on Collapsing k-Cores

The following observation shows that the hardness result by Mathieson [20] (Theorem 1) easily transfers to *COLLAPSED k-CORE* (also in the cases where $x \neq 0$).

**► Observation 2 (*)**. Let $x' > 0$ be a positive integer. There is a reduction which transforms instances $(G, b, x, k)$ of *COLLAPSED k-CORE* with $x = 0$ into equivalent instances $(G', b, x', k)$ of *COLLAPSED k-CORE*.

With that, we arrive at the following corollary.

**► Corollary 3.** *COLLAPSED k-CORE is NP-hard and W[P]-hard when parameterized by b for all $x \ge 0$ and $k \ge 3$, even if the degeneracy of the input graph is $\max\{k, x-1\}$ and the maximum degree of the input graph is $\max\{2k-1, x-1\}$.*

Note that r-DEGENERATE VERTEX DELETION is known to be NP-hard for all $r \ge 0$.<fnref n="6" /> Hence, we also know that *COLLAPSED k-CORE* is NP-hard for $k \le 2$ and all $x \ge 0$. However, the parameterized complexity with respect to *b* is open in this case. We settle this in the next section.

**3 Algorithms and Complexity for $k=1$ and $k=2$**

In this section we investigate the parameterized complexity of *COLLAPSED k-CORE* for the case that $k \le 2$. Since Theorem 3 only applies for $k \ge 3$ we first show in the following that the problem is W[1]-hard with respect to the combination of *b* and $(n-x)$ for all $k \ge 1$. Furthermore, we present two algorithms; one that solves *COLLAPSED k-CORE* with $k=1$ and one for the $k=2$ case. Both algorithms run in single exponential linear FPT-time with respect to the parameter combination $(b+x)$.

We first give a parameterized reduction from *CLIQUE* to *COLLAPSED k-CORE*. Note that since this hardness result holds for the combination of *b* and the dual parameter of *x*, it is incomparable to Theorem 3 even for $k \ge 3$.

**► Proposition 4 (*)**. *COLLAPSED k-CORE is W[1]-hard when parameterized by the combination of b and $(n-x)$ for all $k \ge 1$, even if the input graph is bipartite and $\max\{2, k\}$-degenerate.*

**Proof.** We reduce from W[1]-hard problem *CLIQUE* [9], where given a graph $G = (V, E)$ and an integer $p$, the task is to decide whether $G$ contains a clique of size at least $p$. Let $(G, p)$ be an instance of *CLIQUE* and $k$ be a given constant. We build an instance $(G', b, x, k)$ of *COLLAPSED k-CORE* as follows. We can assume that $p \le |V(G)|$, as otherwise we can output a trivial no-instance. We further assume that each vertex of $G$ has degree at least $p+1$. Vertex of degree less than $p-1$ is not part of a clique of size at least $p$, while for all vertices of degree $p-1$ or $p$ we can check in $O(n \cdot p^3)$ time whether there is a clique of size at least $p$ containing any of them.

We let $V(G') = V \cup U \cup W$, where $V = V(G)$ are the vertices of $G$, $U = \{u_e^i \mid e \in E, i \in \{1, \dots, k\}\}$, and $W = \{w_e^i \mid e \in E, i \in \{1, \dots, k-1\}\}$. We also let $E(G') = E_U \cup E_W$, where $E_U = \{(v, u_e^i) \mid e \in E, i \in \{1, \dots, k\}, v \in e\}$, and $E_W = \{\{u_e^i, w_e^{i'}\} \mid e \in E, i \in \{1, \dots, k\}, i' \in \{1, \dots, k-1\}\}$. We actually only introduce the sets $W$ and $E_W$ if $k \ge 2$.

Finally we set $b=p$ and $x=n - (p + (2k-1)(\binom{p}{2}))$, where $n = |V(G')|$ is the number of vertices of graph $G'$.

<footnote n="6">⁶ Theorem 1 states NP-hardness of r-DEGENERATE VERTEX DELETION for $r \ge 2$. Recall that for $r = 1$ r-DEGENERATE VERTEX DELETION is equivalent to FEEDBACK VERTEX SET and for $r = 0$ it is equivalent to VERTEX COVER, both of which are known to be NP-hard [12].</footnote>
7:4 A Parameterized Complexity View on Collapsing k-Cores

The following observation shows that the hardness result by Mathieson [20] (Theorem 1) easily transfers to *COLLAPSED k-CORE* (also in the cases where $x \neq 0$).

**► Observation 2 (*)**. Let $x' > 0$ be a positive integer. There is a reduction which transforms instances $(G, b, x, k)$ of *COLLAPSED k-CORE* with $x = 0$ into equivalent instances $(G', b, x', k)$ of *COLLAPSED k-CORE*.

With that, we arrive at the following corollary.

**► Corollary 3.** *COLLAPSED k-CORE is NP-hard and W[P]-hard when parameterized by b for all $x \ge 0$ and $k \ge 3$, even if the degeneracy of the input graph is $\max\{k, x-1\}$ and the maximum degree of the input graph is $\max\{2k-1, x-1\}$.*

Note that r-DEGENERATE VERTEX DELETION is known to be NP-hard for all $r \ge 0$.<fnref n="6" /> Hence, we also know that *COLLAPSED k-CORE* is NP-hard for $k \le 2$ and all $x \ge 0$. However, the parameterized complexity with respect to *b* is open in this case. We settle this in the next section.

**3 Algorithms and Complexity for $k=1$ and $k=2$**

In this section we investigate the parameterized complexity of *COLLAPSED k-CORE* for the case that $k \le 2$. Since Theorem 3 only applies for $k \ge 3$ we first show in the following that the problem is W[1]-hard with respect to the combination of *b* and $(n-x)$ for all $k \ge 1$. Furthermore, we present two algorithms; one that solves *COLLAPSED k-CORE* with $k=1$ and one for the $k=2$ case. Both algorithms run in single exponential linear FPT-time with respect to the parameter combination $(b+x)$.

We first give a parameterized reduction from *CLIQUE* to *COLLAPSED k-CORE*. Note that since this hardness result holds for the combination of *b* and the dual parameter of *x*, it is incomparable to Theorem 3 even for $k \ge 3$.

**► Proposition 4 (*)**. *COLLAPSED k-CORE is W[1]-hard when parameterized by the combination of b and $(n-x)$ for all $k \ge 1$, even if the input graph is bipartite and $\max\{2, k\}$-degenerate.*

**Proof.** We reduce from W[1]-hard problem *CLIQUE* [9], where given a graph $G = (V, E)$ and an integer $p$, the task is to decide whether $G$ contains a clique of size at least $p$. Let $(G, p)$ be an instance of *CLIQUE* and $k$ be a given constant. We build an instance $(G', b, x, k)$ of *COLLAPSED k-CORE* as follows. We can assume that $p \le |V(G')|$, as otherwise we can output a trivial no-instance. We further assume that each vertex of $G$ has degree at least $p+1$. Vertex of degree less than $p-1$ is not part of a clique of size at least $p$, while for all vertices of degree $p-1$ or $p$ we can check in $O(n \cdot p^3)$ time whether there is a clique of size at least $p$ containing any of them.

We let $V(G') = V \cup U \cup W$, where $V = V(G)$ are the vertices of $G$, $U = \{u_e^i \mid e \in E, i \in \{1, \dots, k\}\}$, and $W = \{w_e^i \mid e \in E, i \in \{1, \dots, k-1\}\}$. We also let $E(G') = E_U \cup E_W$, where $E_U = \{(v, u_e^i) \mid e \in E, i \in \{1, \dots, k\}, v \in e\}$, and $E_W = \{\{u_e^i, w_e^{i'}\} \mid e \in E, i \in \{1, \dots, k\}, i' \in \{1, \dots, k-1\}\}$. We actually only introduce the sets $W$ and $E_W$ if $k \ge 2$.

Finally we set $b=p$ and $x=n - (p + (2k-1)(\binom{p}{2}))$, where $n = |V(G')|$ is the number of vertices of graph $G'$.

<footnote n="6">⁶ Theorem 1 states NP-hardness of r-DEGENERATE VERTEX DELETION for $r \ge 2$. Recall that for $r = 1$ r-DEGENERATE VERTEX DELETION is equivalent to FEEDBACK VERTEX SET and for $r = 0$ it is equivalent to VERTEX COVER, both of which are known to be NP-hard [12].</footnote>
**Algorithm 1:** Algorithm for COLLAPSED *k*-CORE with *k* = 1.

1. `SOLVEREC(G, S, Q, b, x)`

2. **if** $|S| > b$ or $|Q| > b + x$ **then return** No solution;

3. Let $G'$ be the 1-core of $G \setminus S$.

4. **if** $|V(G')| \le x$ **then return** $S$;

5. **if** $V(G') \subseteq Q$ **then return** No solution;

6. Let $v$ be the vertex with the highest degree in $G'$ which is not in $Q$

7. $T \leftarrow SOLVEREC(G, S \cup \{v\}, Q, b, x)$

8. **if** $T \neq$ **No solution** **then return** $T$;

9. **else return** `SOLVEREC(G, S, Q \cup \{v\}, b, x)`;

We claim that $(G', b, x, k)$ is a yes-instance of COLLAPSED $k$-CORE if and only if $(G, p)$ is a yes-instance of CLIQUE. We defer the proof of this claim to a full version [18]. ▶

Now we proceed with the algorithm for COLLAPSED $k$-CORE with $k=1$. While there is a simple algorithm with $O(3^{x+b}(m+n))$ running time$^7$ for this case, we consider an algorithm with the slightly worse running time as stated, since we then generalize this algorithm to the case $k=2$ with some modifications.

**Proposition 5 (★).** COLLAPSED $k$-CORE with $k=1$ can be solved in $O(2^{x+2b}(m+n))$ time and in $O(2^{O(b+\sqrt{bx})} \cdot n)$ time. Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for COLLAPSED $k$-CORE with $k=1$, for any function $f$.

**Algorithm:** We present a recursive algorithm (see Algorithm 1 for pseudocode) that maintains two sets $S$ and $Q$. The recursive function is supposed to return a solution to the instance, whenever there is a solution $B$ containing all of $S$ and there is no solution containing $S$ and anything of $Q$. If some of the conditions is not met, then the function should return "No solution". In other words, $S$ is the set of deleted vertices and $Q$ is the set of vertices the algorithm has decided not to delete in the previous steps but may be collapsed in the future. Hence, the solution to the instance, or the information that there is none, is obtained by calling the recursive function with both sets $S$ and $Q$ empty.

The correctness proof and running time analysis of Algorithm 1 is deferred to a full version [18]. In the remainder of the section, we show how to adapt this algorithm for COLLAPSED $k$-CORE with $k=2$.

**Theorem 6.** COLLAPSED $k$-CORE with $k=2$ can be solved in $O(1.755^{x+4b} \cdot n)$ time and in $O(2^{O(b+\sqrt{bx})} \cdot n)$ time. Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for COLLAPSED $k$-CORE with $k=2$, for any function $f$.

The above theorem in particular yields an $O(9.487^b \cdot n)$ algorithm for FEEDBACK VERTEX SET.

**Algorithm:** Our algorithm for $k=2$ is similar to Algorithm 1 with two main differences (see Algorithm 2 for pseudocode). First $|Q| > b+x$ is replaced by $|Q| > 3b+x$. Second when selecting the maximum degree vertex from $V(G') \setminus Q$, we need to make sure that this vertex

<footnote>$^7$ An informal description of the algorithm: We use an initially empty set $X$ that should contain vertices of the remaining 1-core. We branch over edges where both endpoints are not in $X$ and either remove one of the endpoints or put both endpoint into $X$. Then we branch over all edges that have exactly one endpoint in $X$ and either remove the other endpoint or put the other endpoint into $X$ as well.</footnote>
**Algorithm 1:** Algorithm for COLLAPSED *k*-CORE with *k* = 1.

1. `SOLVEREC(G, S, Q, b, x)`

2. **if** $|S| > b$ or $|Q| > b + x$ **then return** No solution;

3. Let $G'$ be the 1-core of $G \setminus S$.

4. **if** $|V(G')| \le x$ **then return** $S$;

5. **if** $V(G') \subseteq Q$ **then return** No solution;

6. Let $v$ be the vertex with the highest degree in $G'$ which is not in $Q$

7. $T \leftarrow SOLVEREC(G, S \cup \{v\}, Q, b, x)$

8. **if** $T \ne$ **No solution** **then return** $T$;

9. **else return** `SOLVEREC(G, S, Q \cup \{v\}, b, x)`;

We claim that $(G', b, x, k)$ is a yes-instance of COLLAPSED $k$-CORE if and only if $(G, p)$ is a yes-instance of CLIQUE. We defer the proof of this claim to a full version [18]. ▶

Now we proceed with the algorithm for COLLAPSED $k$-CORE with $k=1$. While there is a simple algorithm with $O(3^{x+b}(m+n))$ running time$^7$ for this case, we consider an algorithm with the slightly worse running time as stated, since we then generalize this algorithm to the case $k=2$ with some modifications.

**Proposition 5 (★).** *COLLAPSED $k$-CORE with $k=1$ can be solved in $O(2^{x+2b}(m+n))$ time and in $O(2^{O(b+\sqrt{bx})} \cdot n)$ time. Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for COLLAPSED $k$-CORE with $k=1$, for any function $f$.*

**Algorithm:** We present a recursive algorithm (see Algorithm 1 for pseudocode) that maintains two sets $S$ and $Q$. The recursive function is supposed to return a solution to the instance, whenever there is a solution $B$ containing all of $S$ and there is no solution containing $S$ and anything of $Q$. If some of the conditions is not met, then the function should return "No solution". In other words, $S$ is the set of deleted vertices and $Q$ is the set of vertices the algorithm has decided not to delete in the previous steps but may be collapsed in the future. Hence, the solution to the instance, or the information that there is none, is obtained by calling the recursive function with both sets $S$ and $Q$ empty.

The correctness proof and running time analysis of Algorithm 1 is deferred to a full version [18]. In the remainder of the section, we show how to adapt this algorithm for COLLAPSED $k$-CORE with $k=2$.

**Theorem 6.** *COLLAPSED $k$-CORE with $k=2$ can be solved in $O(1.755^{x+4b} \cdot n)$ time and in $O(2^{O(b+\sqrt{bx})} \cdot n)$ time. Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for COLLAPSED $k$-CORE with $k=2$, for any function $f$.*

The above theorem in particular yields an $O(9.487^b \cdot n)$ algorithm for FEEDBACK VERTEX SET.

**Algorithm:** Our algorithm for $k=2$ is similar to Algorithm 1 with two main differences (see Algorithm 2 for pseudocode). First $|Q| > b+x$ is replaced by $|Q| > 3b+x$. Second when selecting the maximum degree vertex from $V(G') \setminus Q$, we need to make sure that this vertex

<footnote>$^7$ An informal description of the algorithm: We use an initially empty set $X$ that should contain vertices of the remaining 1-core. We branch over edges where both endpoints are not in $X$ and either remove one of the endpoints or put both endpoint into $X$. Then we branch over all edges that have exactly one endpoint in $X$ and either remove the other endpoint or put the other endpoint into $X$ as well.</footnote>
<caption>**Algorithm 2:** Algorithm for COLLAPSED k-CORE with $k = 2$.</caption>

1. **SOLVE REC2**($G, S, Q, b, x$)
2.   **if** $|S| > b$ or $|Q| > 3b + x$ **then return** No solution;
3.   Let $G'$ be the 2-core of $G \setminus S$.
4.   **if** $|V(G')| \le x$ **then return** $S$;
5.   **if** $V(G') \subseteq Q$ **then return** No solution;
6.   Let $v$ be the vertex with the highest degree in $G'$ which is not in $Q$.
7.   **if** $\deg_{G'}(v) \le 2$ **then**
8.     Let $C_1, \dots, C_r$ be the connected components of $G'$ not containing vertices of $Q$, ordered such that $|V(C_1)| \ge |V(C_2)| \ge \dots \ge |V(C_r)|$;
9.     Let $r' \leftarrow \min\{r, b - |S|\}$;
10.    **if** $|V(G')| - \sum_{i=1}^{r'} |V(C_i)| \le x$ **then**
11.      **for** $i = 1, \dots, r'$ **do** Select an arbitrary vertex from $C_i$ and add it to $S$;
12.      **return** $S$
13.    **end**
14.    **else return** No solution;
15. **end**
16. $T \leftarrow \text{SOLVE REC2}(G, S \cup \{v\}, Q, b, x)$;
17. **if** $T \ne$ No solution **then return** $T$;
18. **else return** $\text{SOLVE REC2}(G, S, Q \cup \{v\}, b, x)$;

has degree greater than 2. Otherwise, either we can directly select vertices from $V(G') \setminus Q$ to break cycles in $G'$ and get a 2-core of size at most $x$, or the algorithm rejects this branch.
We start by claiming that Algorithm 2 has the following running time.

**Lemma 7** (⋆). *Algorithm 2 runs in $O(1.755^{x+4b} \cdot n)$ time and in $O(2^{O(b+\sqrt{bx})} \cdot n)$ time.*

Next we claim the following conditional lower bound on the running time for any algorithm for `COLLAPSED k-CORE` with $k = 2$.

**Lemma 8** (⋆). *Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for `COLLAPSED k-CORE` with $k = 2$, for any function $f$.*

Before showing the correctness of Algorithm 2, we give the following lemmata which will be helpful in the correctness proof. The following lemma claims that, except for some specific connected components, we can limit the solution to contain vertices of degree at least three.

**Lemma 9** (⋆). *For any instance $(G, b, x, 2)$ of `COLLAPSED k-CORE` with $k = 2$, where $G$ is a 2-core and does not contain a cycle as a connected component, if there is a solution $B$ for $(G, b, x, 2)$, then there is also a solution $B'$ for $(G, b, x, 2)$ which contains only vertices with degree larger than 2.*

The next lemma helps to show that line 14 is correct.

**Lemma 10** (⋆). *If line 14 of Algorithm 2 applies, and for every $q \in Q$ there no solution containing whole $S \cup \{Q\}$, then there is no solution containing the whole $S$.*

Next, we show that the second part of line 2 of Algorithm 2 is correct.

**Lemma 11.** *If $Q$ is of size more than $3b+x$, then there is no solution containing whole $S$ and no vertex from $Q$.*
<caption>**Algorithm 2:** Algorithm for COLLAPSED k-CORE with $k = 2$.</caption>

1. **SOLVE REC2**(*G*, *S*, *Q*, *b*, *x*)
2.   **if** |*S*| > *b* or |*Q*| > 3*b* + *x* **then return** No solution;
3.   Let *G'* be the 2-core of *G* \ *S*.
4.   **if** |*V*(*G'*)| ≤ *x* **then return** *S*;
5.   **if** *V*(*G'*') ⊆ *Q* **then return** No solution;
6.   Let *v* be the vertex with the highest degree in *G'* which is not in *Q*
7.   **if** deg<sub>*G'*</sub>(*v*) ≤ 2 **then**
8.     Let *C*₁, ..., *C*<sub>*r*</sub> be the connected components of *G'* not containing vertices of *Q*,
        ordered such that |*V*(*C*₁)| ≥ |*V*(*C*₂)| ≥ ... ≥ |*V*(*C*<sub>*r*</sub>)|;
9.     Let *r'* ← min{*r*, *b* − |*S*|};
10.    **if** |*V*(*G'*')| − ∑<sub>*i*=1</sub><sup>*r'*</sup> |*V*(*C*<sub>*i*</sub>)| ≤ *x* **then**
11.      **for** *i* = 1, ..., *r'* **do** Select an arbitrary vertex from *C*<sub>*i*</sub> and add it to *S*;
12.      **return** *S*
13.    **end**
14.   **else return** No solution;
15. **end**
16. **T** ← **SOLVE REC2**(*G*, *S* ∪ {*v*}, *Q*, *b*, *x*);
17. **if** T ≠ No solution **then return** *T*;
18. **else return** **SOLVE REC2**(*G*, *S*, *Q* ∪ {*v*}, *b*, *x*);

has degree greater than 2. Otherwise, either we can directly select vertices from $V(G') \setminus Q$
to break cycles in $G'$ and get a 2-core of size at most $x$, or the algorithm rejects this branch.
We start by claiming that Algorithm 2 has the following running time.

► **Lemma 7** (⋆). *Algorithm 2 runs in* $O(1.755^{x+4b} \cdot n)$ *time and in* $O(2^{O(b+\sqrt{bx})} \cdot n)$ *time.*

Next we claim the following conditional lower bound on the running time for any algorithm
for `COLLAPSED k-CORE` with `k = 2`.

► **Lemma 8** (⋆). Assuming the Exponential Time Hypothesis, there is no $2^{o(b) \cdot f(x)} n^{O(1)}$ time algorithm for `COLLAPSED k-CORE` with $k = 2$, for any function $f$.

Before showing the correctness of Algorithm 2, we give the following lemmata which will
be helpful in the correctness proof. The following lemma claims that, except for some specific
connected components, we can limit the solution to contain vertices of degree at least three.

► **Lemma 9** (⋆). For any instance (*G*, *b*, *x*, 2) of **COLLAPSED k-CORE** with *k* = 2, where *G* is a 2-core and does not contain a cycle as a connected component, if there is a solution *B* for (*G*, *b*, *x*, 2), then there is also a solution *B'* for (*G*, *b*, *x*, 2) which contains only vertices with degree larger than 2.

The next lemma helps to show that line 14 is correct.

► **Lemma 10** (⋆). If line 14 of Algorithm 2 applies, and for every $q \in Q$ there no solution containing whole $S \cup \{Q\}$, then there is no solution containing the whole $S$.

Next, we show that the second part of line 2 of Algorithm 2 is correct.

► **Lemma 11.** If *Q* is of size more than 3*b* + *x*, then there is no solution containing whole *S* and no vertex from *Q*.
<figure><img src="image_47.png" /><figcaption>■ **Figure 1** Illustration of function *f*. Vertices in *Q* are separated into two parts: gray vertices from *X* and blue vertices from *Q'* = *Q* \ *X*. Every vertex in *S* is mapped to a set of three consecutive blue vertices in *Q'* from the right to the left. Graph *G*<sub>*j*<sub>0</sub></sub> with the property that *i* > max{*j* | *j* ∈ *f*(*i*)} for every *i* with *v*<sub>*i*</sub> ∈ *B* ∩ *V*(*G*<sub>*j*<sub>0</sub></sub>) is contained in the green box.</figcaption></figure>

**Proof.** Suppose for contradiction that there is a set $\mathcal{Q}$ of size at least $3b + x + 1$ and a solution $\mathcal{B}$ such that $|\mathcal{B}| \le b$, $\mathcal{S} \subseteq \mathcal{B}$ and $\mathcal{B} \cap \mathcal{Q} = \emptyset$. Let $v_1, v_2, \dots, v_{r'}$ be the vertices of the set $\mathcal{S} \cup \mathcal{Q}$ in the order as they were added to the set by successive recursive calls. Moreover, if $\mathcal{B} \setminus \mathcal{S}$ is empty, then let $r = r'$. Otherwise, let $\mathcal{B} \setminus \mathcal{S} = \{v_{r'+1}, \dots, v_r\}$, i.e., in both cases $\{v_1, \dots, v_r\} = \mathcal{B} \cup \mathcal{Q}$. Without loss of generality, we can assume that for every vertex $v_i \in \mathcal{B}$, $v_i$ is contained in the 2-core of $\mathcal{G} \setminus (\mathcal{B} \cap \{v_1, v_2, \dots, v_{i-1}\})$, since otherwise $v_i$ must come from $\mathcal{B} \setminus \mathcal{S}$, then $\mathcal{B}' = \mathcal{B} \setminus \{v_i\}$ is also a solution such that $|\mathcal{B}'| \le b$, $\mathcal{S} \subseteq \mathcal{B}'$ and $\mathcal{B}' \cap \mathcal{Q} = \emptyset$. Let $\mathcal{G}'$ be the 2-core of $\mathcal{G} \setminus \mathcal{B}$ and let $\mathcal{X} = \mathcal{V}(\mathcal{G}') \cap \mathcal{Q}$. Since $\mathcal{B}$ is a solution, we know that $|\mathcal{X}| \le x$.

We construct a function $f$ that maps every vertex of $\mathcal{B}$ to a set of three consecutive vertices of $\mathcal{Q} \setminus \mathcal{X}$ (see also Figure 1). First let $v_i$ be the vertex in $\mathcal{B}$ with the largest $i$. We let $f(i)$ be the set $\{j_1, j_2, j_3\}$, where $j_1 = \max\{j | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$, $j_2 = \max\{j < j_1 | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$, and $j_3 = \max\{j < j_2 | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$. Now let $v_i$ be the vertex from $\mathcal{B}$ with the largest $i$ such that $f(i)$ was not set yet and $v_{i'}$ be the vertex from $\mathcal{B}$ with the least $i'$ such that $i' > i$. We set $f(i) = \{j_1, j_2, j_3\}$, where $j_1 = \max\{j < \min\{k \in f(i')\} | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$, $j_2 = \max\{j < j_1 | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$, and $j_3 = \max\{j < j_2 | v_j \in \mathcal{Q} \setminus \mathcal{X}\}$. Since the set $\mathcal{Q} \setminus \mathcal{X}$ contains at least $3b+1$ vertices, while $\mathcal{B}$ contains at most $b$, this way we find a mapping for every vertex in $\mathcal{B}$, keeping the images of different vertices disjoint. Moreover, denote $p = |\mathcal{Q} \setminus \mathcal{X}| - 3|\mathcal{B}| \ge 1$. There remains $p$ vertices in $\mathcal{Q} \setminus \mathcal{X}$ not being in the union of images of $f$, let us denote them $v_{q_1}, \dots, v_{q_p}$.

For $t \in \{1, \dots, r\}$ let $G_t$ be the 2-core of the graph $\mathcal{G} \setminus (\mathcal{B} \cap \{v_1, \dots, v_{t-1}\})$. For $v \in \mathcal{V}(G_t)$ let $\deg_t(v)$ be the degree of the vertex $v$ in $G_t$. By the way we selected $v_t$ we again know that $\deg_t(v_t) \ge \deg_t(v_{t'}) \ge \deg_{t'}(v_{t'})$ for every $t < t' \le r'$ and $\deg_t(v_t) \ge \deg_t(v_{t'}) \ge \deg_{t'}(v_{t'})$ for every $t \le r' < t'$. Note also that $\deg_t(v_t) \ge 3$ for all $v_t \in \mathcal{Q}$.

If for every vertex $v_i \in \mathcal{B}$ we have $i > \max\{j | j \in f(i)\}$, then $\deg_t(v_i) \le \deg_j(v_j)$ for vertex $v_i$ in $\mathcal{B}$ and every $j \in f(i)$. Together with $\deg_t(v_t) \ge 3$ for all $v_t \in \mathcal{Q}$, we have $\deg_i(v_i) - \sum_{j \in f(i)} \deg_j(v_j) + 6 \le 0$ for every vertex $v_i$ in $\mathcal{B}$. Let $V = B \uplus Q' \uplus X \uplus Y \uplus Z$, where $Q' = \mathcal{Q} \setminus \mathcal{X}$, $Y$ is the set of collapsed vertices not contained in $\mathcal{Q}$ and $Z = \mathcal{V}(G') \setminus \mathcal{X}$ the part of the core of $\mathcal{G} \setminus \mathcal{B}$ not in $\mathcal{Q}$. Now we transform graph $\mathcal{G}$ into a partial directed graph by considering the collapsing process (see also Figure 2). More precisely, for every edge in $\mathcal{G}$, except for edges which have two endpoints in $X \cup Z$, we will assign it a direction. To this end, we just need to give an order of vertices in $V(\mathcal{G}) \setminus (X \cup Z)$. We define this order based on the time vertices being deleted or collapsed. It may happen that several vertices in $Q'$ or $Y$ collapse at the same time. For this situation, we just order these vertices according to an arbitrary but fixed order. Since $k=2$, every collapsed vertex in $Q' \cup Y$ has at most one outgoing edge. Let us consider the number, denoted by $N$, of edges of the form $\overrightarrow{v_iv_j}$ such that the head $v_j$ is in $Q'$. Since every vertex in $Q'$ has at most one outgoing edge, we have $N \ge \sum_{v_j \in Q'} \deg_j(v_j) - |Q'|$.
<figure><img src="image_50.png" /><figcaption>■ **Figure 1** Illustration of function *f*. Vertices in *Q* are separated into two parts: gray vertices from *X* and blue vertices from *Q'* = *Q* \ *X*. Every vertex in *S* is mapped to a set of three consecutive blue vertices in *Q'* from the right to the left. Graph *G*<sub>*j*<sub>0</sub></sub> with the property that *i* > max{*j* | *j* ∈ *f*(*i*)} for every *i* with *v*<sub>*i*</sub> ∈ *B* ∩ *V*(*G*<sub>*j*<sub>0</sub></sub>) is contained in the green box.</figcaption></figure>

**Proof.** Suppose for contradiction that there is a set $\mathcal{Q}$ of size at least $3b + x + 1$ and a solution $\mathcal{B}$ such that $|\mathcal{B}| \le b$, $\mathcal{S} \subseteq \mathcal{B}$ and $\mathcal{B} \cap \mathcal{Q} = \emptyset$. Let $v_1, v_2, \dots, v_{r'}$ be the vertices of the set $\mathcal{S} \cup \mathcal{Q}$ in the order as they were added to the set by successive recursive calls. Moreover, if $\mathcal{B} \setminus \mathcal{S}$ is empty, then let $r = r'$. Otherwise, let $\mathcal{B} \setminus \mathcal{S} = \{v_{r'+1}, \dots, v_r\}$, i.e., in both cases $\{v_1, \dots, v_r\} = \mathcal{B} \cup \mathcal{Q}$. Without loss of generality, we can assume that for every vertex $v_i \in \mathcal{B}$, $v_i$ is contained in the 2-core of $\mathcal{G} \setminus (\mathcal{B} \cap \{v_1, v_2, \dots, v_{i-1}\})$, since otherwise $v_i$ must come from $\mathcal{B} \setminus \mathcal{S}$, then $\mathcal{B}' = \mathcal{B} \setminus \{v_i\}$ is also a solution such that $|\mathcal{B}'| \le b$, $\mathcal{S} \subseteq \mathcal{B}'$ and $\mathcal{B}' \cap \mathcal{Q} = \emptyset$. Let $\mathcal{G}'$ be the 2-core of $\mathcal{G} \setminus \mathcal{B}$ and let $\mathcal{X} = \mathcal{V}(\mathcal{G}') \cap \mathcal{Q}$. Since $\mathcal{B}$ is a solution, we know that $|\mathcal{X}| \le x$.

We construct a function *f* that maps every vertex of *B* to a set of three consecutive vertices of *Q* \ *X* (see also Figure 1). First let *v*ᵢ be the vertex in *B* with the largest *i*. We let *f*(*i*) be the set {*j*₁, *j*₂, *j*₃}, where *j*₁ = max{*j* | *v*ⱼ ∈ *Q* \ *X*}, *j*₂ = max{*j* < *j*₁ | *v*ⱼ ∈ *Q* \ *X*}, and *j*₃ = max{*j* < *j*₂ | *v*ⱼ ∈ *Q* \ *X*}. Now let *v*ᵢ be the vertex from *B* with the largest *i* such that *f*(*i*) was not set yet and *v*ᵢ' be the vertex from *B* with the least *i*' such that *i*' > *i*. We set *f*(*i*) = {*j*₁, *j*₂, *j*₃}, where *j*₁ = max{*j* < min{*k* ∈ *f*(*i*)} | *v*ⱼ ∈ *Q* \ *X*}, *j*₂ = max{*j* < *j*₁ | *v*ⱼ ∈ *Q* \ *X*}, and *j*₃ = max{*j* < *j*₂ | *v*ⱼ ∈ *Q* \ *X*. Since the set *Q* \ *X* contains at least 3*b* + 1 vertices, while *B* contains at most *b*, this way we find a mapping for every vertex in *B*, keeping the images of different vertices disjoint. Moreover, denote *p* = |*Q* \ *X* - 3|*B*| ≥ 1. There remains *p* vertices in *Q* \ *X* not being in the union of images of *f*, let us denote them *v*₁*,..., *v*ₚ*.

For $t \in \{1, \dots, r\}$ let $G_t$ be the 2-core of the graph $G \setminus (B \cap \{v_1, \dots, v_{t-1}\})$. For $v \in V(G_t)$ let $\deg_t(v)$ be the degree of the vertex $v$ in $G_t$. By the way we selected $v_t$ we again know that $\deg_t(v_t) \ge \deg_t(v_{t'}) \ge \deg_{t'}(v_{t'})$ for every $t < t' \le r'$ and $\deg_t(v_t) \ge \deg_t(v_{t'}) \ge \deg_{t'}(v_{t'})$ for every $t \le r' < t'$. Note also that $\deg_t(v_t) \ge 3$ for all $v_t \in Q$.

If for every vertex $v_i \in B$ we have $i > \max\{j | j \in f(i)\}$, then $\deg_t(v_i) \le \deg_j(v_j)$ for vertex $v_i$ in $B$ and every $j \in f(i)$. Together with $\deg_t(v_t) \ge 3$ for all $v_t \in Q$, we have $\deg_i(v_i) - \sum_{j \in f(i)} \deg_j(v_j) + 6 \le 0$ for every vertex $v_i$ in $B$. Let $V = B \uplus Q' \uplus X \uplus Y \uplus Z$, where $Q' = Q \setminus X$, $Y$ is the set of collapsed vertices not contained in $Q$ and $Z = V(G') \setminus X$ the part of the core of $G \setminus B$ not in $Q$. Now we transform graph $G$ into a partial directed graph by considering the collapsing process (see also Figure 2). More precisely, for every edge in $G$, except for edges which have two endpoints in $X \cup Z$, we will assign it a direction. To this end, we just need to give an order of vertices in $V(G) \setminus (X \cup Z)$. We define this order based on the time vertices being deleted or collapsed. It may happen that several vertices in $Q'$ or $Y$ collapse at the same time. For this situation, we just order these vertices according to an arbitrary but fixed order. Since $k=2$, every collapsed vertex in $Q' \cup Y$ has at most one outgoing edge. Let us consider the number, denoted by $N$, of edges of the form $\overrightarrow{v_iv_j}$ such that the head $v_j$ is in $Q'$. Since every vertex in $Q'$ has at most one outgoing edge, we have $N \ge \sum_{v_j \in Q'} \deg_j(v_j) - |Q'|$.
<figure><img src="image_48.png" /><figcaption>■ **Figure 2** Illustration of the partial directed graph when considering the collapsing process. The set $B$ contains the deleted vertices and $X$ is the set of vertices remaining in the 2-core of $G \setminus B$. The set $Q'$ contains vertices the algorithm has decided not to delete but eventually collapse and $Y$ is the set of other collapsed vertices.</figcaption></figure>

On the other hand, let

- $N_{\overrightarrow{BQ'}}$ be the number of edges going from $B$ to $Q'$;

- $N_{\overrightarrow{BY}}$ be the number of edges going from $B$ to $Y$;

- $N_{\overrightarrow{YQ'}}$ be the number of edges going from $Y$ to $Q'$;

- $N_{\overrightarrow{Q'Y}}$ be the number of edges going from $Q'$ to $Y$.

We claim that $N_{\overrightarrow{YQ'}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}}$. To show that, denote the number of edges in $G[Y]$ by $N_{\overrightarrow{YY}}$. Since every vertex in $Y$ has at least one incoming edge but at most one outgoing edge, we have $\sum_{v \in Y} \deg^{-}(v) \le \sum_{v \in Y} \deg^{+}(v)$, where $\deg^{+}(v) (\deg^{-}(v))$ is the number of incoming (outgoing) edges of vertex $v$ in $G$, respectively. This means $N_{\overrightarrow{YQ'}} + N_{\overrightarrow{YY}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}} + N_{\overrightarrow{YY}}$, therefore, $N_{\overrightarrow{YQ'}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}}$, finishing the proof of the claim.

Since the edges which have their heads in $Q'$ have their tails from $B \cup Y \cup Q'$,

$$ 
\begin{aligned}
N &\le N_{\overrightarrow{BQ'}} + N_{\overrightarrow{YQ'}} + (|Q'| - N_{\overrightarrow{Q'Y}}) \le N_{\overrightarrow{BQ'}} + |Q'| + N_{\overrightarrow{BY}} \\
  &\le \sum_{v_i \in B} \deg^{-}(v_i) + |Q'| \le \sum_{v_i \in B} \deg_{i}(v_i) + |Q'|.
\end{aligned}
$$

The last inequality holds since for every vertex $v_i \in B$, $v_i$ is contained in the 2-core of $G \setminus (B \cap \{v_1, v_2, \dots, v_{i-1}\})$, which means all outgoing edges of $v_i$ are counted in $\deg_i(v_i)$. Then we have that $\sum_{v_i \in B} \deg^{-}(v_i) \le \sum_{v_i \in B} \deg_i(v_i)$.

$$ 
\begin{aligned}
0 &\le \sum_{v_i \in B} \deg_i(v_i) + |Q'| - \left( \sum_{v_j \in Q'} \deg_j(v_j) - |Q'| \right) \\
&= \sum_{v_i \in B} \deg_i(v_i) - \sum_{v_j \in Q'} (\deg_j(v_j) - 2) \\
&\le \sum_{v_i \in B} \deg_i(v_i) - \left( \sum_{v_i \in B} \sum_{j \in f(i)} (\deg_j(v_j) - 2) + \sum_{i=1}^{p} (\deg_{q_i}(v_{q_i}) - 2) \right) \\
&< \sum_{v_i \in B} \deg_i(v_i) - \sum_{v_i \in B} \sum_{j \in f(i)} (\deg_j(v_j) - 2) \\
&= \sum_{v_i \in B} \left( \deg_i(v_i) - \sum_{j \in f(i)} \deg_j(v_j) + 6 \right) \le 0
\end{aligned}
$$

which is a contradiction.

The remaining case where there exist a $i$ such that $i < \max\{j | j \in f(i)\}$ is analogous and deferred to a full version [18]. ▴
<figure><img src="image_51.png" /><figcaption>■ **Figure 2** Illustration of the partial directed graph when considering the collapsing process. The set $B$ contains the deleted vertices and $X$ is the set of vertices remaining in the 2-core of $G \setminus B$. The set $Q'$ contains vertices the algorithm has decided not to delete but eventually collapse and $Y$ is the set of other collapsed vertices.</figcaption></figure>

On the other hand, let

- $N_{\overrightarrow{BQ'}}$ be the number of edges going from $B$ to $Q'$;

- $N_{\overrightarrow{BY}}$ be the number of edges going from $B$ to $Y$;

- $N_{\overrightarrow{YQ'}}$ be the number of edges going from $Y$ to $Q'$;

- $N_{\overrightarrow{Q'Y}}$ be the number of edges going from $Q'$ to $Y$.

We claim that $N_{\overrightarrow{YQ'}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}}$. To show that, denote the number of edges in $G[Y]$ by $N_{\overrightarrow{YY}}$. Since every vertex in $Y$ has at least one incoming edge but at most one outgoing edge, we have $\sum_{v \in Y} \deg^{-}(v) \le \sum_{v \in Y} \deg^{+}(v)$, where $\deg^{+}(v) (\deg^{-}(v))$ is the number of incoming (outgoing) edges of vertex $v$ in $G$, respectively. This means $N_{\overrightarrow{YQ'}} + N_{\overrightarrow{YY}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}} + N_{\overrightarrow{YY}}$, therefore, $N_{\overrightarrow{YQ'}} \le N_{\overrightarrow{BY}} + N_{\overrightarrow{Q'Y}}$, finishing the proof of the claim.

Since the edges which have their heads in $Q'$ have their tails from $B \cup Y \cup Q'$,

$$ 
\begin{aligned}
N &\le N_{\overrightarrow{BQ'}} + N_{\overrightarrow{YQ'}} + (|Q'| - N_{\overrightarrow{Q'Y}}) \le N_{\overrightarrow{BQ'}} + |Q'| + N_{\overrightarrow{BY}} \\
&\le \sum_{v_i \in B} \deg^{-}(v_i) + |Q'| \le \sum_{v_i \in B} \deg_{i}(v_i) + |Q'|.
\end{aligned}
$$

The last inequality holds since for every vertex $v_i \in B$, $v_i$ is contained in the 2-core of $G \setminus (B \cap \{v_1, v_2, \dots, v_{i-1}\})$, which means all outgoing edges of $v_i$ are counted in $\deg_i(v_i)$. Then we have that $\sum_{v_i \in B} \deg^{-}(v_i) \le \sum_{v_i \in B} \deg_i(v_i)$.

$$ 
\begin{aligned}
0 &\le \sum_{v_i \in B} \deg_i(v_i) + |Q'| - \left( \sum_{v_j \in Q'} \deg_j(v_j) - |Q'| \right) \\
&= \sum_{v_i \in B} \deg_i(v_i) - \sum_{v_j \in Q'} (\deg_j(v_j) - 2) \\
&\le \sum_{v_i \in B} \deg_i(v_i) - \left( \sum_{v_i \in B} \sum_{j \in f(i)} (\deg_j(v_j) - 2) + \sum_{i=1}^{p} (\deg_{q_i}(v_{q_i}) - 2) \right) \\
&< \sum_{v_i \in B} \deg_i(v_i) - \sum_{v_i \in B} \sum_{j \in f(i)} (\deg_j(v_j) - 2) \\
&= \sum_{v_i \in B} \left( \deg_i(v_i) - \sum_{j \in f(i)} \deg_j(v_j) + 6 \right) \le 0
\end{aligned}
$$

which is a contradiction.

The remaining case where there exist a $i$ such that $i < \max\{j | j \in f(i)\}$ is analogous and deferred to a full version [18]. ▴
The last part of the proof of Theorem 6 is deferred to a full version [18].

# 4 Structural Graph Parameters

In this section, we investigate the parameterized complexity of COLLAPSED *k*-CORE with respect to several structural parameters of the input graph. Theorem 3 already implies hardness for constant values of several structural graph parameters. We expand this picture by observing that the problem remains NP-hard on graphs with a dominating set of size one and by showing that the problem is W[1]-hard when parameterized by the combination of *b* and the clique cover number of the input graph. On the positive side, we show that the problem is in FPT when parameterized by the treewidth of the input graph or the clique-width of the input graph and *k* combined with either *b*, *x*, *n* − *x*, or *n* − *b*. Lastly, we show that the problem presumably does not admit a polynomial kernel for any *k* ≥ 2 when parameterized by the combination of *b* and the vertex cover number of the input graph, or by the combination of *b*, *k*, and the bandwidth of the input graph.

We start with an easy observation that we will make use of in most of the hardness results
in this section.

**Observation 12 (*)**. If $(G, b, x, k)$ is an instance of COLLAPSED $k$-CORE and vertex $v$ is a part of the $(k+b)$-core of $G$, and $S \subseteq V$ is of size at most $b$, then either $v \in S$ or $v$ is part of the $k$-core of $G \setminus S$.

The following observation yields that we can reduce the size of a dominating set of any
instance of COLLAPSED *k*-CORE to one by introducing a universal vertex. Note that, for
example, this only increases the degeneracy by one.

**Observation 13 (*)**. Let $(G, b, x, k)$ be an instance of COLLAPSED $k$-CORE and $G'$ be the graph obtained from $G$ by adding a universal vertex, then $(G', b+1, x, k)$ is an equivalent instance of COLLAPSED $k$-CORE.

Considering a larger parameter than, e.g., the size of the dominating set, namely the clique
cover number<sup>8</sup>, we can show W[1]-hardness, even in combination with *b*. This can be done
with a parameterized reduction from MULTICOLORED CLIQUE parameterized by the solution
size.

**Proposition 14 (*)**. COLLAPSED *k*-CORE is W[1]-hard when parameterized by the combination of *b* and the clique cover number of the input graph.

On the positive side, we sketch a dynamic program on the tree decomposition of the
input graph *G* which implies that COLLAPSED *k*-CORE is in FPT when parameterized by
the treewidth of the input graph.

**Proposition 15 (*)**. COLLAPSED *k*-CORE is in FPT when parameterized by the treewidth of the input graph.

**Proof Sketch.** Let $(G, b, x, k)$ be an instance of COLLAPSED $k$-CORE. Observe that either $k \le \text{tw}(G)$ or the $k$-core of $G$ is (already) empty and we can answer Yes. Hence, for the rest of the proof we assume that $k \le \text{tw}(G)$. We assume that we are given a nice tree decomposition

<footnote n="8">⁸ The clique cover number of a graph *G* is the minimum number of induced cliques such that their union contains all vertices of *G*.</footnote>
The last part of the proof of Theorem 6 is deferred to a full version [18].

## 4 Structural Graph Parameters

In this section, we investigate the parameterized complexity of COLLAPSED *k*-CORE with respect to several structural parameters of the input graph. Theorem 3 already implies hardness for constant values of several structural graph parameters. We expand this picture by observing that the problem remains NP-hard on graphs with a dominating set of size one and by showing that the problem is W[1]-hard when parameterized by the combination of *b* and the clique cover number of the input graph. On the positive side, we show that the problem is in FPT when parameterized by the treewidth of the input graph or the clique-width of the input graph and *k* combined with either *b*, *x*, *n* − *x*, or *n* − *b*. Lastly, we show that the problem presumably does not admit a polynomial kernel for any *k* ≥ 2 when parameterized by the combination of *b* and the vertex cover number of the input graph, or by the combination of *b*, *k*, and the bandwidth of the input graph.

We start with an easy observation that we will make use of in most of the hardness results in this section.

**Observation 12 (*)**. If (*G*, *b*, *x*, *k*) is an instance of COLLAPSED *k*-CORE and vertex *v* is a part of the (*k* + *b*)-core of *G*, and *S* ⊆ *V* is of size at most *b*, then either *v* ∈ *S* or *v* is part of the *k*-core of *G* \ *S*.

The following observation yields that we can reduce the size of a dominating set of any instance of COLLAPSED *k*-CORE to one by introducing a universal vertex. Note that, for example, this only increases the degeneracy by one.

**Observation 13 (*)**. Let (*G*, *b*, *x*, *k*) be an instance of COLLAPSED *k*-CORE and *G'* be the graph obtained from *G* by adding a universal vertex, then (*G'*, *b* + 1, *x*, *k*) is an equivalent instance of COLLAPSED *k*-CORE.

Considering a larger parameter than, e.g., the size of the dominating set, namely the clique cover number<sup>8</sup>, we can show W[1]-hardness, even in combination with *b*. This can be done with a parameterized reduction from MULTICOLORED CLIQUE parameterized by the solution size.

**Proposition 14 (*)**. COLLAPSED *k*-CORE is W[1]-hard when parameterized by the combination of *b* and the clique cover number of the input graph.

On the positive side, we sketch a dynamic program on the tree decomposition of the input graph *G* which implies that COLLAPSED *k*-CORE is in FPT when parameterized by the treewidth of the input graph.

**Proposition 15 (*)**. COLLAPSED *k*-CORE is in FPT when parameterized by the treewidth of the input graph.

**Proof Sketch.** Let (*G*, *b*, *x*, *k*) be an instance of COLLAPSED *k*-CORE. Observe that either *k* ≤ *tw*(*G*) or the *k*-core of *G* is (already) empty and we can answer Yes. Hence, for the rest of the proof we assume that *k* ≤ *tw*(*G*). We assume that we are given a nice tree decomposition

<footnote n="8">⁸ The clique cover number of a graph *G* is the minimum number of induced cliques such that their union contains all vertices of *G*.</footnote>
7:10 A Parameterized Complexity View on Collapsing $k$-Cores

of $G$ [15, 3] and use dynamic programming on the nice tree decomposition of $G$. The indices of the table are formed for each bag of the decomposition by the number of vertices of the solution already forgotten, the number of vertices in the core already forgotten, a partition of the bag into three set $B$, $X$, and $Q$, an (elimination) order for the vertices in $Q$, and for each vertex in $Q$ the number of its neighbors in $X$ or higher in the order. This number is always in $0, \dots, k-1$, as otherwise it would not be possible to eliminate the vertex.

The set $B$ represents the partial solution (or rather its intersection with the bag), i.e., the vertices to be deleted. The set $X$ represents the vertices which (are free to) remain in the core. The vertices in $Q$ should collapse after removing the vertices of the solution and the collapse of the vertices preceding them in the order.

There are $3^{\mathrm{tw}(G)} \cdot (\mathrm{tw}(G))^{O(\mathrm{tw}(G))} \cdot k^{\mathrm{tw}(G)} = (\mathrm{tw}(G))^{O(\mathrm{tw}(G))}$ possible indices for each bag. Hence the slightly superexponential running time of $(\mathrm{tw}(G))^{O(\mathrm{tw}(G))} \cdot n^{O(1)}$ follows. $\quad \blacksquare$

Using monadic second order (MSO) logic formulas, it can be shown that for a smaller structural parameter, namely the cliquewidth of the input graph, there are also positive results. Here however, we can only show fixed-parameter tractability for the combination of the cliquewidth of the input graph with $k$ and either $b$, $x$, $n-x$, or $n-b$.

**Proposition 16** (*). *COLLAPSED $k$-CORE is in FPT when parameterized by the cliquewidth of the input graph combined with $k$ and either $b, x, n-x$, or $n-b$.*

In the remainder of this section, we show that *COLLAPSED $k$-CORE* does not admit a polynomial kernel when parameterized by rather large parameter combinations. We first show an OR-cross composition [4, 9] from *CUBIC VERTEX COVER*.

**Theorem 17.** *For all $k \ge 2$ COLLAPSED $k$-CORE does not admit a polynomial kernel when parameterized by the combination of $b$ and the vertex cover number of the input graph unless $NP \subseteq coNP/poly$.*

**Proof.** We apply an OR-cross composition [4, 9] from the NP-hard problem CUBIC VERTEX COVER [12]. In CUBIC VERTEX COVER, we are given a 3-regular graph $G$ and an integer $s$, and the task is to find a vertex subset of size at most $s$ which contains at least one endpoint of each edge of $G$.

We say an instance of CUBIC VERTEX COVER is *malformed* if the string does not represent a pair $(G, s)$, where $G$ is a 3-regular graph and $s$ is a positive integer. It is *trivial*, if $s \ge |V(G)|$. We define the equivalence relation $\mathcal{R}$ as follows: all malformed instances are equivalent, all trivial instances are equivalent and two well-formed non-trivial instances $(G, s)$ and $(G', s')$ are $\mathcal{R}$-equivalent if $|V(G)| = |V(G')|$ and $s = s'$. Observe that $\mathcal{R}$ is a polynomial equivalence relation.

Let the input consist of $T$ $\mathcal{R}$-equivalent instances of CUBIC VERTEX COVER. If the instances are malformed or trivial, we return a constant size no- or yes- instance of COLLAPSED $k$-CORE, respectively. Let $(G_i, s)_{0 \le i \le T-1}$ be well-formed non-trivial $\mathcal{R}$-equivalent instances of CUBIC VERTEX COVER. Since all instances have the same size of the vertex set, we can assume they share the same vertex set $V = \{v_1, v_2, \dots, v_n\}$. We assume $T$ to be a power of 2, as otherwise we can duplicate some instances. Now we create an instance $(G, b, x, k)$ of COLLAPSED $k$-CORE for some arbitrary but fixed $k \ge 2$ as follows.

- Set $b = s + 2ks \log T$ and $x = N - N'$, where $N = n + \frac{3}{2}nT + 4ks \log T + k + s + \frac{3}{2}n(k-2)$ is the number of all vertices in graph $G$ we will construct and $N' = s + 2ks \log T + \frac{3}{2}n$.

- First for every vertex $v_i$ in $V$, create a vertex $v'_i$ in $G$.
7:10 A Parameterized Complexity View on Collapsing $k$-Cores

of $G$ [15, 3] and use dynamic programming on the nice tree decomposition of $G$. The indices of the table are formed for each bag of the decomposition by the number of vertices of the solution already forgotten, the number of vertices in the core already forgotten, a partition of the bag into three set $B$, $X$, and $Q$, an (elimination) order for the vertices in $Q$, and for each vertex in $Q$ the number of its neighbors in $X$ or higher in the order. This number is always in $0, \dots, k-1$, as otherwise it would not be possible to eliminate the vertex.

The set $B$ represents the partial solution (or rather its intersection with the bag), i.e., the vertices to be deleted. The set $X$ represents the vertices which (are free to) remain in the core. The vertices in $Q$ should collapse after removing the vertices of the solution and the collapse of the vertices preceding them in the order.

There are $3^{\text{tw}(G)} \cdot (\text{tw}(G))^{O(\text{tw}(G))} \cdot k^{\text{tw}(G)} = (\text{tw}(G))^{O(\text{tw}(G))}$ possible indices for each bag. Hence the slightly superexponential running time of $(\text{tw}(G))^{O(\text{tw}(G))} \cdot n^{O(1)}$ follows. $\quad \blacksquare$

Using monadic second order (MSO) logic formulas, it can be shown that for a smaller structural parameter, namely the cliquewidth of the input graph, there are also positive results. Here however, we can only show fixed-parameter tractability for the combination of the cliquewidth of the input graph with $k$ and either $b$, $x$, $n-x$, or $n-b$.

**Proposition 16** (*). *COLLAPSED $k$-CORE is in FPT when parameterized by the cliquewidth of the input graph combined with $k$ and either $b, x, n-x$, or $n-b$.*

In the remainder of this section, we show that *COLLAPSED $k$-CORE* does not admit a polynomial kernel when parameterized by rather large parameter combinations. We first show an OR-cross composition [4, 9] from *CUBIC VERTEX COVER*.

**Theorem 17.** *For all $k \ge 2$ COLLAPSED $k$-CORE does not admit a polynomial kernel when parameterized by the combination of $b$ and the vertex cover number of the input graph unless $NP \subseteq coNP/poly$.*

**Proof.** We apply an OR-cross composition [4, 9] from the NP-hard problem CUBIC VERTEX COVER [12]. In CUBIC VERTEX COVER, we are given a 3-regular graph $G$ and an integer $s$, and the task is to find a vertex subset of size at most $s$ which contains at least one endpoint of each edge of $G$.

We say an instance of CUBIC VERTEX COVER is *malformed* if the string does not represent a pair $(G, s)$, where $G$ is a 3-regular graph and $s$ is a positive integer. It is *trivial*, if $s \ge |V(G)|$. We define the equivalence relation $\mathcal{R}$ as follows: all malformed instances are equivalent, all trivial instances are equivalent and two well-formed non-trivial instances $(G, s)$ and $(G', s')$ are $\mathcal{R}$-equivalent if $|V(G)| = |V(G')|$ and $s = s'$. Observe that $\mathcal{R}$ is a polynomial equivalence relation.

Let the input consist of $T$ $\mathcal{R}$-equivalent instances of CUBIC VERTEX COVER. If the instances are malformed or trivial, we return a constant size no- or yes- instance of COLLAPSED $k$-CORE, respectively. Let $(G_i, s)_{0 \le i \le T-1}$ be well-formed non-trivial $\mathcal{R}$-equivalent instances of CUBIC VERTEX COVER. Since all instances have the same size of the vertex set, we can assume they share the same vertex set $V = \{v_1, v_2, \dots, v_n\}$. We assume $T$ to be a power of 2, as otherwise we can duplicate some instances. Now we create an instance $(G, b, x, k)$ of COLLAPSED $k$-CORE for some arbitrary but fixed $k \ge 2$ as follows.

- Set $b = s + 2ks \log T$ and $x = N - N'$, where $N = n + \frac{3}{2}nT + 4ks \log T + k + s + \frac{3}{2}n(k-2)$ is the number of all vertices in graph $G$ we will construct and $N' = s + 2ks \log T + \frac{3}{2}n$.

- First for every vertex $v_i$ in $V$, create a vertex $v'_i$ in $G$.
<figure><img src="image_49.png" /><figcaption>■ **Figure 3** Illustration of the OR-cross composition from CUBIC VERTEX COVER to COLLAPSED k-CORE with $k=5$. The selection gadget is all the circles contained in the green box. Every gray edge in this figure means that all vertices in one endpoint of this edge are connected to all vertices in the other endpoint. Every vertex in $V_i^E$ connects to two endpoints of its corresponding edge in $G_i$. For example, the yellow vertex in $V_2^E$ is connected to the blue and the red vertex in $V$, which represents the two endpoints of the corresponding edge in $G_2$. The big clique $C$ is separated into two parts. Every vertex in $V_i^E$ is connected to $k-2$ vertices in the upper part of $C$. Since $k=5$, the yellow vertex in $V_2^E$ is connected to three vertices in $C$. Vertices contained in thick outlined vertex sets form a vertex cover. To keep the picture simple, edges that contain vertices from $V_i^E$ with $i \neq 2$ are not depicted.</figcaption></figure>

- For every edge set $E(G_i)$, create a vertex set $V_i^E$ in $G$, in which a vertex $v_{p,q}$ represents an edge $v_p v_q$ in $E(G_i)$. Then we have $T$ of these vertex sets and each set has $\frac{3}{2}n$ vertices.

- For every edge $v_p v_q$ in $E(G_i)$, add 2 edges $v_{p,q}v_p$ and $v_{p,q}v_q$ in $G$.

- Now create the selection gadget in $G$. It contains $\log T$ pairs of cliques $C_i^d$ ($1 \le i \le \log T, d \in \{0,1\}$), and all of them have the same size of $2ks$. For every vertex set $V_i^E$, let $i = (d_{\log T-1}d_{\log T-2}\dots d_0)_2$ be the binary representation of the index $i$, where $d_j \in \{0,1\}$ for $0 \le j \le \log T-1$ and we add leading zeros so that the length of the representation is exactly $\log T$. We add edges between all vertices in $V_i^E$ and all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$.

- Finally we create a clique $C$ with $|C| = k+b+\frac{3}{2}n(k-2)$, which contains two parts of vertices. The first part contains $k+b$ vertices and each of them connects to all vertices in $V \cup \bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^1 C_j^d$. The second part of $\frac{3}{2}n(k-2)$ vertices is connected to vertices in $V_i^E$ in the following way. For every vertex $v_{p,q}$ in $V_i^E$, add edges between $v_{p,q}$ and $k-2$ vertices in $C$. We make sure that all vertices in the same $V_i^E$ connect to different vertices in $C$. In other words, every vertex in the second part of $C$ connects to exactly one vertex in every $V_i^E$.

Notice that the vertex cover number of $G$ is $n+4ks \log T+k+b+\frac{3}{2}n(k-2)$. The construction is illustrated in Figure 3. We now show that at least one instance $(G_i, s)$ is a yes-instance if and only if the instance $(G, b, x, k)$ of COLLAPSED k-CORE constructed above is a yes-instance.

⇒ If $(G_i, s)$ is a yes-instance, which means that there is a vertex subset $V^*$ of size $s$ that covers all edges in $G_i$, then we delete the corresponding $s$ vertices in $G$ and all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$, where $i = (d_{\log T-1} \dots d_0)_2$ is the binary representation of $i$. So far, we deleted
<figure><img src="image_52.png" /><figcaption>■ **Figure 3** Illustration of the OR-cross composition from CUBIC VERTEX COVER to COLLAPSED k-CORE with $k=5$. The selection gadget is all the circles contained in the green box. Every gray edge in this figure means that all vertices in one endpoint of this edge are connected to all vertices in the other endpoint. Every vertex in $V_i^E$ connects to two endpoints of its corresponding edge in $G_i$. For example, the yellow vertex in $V_2^E$ is connected to the blue and the red vertex in $V$, which represents the two endpoints of the corresponding edge in $G_2$. The big clique $C$ is separated into two parts. Every vertex in $V_i^E$ is connected to $k-2$ vertices in the upper part of $C$. Since $k=5$, the yellow vertex in $V_2^E$ is connected to three vertices in $C$. Vertices contained in thick outlined vertex sets form a vertex cover. To keep the picture simple, edges that contain vertices from $V_i^E$ with $i \neq 2$ are not depicted.</figcaption></figure>

- For every edge set $E(G_i)$, create a vertex set $V_i^E$ in $G$, in which a vertex $v_{p,q}$ represents an edge $v_p v_q$ in $E(G_i)$. Then we have $T$ of these vertex sets and each set has $\frac{3}{2}n$ vertices.

- For every edge $v_p v_q$ in $E(G_i)$, add 2 edges $v_{p,q}v_p$ and $v_{p,q}v_q$ in $G$.

- Now create the selection gadget in $G$. It contains $\log T$ pairs of cliques $C_i^d$ ($1 \le i \le \log T, d \in \{0,1\}$), and all of them have the same size of $2ks$. For every vertex set $V_i^E$, let $i = (d_{\log T-1}d_{\log T-2}\dots d_0)_2$ be the binary representation of the index $i$, where $d_j \in \{0,1\}$ for $0 \le j \le \log T-1$ and we add leading zeros so that the length of the representation is exactly $\log T$. We add edges between all vertices in $V_i^E$ and all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$.

- Finally we create a clique $C$ with $|C| = k+b+\frac{3}{2}n(k-2)$, which contains two parts of vertices. The first part contains $k+b$ vertices and each of them connects to all vertices in $V \cup \bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^1 C_j^d$. The second part of $\frac{3}{2}n(k-2)$ vertices is connected to vertices in $V_i^E$ in the following way. For every vertex $v_{p,q}$ in $V_i^E$, add edges between $v_{p,q}$ and $k-2$ vertices in $C$. We make sure that all vertices in the same $V_i^E$ connect to different vertices in $C$. In other words, every vertex in the second part of $C$ connects to exactly one vertex in every $V_i^E$.

Notice that the vertex cover number of $G$ is $n+4ks \log T+k+b+\frac{3}{2}n(k-2)$. The construction is illustrated in Figure 3. We now show that at least one instance $(G_i, s)$ is a yes-instance if and only if the instance $(G, b, x, k)$ of COLLAPSED k-CORE constructed above is a yes-instance.

⇒ If $(G_i, s)$ is a yes-instance, which means that there is a vertex subset $V^*$ of size $s$ that covers all edges in $G_i$, then we delete the corresponding $s$ vertices in $G$ and all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$, where $i = (d_{\log T-1}\dots d_0)_2$ is the binary representation of $i$. So far, we deleted
7:12 A Parameterized Complexity View on Collapsing k-Cores

$s + 2ks \log T$ vertices, and all vertices in $V_i^E$ will collapse, since they just have at most $k-1$ edges remaining, $k-2$ of which connect to vertices in $C$ and at most one to vertices in $V$. Therefore, the number of remaining vertices is $x$ and instance $(G, b, x, k)$ is a yes-instance.

⇔: If $(G, b, x, k)$ is a yes-instance, we need to show that there is at least one instance which has a vertex cover of size at most $s$. Let $S$ be the set of deleted vertices of size at most $b$ and let $S'$ be the set of all collapsed vertices. Since $N' = s + 2ks \log T + \frac{3}{2}n$, we have $|S'| \ge \frac{3}{2}n$. In the subgraph of $G$ induced by $V$, $C$ and $\bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^{1} C_j^d$ all vertices in $V \cup \bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^{1} C_j^d \cup C$ have degree larger than $k+b$. Hence, by Theorem 12 they will not collapse and all collapsed vertices come from $\bigcup_{i=0}^{T-1} V_i^E$.

We show that all collapsed vertices can only come from one single $V_i^E$ for some $i$. Suppose two vertices $v$ and $v'$ from different sets of $V_i^E$ ($0 \le i \le T-1$) collapse after deleting $S$, then there is at least one pair of cliques $C_{j_0}^0$ and $C_{j_0}^1$ such that $v$ is connected to all vertices in $C_{j_0}^{d_0}$ for some $d_0 \in \{0, 1\}$ and $v'$ is connected to all vertices in $C_{j_0}^{1-d_0}$. To make $v$ collapse, at least $2ks \log T - (k-1)$ vertices from the corresponding cliques in the selection gadget need to be deleted. Then to make $v'$ collapse, at least $2ks - (k-1)$ vertices from $C_{j_0}^{1-d_0}$ need to be deleted. Therefore, at least $2ks \log T + 2ks - 2(k-1)$ vertices need to be deleted, which is strictly more than $b$. This means that the collapsed vertices come from one single $V_i^E$. Since $|S'| \ge \frac{3}{2}n$ and $|V_i^E| = \frac{3}{2}n$, we have $S' = V_i^E$ and $S \cap V_i^E = \emptyset$ for some $i$.

We consider the vertex set $S$. We know that after deleting $S$, all vertices in $V_i^E$ collapse. Denote $V_I$ the vertex set of all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$, where $i = (d_{\log T-1} \dots d_0)_2$ is the binary representation of $i$. Since every vertex in $V_I$ is connected to all vertices in $V_i^E$, to make $V_i^E$ collapse, it is always better to choose vertices from $V_I$ than any other vertex. If $S$ does not contain all vertices from $V_I$, we can update $S$ by replacing any $|V_I \setminus S|$ vertices in $S$ with vertices in $V_I \setminus S$. Then $V_I \subseteq S$.

Suppose there is a vertex $v_{p,q}$ in $V_i^E$ such that both $v_p$ and $v_q$ are not in $S \cap V$, then $S$ contains at least one vertex $v_c$ in $C$ connected to $v_{p,q}$, as otherwise $v_{p,q}$ has degree at least $k$ and will not collapse. We update $S$ by replacing $v_c$ with $v_p$. This will not influence the size of $S$ and more importantly, this will not influence the collapsed set $S' = V_i^E$, since $v_c$ in $C$ is connected to only one vertex $v_{p,q}$ in $V_i^E$, and $v_{p,q}$ will still collapse under the new $S$. By updating $S$ in the same way for other vertices in $V_i^E$ not covered by vertices in $S \cap V$, we get a vertex set $S \cap V$ which covers all vertices in $V_i^E$ at least once. And $|S \cap V| \le s$, since $V_I \subseteq S$ and $|V_I| = 2ks \log T$. This corresponds to a vertex cover of size $s$ in $G_i$. $\quad$

Lastly, we claim that there is a simple OR-cross composition [4, 9] from COLLAPSED $k$-CORE onto itself. Note that the parameter combination of the following result is incomparable to that of Theorem 17.

**Proposition 18** (⋆). COLLAPSED $k$-CORE does not admit a polynomial kernel when parameterized by the combination of $b, k$, and the bandwidth of the input graph unless $NP \subseteq coNP/poly$.

**5 Conclusion**

Our results highlight a dichotomy in the computational complexity of COLLAPSED $k$-CORE for $k \le 2$ and $k \ge 3$. Along the way, we correct some inaccuracies in the literature concerning the parameterized complexity of COLLAPSED $k$-CORE with $k = 3$ and $x = 0$ and give a simple single exponential linear time parameterized algorithm for COLLAPSED $k$-CORE with $k = 2$, which almost matches the simplest known, independently found, single exponential linear time algorithm for FEEDBACK VERTEX SET. We leave as an open question whether
7:12 A Parameterized Complexity View on Collapsing k-Cores

$s + 2ks \log T$ vertices, and all vertices in $V_i^E$ will collapse, since they just have at most $k-1$ edges remaining, $k-2$ of which connect to vertices in $C$ and at most one to vertices in $V$. Therefore, the number of remaining vertices is $x$ and instance $(G, b, x, k)$ is a yes-instance.

⇔: If $(G, b, x, k)$ is a yes-instance, we need to show that there is at least one instance which has a vertex cover of size at most $s$. Let $S$ be the set of deleted vertices of size at most $b$ and let $S'$ be the set of all collapsed vertices. Since $N' = s + 2ks \log T + \frac{3}{2}n$, we have $|S'| \ge \frac{3}{2}n$. In the subgraph of $G$ induced by $V$, $C$ and $\bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^{1} C_j^d$ all vertices in $V \cup \bigcup_{j=0}^{\log T-1} \bigcup_{d=0}^{1} C_j^d \cup C$ have degree larger than $k+b$. Hence, by Theorem 12 they will not collapse and all collapsed vertices come from $\bigcup_{i=0}^{T-1} V_i^E$.

We show that all collapsed vertices can only come from one single $V_i^E$ for some $i$. Suppose two vertices $v$ and $v'$ from different sets of $V_i^E$ ($0 \le i \le T-1$) collapse after deleting $S$, then there is at least one pair of cliques $C_{j_0}^0$ and $C_{j_0}^1$ such that $v$ is connected to all vertices in $C_{j_0}^{d_0}$ for some $d_0 \in \{0, 1\}$ and $v'$ is connected to all vertices in $C_{j_0}^{1-d_0}$. To make $v$ collapse, at least $2ks \log T - (k-1)$ vertices from the corresponding cliques in the selection gadget need to be deleted. Then to make $v'$ collapse, at least $2ks - (k-1)$ vertices from $C_{j_0}^{1-d_0}$ need to be deleted. Therefore, at least $2ks \log T + 2ks - 2(k-1)$ vertices need to be deleted, which is strictly more than $b$. This means that the collapsed vertices come from one single $V_i^E$. Since $|S'| \ge \frac{3}{2}n$ and $|V_i^E| = \frac{3}{2}n$, we have $S' = V_i^E$ and $S \cap V_i^E = \emptyset$ for some $i$.

We consider the vertex set $S$. We know that after deleting $S$, all vertices in $V_i^E$ collapse. Denote $V_I$ the vertex set of all vertices in $\bigcup_{j=0}^{\log T-1} C_j^{d_j}$, where $i = (d_{\log T-1} \dots d_0)_2$ is the binary representation of $i$. Since every vertex in $V_I$ is connected to all vertices in $V_i^E$, to make $V_i^E$ collapse, it is always better to choose vertices from $V_I$ than any other vertex. If $S$ does not contain all vertices from $V_I$, we can update $S$ by replacing any $|V_I \setminus S|$ vertices in $S$ with vertices in $V_I \setminus S$. Then $V_I \subseteq S$.

Suppose there is a vertex $v_{p,q}$ in $V_i^E$ such that both $v_p$ and $v_q$ are not in $S \cap V$, then $S$ contains at least one vertex $v_c$ in $C$ connected to $v_{p,q}$, as otherwise $v_{p,q}$ has degree at least $k$ and will not collapse. We update $S$ by replacing $v_c$ with $v_p$. This will not influence the size of $S$ and more importantly, this will not influence the collapsed set $S' = V_i^E$, since $v_c$ in $C$ is connected to only one vertex $v_{p,q}$ in $V_i^E$, and $v_{p,q}$ will still collapse under the new $S$. By updating $S$ in the same way for other vertices in $V_i^E$ not covered by vertices in $S \cap V$, we get a vertex set $S \cap V$ which covers all vertices in $V_i^E$ at least once. And $|S \cap V| \le s$, since $V_I \subseteq S$ and $|V_I| = 2ks \log T$. This corresponds to a vertex cover of size $s$ in $G_i$. $\quad$

Lastly, we claim that there is a simple OR-cross composition [4, 9] from COLLAPSED $k$-CORE onto itself. Note that the parameter combination of the following result is incomparable to that of Theorem 17.

**Proposition 18** (⋆). COLLAPSED $k$-CORE does not admit a polynomial kernel when parameterized by the combination of $b, k$, and the bandwidth of the input graph unless $NP \subseteq coNP/poly$.

**5 Conclusion**

Our results highlight a dichotomy in the computational complexity of COLLAPSED $k$-CORE for $k \le 2$ and $k \ge 3$. Along the way, we correct some inaccuracies in the literature concerning the parameterized complexity of COLLAPSED $k$-CORE with $k = 3$ and $x = 0$ and give a simple single exponential linear time parameterized algorithm for COLLAPSED $k$-CORE with $k = 2$, which almost matches the simplest known, independently found, single exponential linear time algorithm for FEEDBACK VERTEX SET. We leave as an open question whether
COLLAPSED *k*-CORE with *k* = 2 on graphs of maximum degree 3 is polynomial time solvable similarly as FEEDBACK VERTEX SET [6, 22]. This would improve also the running time of our algorithm for COLLAPSED *k*-CORE with *k* = 2 on general graphs. We further investigate the parameterized complexity with respect to several structural parameters of the input graph. As a highlight we show that COLLAPSED *k*-CORE does not admit polynomial kernels for rather large parameter combinations. We leave the complexity of COLLAPSED *k*-CORE when parameterized solely by the cliquewidth of the input graph open.

References

1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. *Annals of Pure and Applied Logic*, 73(3):235–276, 1995.

2. Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: the anchored *k*-core problem. *SIAM Journal on Discrete Mathematics*, 29(3):1452–1475, 2015.

3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A *c*<sup>*k*</sup>*n* 5-Approximation Algorithm for Treewidth. *SIAM Journal on Computing*, 45(2):317–378, 2016.

4. Hans L. Bodlaender, Bart MP Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

5. Yixin Cao. A Naive Algorithm for Feedback Vertex Set. In *Proceedings of the 1st Symposium on Simplicity in Algorithms*, (SOSA '18), volume 61 of *OASICS*, pages 1:1–1:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.

6. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. *Algorithmica*, 73(1):63–86, 2015.

7. Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized complexity of the anchored *k*-core problem for directed graphs. *Information and Computation*, 247:11–22, 2016.

8. Rajesh Hemant Chitnis, Fedor V. Fomin, and Petr A. Golovach. Preventing Unraveling in Social Networks Gets Harder. In *Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI '13)*, pages 1085–1091. AAAI Press, 2013.

9. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

10. Reinhard Diestel. *Graph Theory, 5th Edition*, volume 173 of *Graduate Texts in Mathematics*. Springer, 2016.

11. David Garcia, Pavlin Mavrodiev, and Frank Schweitzer. Social resilience in online communities: The autopsy of friendster. In *Proceedings of the 1st ACM Conference on Online Social Networks (COSN '13)*, pages 39–50. ACM, 2013.

12. Michael R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman, 1979.

13. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartition. *Journal of Computer and System Sciences*, 72(8):1386–1396, 2006.

14. Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In *Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)*, volume 80 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 68:1–68:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2017.68.
COLLAPSED *k*-CORE with *k* = 2 on graphs of maximum degree 3 is polynomial time solvable similarly as FEEDBACK VERTEX SET [6, 22]. This would improve also the running time of our algorithm for COLLAPSED *k*-CORE with *k* = 2 on general graphs. We further investigate the parameterized complexity with respect to several structural parameters of the input graph. As a highlight we show that COLLAPSED *k*-CORE does not admit polynomial kernels for rather large parameter combinations. We leave the complexity of COLLAPSED *k*-CORE when parameterized solely by the cliquewidth of the input graph open.

References

1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. *Annals of Pure and Applied Logic*, 73(3):235–276, 1995.

2. Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: the anchored *k*-core problem. *SIAM Journal on Discrete Mathematics*, 29(3):1452–1475, 2015.

3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A *c*<sup>*k*</sup>*n* 5-Approximation Algorithm for Treewidth. *SIAM Journal on Computing*, 45(2):317–378, 2016.

4. Hans L. Bodlaender, Bart MP Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

5. Yixin Cao. A Naive Algorithm for Feedback Vertex Set. In *Proceedings of the 1st Symposium on Simplicity in Algorithms*, (SOSA '18), volume 61 of *OASICS*, pages 1:1–1:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.

6. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. *Algorithmica*, 73(1):63–86, 2015.

7. Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized complexity of the anchored *k*-core problem for directed graphs. *Information and Computation*, 247:11–22, 2016.

8. Rajesh Hemant Chitnis, Fedor V. Fomin, and Petr A. Golovach. Preventing Unraveling in Social Networks Gets Harder. In *Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI '13)*, pages 1085–1091. AAAI Press, 2013.

9. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

10. Reinhard Diestel. *Graph Theory, 5th Edition*, volume 173 of *Graduate Texts in Mathematics*. Springer, 2016.

11. David Garcia, Pavlin Mavrodiev, and Frank Schweitzer. Social resilience in online communities: The autopsy of friendster. In *Proceedings of the 1st ACM Conference on Online Social Networks (COSN '13)*, pages 39–50. ACM, 2013.

12. Michael R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman, 1979.

13. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartition. *Journal of Computer and System Sciences*, 72(8):1386–1396, 2006.

14. Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In *Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)*, volume 80 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 68:1–68:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2017.68.
15 Ton Kloks. *Treewidth, Computations and Approximations*, volume 842 of *Lecture Notes in Computer Science*. Springer, 1994.

16 Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. *Information Processing Letters*, 114(10):556-560, 2014.

17 Daniel Lokshtanov, MS Ramanujan, and Saket Saurabh. Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. *ACM Transactions on Algorithms (TALG)*, 14(1):7, 2018.

18 Junjie Luo, Hendrik Molter, and Ondřej Suchý. A Parameterized Complexity View on Collapsing *k*-Cores. *CoRR*, 2018. arXiv:1805.12453.

19 Fragkiskos D. Malliaros and Michalis Vazirgiannis. To stay or not to stay: modeling engagement dynamics in social graphs. In *Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (CIKM '13)*, pages 469-478. ACM, 2013.

20 Luke Mathieson. The parameterized complexity of editing graphs for bounded degeneracy. *Theoretical Computer Science*, 411(34-36):3181-3187, 2010.

21 Stephen B. Seidman. Network structure and minimum degree. *Social Networks*, 5(3):269-287, 1983.

22 Shuichi Ueno, Yoji Kajitani, and Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. *Discrete Mathematics*, 72(1-3):355-360, 1988.

23 Xin Wang, Roger Donaldson, Christopher Nell, Peter Gorniak, Martin Ester, and Jiajun Bu. Recommending Groups to Users Using User-Group Engagement and Time-Dependent Matrix Factorization. In *Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI '16)*, pages 1331-1337. AAAI Press, 2016.

24 Shaomei Wu, Atish Das Sarma, Alex Fabrikant, Silvio Lattanzi, and Andrew Tomkins. Arrival and departure dynamics in social networks. In *Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM '13)*, pages 233-242. ACM, 2013.

25 Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding Critical Users for Social Network Engagement: The Collapsed *k*-Core Problem. In *Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI '17)*, pages 245-251. AAAI Press, 2017.
7:14 A Parameterized Complexity View on Collapsing *k*-Cores

15 Ton Kloks. *Treewidth, Computations and Approximations*, volume 842 of *Lecture Notes in Computer Science*. Springer, 1994.

16 Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. *Information Processing Letters*, 114(10):556-560, 2014.

17 Daniel Lokshtanov, MS Ramanujan, and Saket Saurabh. Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. *ACM Transactions on Algorithms (TALG)*, 14(1):7, 2018.

18 Junjie Luo, Hendrik Molter, and Ondřej Suchý. A Parameterized Complexity View on Collapsing *k*-Cores. *CoRR*, 2018. arXiv:1805.12453.

19 Fragkiskos D. Malliaros and Michalis Vazirgiannis. To stay or not to stay: modeling engagement dynamics in social graphs. In *Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (CIKM '13)*, pages 469-478. ACM, 2013.

20 Luke Mathieson. The parameterized complexity of editing graphs for bounded degeneracy. *Theoretical Computer Science*, 411(34-36):3181-3187, 2010.

21 Stephen B. Seidman. Network structure and minimum degree. *Social Networks*, 5(3):269-287, 1983.

22 Shuichi Ueno, Yoji Kajitani, and Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. *Discrete Mathematics*, 72(1-3):355-360, 1988.

23 Xin Wang, Roger Donaldson, Christopher Nell, Peter Gorniak, Martin Ester, and Jiajun Bu. Recommending Groups to Users Using User-Group Engagement and Time-Dependent Matrix Factorization. In *Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI '16)*, pages 1331-1337. AAAI Press, 2016.

24 Shaomei Wu, Atish Das Sarma, Alex Fabrikant, Silvio Lattanzi, and Andrew Tomkins. Arrival and departure dynamics in social networks. In *Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM '13)*, pages 233-242. ACM, 2013.

25 Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding Critical Users for Social Network Engagement: The Collapsed *k*-Core Problem. In *Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI '17)*, pages 245-251. AAAI Press, 2017.
# Parameterized Complexity of Multi-Node Hubs

## Saket Saurabh

University of Bergen, Norway, and Institute of Mathematical Science, HBNI, India
saket@imsc.res.in

## Meirav Zehavi

Ben-Gurion University, Israel
meiravze@bgu.ac.il

### Abstract

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks. Furthermore, identifying and allocating hubs are routine tasks in applications. In this paper, we do not seek a hub that is a single node, but a hub that consists of *k* nodes. Formally, given a graph *G* = (*V*, *E*), we seek a set *A* ⊆ *V* of size *k* that induces a connected subgraph from which at least *p* edges emanate. Thus, we identify *k* nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call MULTI-NODE HUB (MNH), can also be viewed as a variant of the classic MAX CUT problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter *k*, our main contribution is the first parameterized algorithm that shows that MNH is FPT with respect to the parameter *p*.

Despite recent breakthrough advances for cut-problems like MULTICUT and MINIMUM BISECTION, MNH is still very challenging. Not only does a connectivity constraint has to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a maximization problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [STOC 2014] to solve MINIMUM BISECTION, where we demonstrate how connectivity constraints can be replaced by simpler size constraints. Our approach may be relevant to the design of algorithms for other cut-problems of this nature.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** hub, bisection, tree decomposition

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.8

## 1 Introduction

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks [25, 5, 1, 19, 35]. For example, hubs have been examined in the context of complex phylogenetic diseases such as asthma [33]; indeed, deletion of a hub protein is more likely to be lethal than deletion of a non-hub protein [21, 24]. Furthermore, identifying and allocating hubs are routine tasks in a wide-variety of applications [6]. In fact, the concept of hubs is also of significant interest in studies of hyperlinked environments [27], viral marketing [30], outbreaks of epidemics [4] and the Blogosphere [41].

<figure><img src="image_50.png" /></figure>

© Saket Saurabh and Meirav Zehavi;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 8; pp. 8:1–8:14

<figure><img src="image_51.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Parameterized Complexity of Multi-Node Hubs

## Saket Saurabh

University of Bergen, Norway, and Institute of Mathematical Science, HBNI, India
saket@imsc.res.in

## Meirav Zehavi

Ben-Gurion University, Israel
meiravze@bgu.ac.il

### Abstract

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks. Furthermore, identifying and allocating hubs are routine tasks in applications. In this paper, we do not seek a hub that is a single node, but a hub that consists of *k* nodes. Formally, given a graph *G* = (*V*, *E*), we seek a set *A* ⊆ *V* of size *k* that induces a connected subgraph from which at least *p* edges emanate. Thus, we identify *k* nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call MULTI-NODE HUB (MNH), can also be viewed as a variant of the classic MAX CUT problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter *k*, our main contribution is the first parameterized algorithm that shows that MNH is FPT with respect to the parameter *p*.

Despite recent breakthrough advances for cut-problems like MULTICUT and MINIMUM BISECTION, MNH is still very challenging. Not only does a *connectivity constraint* has to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a *maximization* problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [STOC 2014] to solve MINIMUM BISECTION, where we demonstrate how *connectivity constraints* can be replaced by simpler *size constraints*. Our approach may be relevant to the design of algorithms for other cut-problems of this nature.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** hub, bisection, tree decomposition

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.8

## 1 Introduction

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks [25, 5, 1, 19, 35]. For example, hubs have been examined in the context of complex phylogenetic diseases such as asthma [33]; indeed, deletion of a hub protein is more likely to be lethal than deletion of a non-hub protein [21, 24]. Furthermore, identifying and allocating hubs are routine tasks in a wide-variety of applications [6]. In fact, the concept of hubs is also of significant interest in studies of hyperlinked environments [27], viral marketing [30], outbreaks of epidemics [4] and the Blogosphere [41].

<figure><img src="image_53.png" /></figure>

© Saket Saurabh and Meirav Zehavi;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 8; pp. 8:1–8:14

<figure><img src="image_54.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 8:2 Parameterized Complexity of Multi-Node Hubs

It is natural to ask whether one can not only efficiently find a hub that is merely a single node, but a hub that consists of at most *k* nodes or (more generally) exactly *k* nodes.<fnref n="1" /> More precisely, given a threshold parameter *p*, a hub can be defined as a node of degree at least *p*. Here, we introduce the concept of a *multi-node hub*, which is a connected set of nodes of degree at least *p*. In other words, we aim to identify *k* nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). For example, in the context of biological networks, we might want to seek a module or a protein complex that acts as a hub, and in the context of social networks, we might want to identify a group of people that together act as a hub. Formally, we solve the following problem.

**MULTI-NODE HUB (MNH)**

**Input:** An undirected graph $G$ such that $|V(G)| = n$, and positive integers $k$ and $p$.

**Question:** Does there exist a subset $A \subseteq V(G)$ of size exactly $k$ such that $G[A]$ is connected, and $E(G)$ contains at least $p$ edges with exactly one endpoint in $A$?

**Parameters:** $k, p$

Multi-node hubs are of interest also for large values of $k$: when $k$ is close to $n$, a multi-node hub allows us to “shave” a few nodes from the network while ensuring that the core stays connected and has a large number of links to the nodes that were shaved. Moreover, we believe that multi-node hubs deserve to be studied also because they are simple, elegant combinatorial objects. The MNH problem involves three different types of constraints, namely a cut constraint, a size constraint and a connectivity constraint. On the one hand, it is easily seen to be MNH is W[1]-hard with respect to $k$; that is, it is unlikely that MNH is FPT with respect to $k$. On the other hand, it can be shown to be FPT with respect to $k + p$ (by a simple application of color-coding [3]). This brings us to the parameter $p$. By relying on a preprocessing phase inspired by algorithms for the MAX LEAF SPANNING TREE problem along with a novel application of special tree decompositions, namely “unbreakable tree decompositions”, we are able to establish that MNH is FPT with respect to the parameter $p$.

**Related Work.** MNH is closely related to the classical NP-hard MAX-CUT problem. Here, the input consists of a graph $G$ and a positive integer $p$, and the objective is to check whether there is a cut of size at least $p$. A cut of a graph is a partition of the vertices of the graph into two disjoint subsets. The size of the cut is the number of edges whose endpoints belong to different subsets of the partition. MAX-CUT has been the focus of extensive study from the algorithmic perspective of computer science as well as the extremal perspective of combinatorics. Papadimitriou and Yannakakis showed that MAX-CUT is APX-hard [37]. It is also well known that given an arbitrary partition of the vertex-set of $G$, by repeatedly moving vertices from one subset of the partition to the other as long as the size of the cut increases, one obtains a cut of size at least $|E(G)|/2$. A breakthrough result by Goemans and Williamson [20] gave a 0.878-approximation algorithm, which is optimal under the Unique Games Conjecture [26]. MAX-CUT has also been well studied from the viewpoint of parameterized complexity [12, 13, 34, 38]. In this context, a notable work is the parameterized algorithm for an above-guarantee version of MAX-CUT [13].

The $(k, n-k)$-MAX CUT problem, which is a variant of MAX CUT that has been extensively studied in the literature, is linked even more tightly to MNH. This variant asks whether there exists a subset $A$ of the vertex-set of a given graph $G = (V, E)$ such that

<footnote n="1">¹ If we solve the problem with the condition “exactly”, then we solve the version with the condition “at most” by trying every option to choose $k$. The condition “exactly” is of use when we have $k$ tokens that should be placed on distinct nodes, which together should act as a hub.</footnote>
## 8:2 Parameterized Complexity of Multi-Node Hubs

It is natural to ask whether one can not only efficiently find a hub that is merely a single node, but a hub that consists of at most *k* nodes or (more generally) exactly *k* nodes.<fnref n="1" /> More precisely, given a threshold parameter *p*, a hub can be defined as a node of degree at least *p*. Here, we introduce the concept of a *multi-node hub*, which is a connected set of nodes of degree at least *p*. In other words, we aim to identify *k* nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). For example, in the context of biological networks, we might want to seek a module or a protein complex that acts as a hub, and in the context of social networks, we might want to identify a group of people that together act as a hub. Formally, we solve the following problem.

**MULTI-NODE HUB (MNH)**

**Parameters:** *k*, *p*

**Input:** An undirected graph *G* such that |*V*(*G*)| = *n*, and positive integers *k* and *p*.

**Question:** Does there exist a subset *A* ⊆ *V*(*G*) of size exactly *k* such that *G*[*A*] is connected, and *E*(*G*) contains at least *p* edges with exactly one endpoint in *A*?

Multi-node hubs are of interest also for large values of *k*: when *k* is close to *n*, a multi-node hub allows us to “shave” a few nodes from the network while ensuring that the core stays connected and has a large number of links to the nodes that were shaved. Moreover, we believe that multi-node hubs deserve to be studied also because they are simple, elegant combinatorial objects. The MNH problem involves three different types of constraints, namely a cut constraint, a size constraint and a connectivity constraint. On the one hand, it is easily seen to be MNH is W[1]-hard with respect to *k*; that is, it is unlikely that MNH is FPT with respect to *k*. On the other hand, it can be shown to be FPT with respect to *k* + *p* (by a simple application of color-coding [3]). This brings us to the parameter *p*. By relying on a preprocessing phase inspired by algorithms for the MAX LEAF SPANNING TREE problem along with a novel application of special tree decompositions, namely “unbreakable tree decompositions”, we are able to establish that MNH is FPT with respect to the parameter *p*.

**Related Work.** MNH is closely related to the classical NP-hard MAX-CUT problem. Here, the input consists of a graph *G* and a positive integer *p*, and the objective is to check whether there is a cut of size at least *p*. A cut of a graph is a partition of the vertices of the graph into two disjoint subsets. The size of the cut is the number of edges whose endpoints belong to different subsets of the partition. MAX-CUT has been the focus of extensive study from the algorithmic perspective of computer science as well as the extremal perspective of combinatorics. Papadimitriou and Yannakakis showed that MAX-CUT is APX-hard [37]. It is also well known that given an arbitrary partition of the vertex-set of *G*, by repeatedly moving vertices from one subset of the partition to the other as long as the size of the cut increases, one obtains a cut of size at least |*E*(*G*)|/2. A breakthrough result by Goemans and Williamson [20] gave a 0.878-approximation algorithm, which is optimal under the Unique Games Conjecture [26]. MAX-CUT has also been well studied from the viewpoint of parameterized complexity [12, 13, 34, 38]. In this context, a notable work is the parameterized algorithm for an above-guarantee version of MAX-CUT [13].

The (*k*, *n* − *k*)-MAX CUT problem, which is a variant of MAX CUT that has been extensively studied in the literature, is linked even more tightly to MNH. This variant asks whether there exists a subset *A* of the vertex-set of a given graph *G* = (*V*, *E*) such that

<footnote n="1">¹ If we solve the problem with the condition “exactly”, then we solve the version with the condition “at most” by trying every option to choose *k*. The condition “exactly” is of use when we have *k* tokens that should be placed on distinct nodes, which together should act as a hub.</footnote>
$|A| = k$ and $E$ contains at least $p$ edges with exactly one endpoint in $A$. For this specific variant, Ageev and Sviridenko gave a 0.5-approximation algorithm [2], which has been slightly improved by Feige and Langberg [17]. It is also known that this variant is W[1]-hard with respect to the parameter $k$ [9]. With respect to the parameter $p$, $(k, n - k)$-MAX CUT can be solved in time $O^*(p^p)$ [8]. This bound was improved to $O^*(4^{p+o(p)})$ in [40], and to $O^*(2^p)$ in [39]. The latter work also gives a polynomial kernel for $(k, n - k)$-MAX CUT with respect to the parameter $p$. Bonnet et al. [8] also gave a parameterized approximation scheme for $(k, n - k)$-MAX CUT with respect to the parameter $k$.

Furthermore, CONNECTED MAX-CUT (CMC), the variant of MAX CUT where $G[A]$ should be a connected graph, has also been investigated in the literature. This variant is of interest, for example, in image segmentation [42]. Essentially, MNH can be defined as the variant of $(k, n - k)$-MAX CUT that adopts the connectivity constraint of CMC. Hajiaghayi et al. [23] studied CMC from the view point of approximation, and obtained an $\Omega(\frac{1}{\log n})$-approximation algorithm for this problem. They explicitly note that since CMC has the flavors of both cut and connectivity problems simultaneously, well-known approaches used to develop algorithms for either connectivity problems or cut problems such as MINIMUM BISECTION are not applicable to CMC. Recently, Lee et al. [29] developed a 0.5-approximation algorithm for the special case of CMC where the input graph has bounded treewidth. We remark that the study of the parameterized complexity of natural connectivity variants of well-known problems, such as CONNECTED VERTEX COVER [7, 14, 16, 18, 22, 36], is an active research area that has received considerable attention.

**Our Contribution.** In this paper, we initiate the study of multi-node hubs in general, and of algorithmic aspects of MNH in particular. Since the concept of multi-node hubs is a natural generalization of the concept of hubs, it can be of significant interest in various studies of complex networks where hubs play a central role. We believe that connectivity is the most fundamental condition to demand from multi-node hubs; in particular, it is the most basic requirement that can allow the nodes to act as a single unit. In specialized scenarios, one may want the hub to be “highly-connected” or to be structured in a manner compatible with some application-specific demands. We believe that our paper can lead to several follow-up works, not only from the viewpoint of Parameterized Complexity, on (possibly enriched) multi-node hubs.

While it is easy to observe that MNH is W[1]-hard with respect to the parameter $k$, our main contribution is the first parameterized algorithm that shows that MNH is FPT with respect to $p$ (Section 4). Our algorithm is primarily a classification result and should be viewed as a proof of concept that the problem is FPT with respect to $p$. As a corollary to our algorithm we also get that CMC is FPT with respect to $p$.

Despite the recent breakthrough advances for cut-problems like MULTICUT and MINIMUM BISECTION, MNH is still very challenging. Not only does a *connectivity constraint* have to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a *maximization* problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [15] to solve MINIMUM BISECTION, where we demonstrate how *connectivity constraints* can be replaced by simpler *size constraints*. A more detailed description of this approach can be found in Section 3. We believe that our approach can be relevant to the design of algorithms for other cut-problems of this nature.
$|A| = k$ and $E$ contains at least $p$ edges with exactly one endpoint in $A$. For this specific variant, Ageev and Sviridenko gave a 0.5-approximation algorithm [2], which has been slightly improved by Feige and Langberg [17]. It is also known that this variant is W[1]-hard with respect to the parameter $k$ [9]. With respect to the parameter $p$, $(k, n - k)$-MAX CUT can be solved in time $O^*(p^p)$ [8]. This bound was improved to $O^*(4^{p+o(p)})$ in [40], and to $O^*(2^p)$ in [39]. The latter work also gives a polynomial kernel for $(k, n - k)$-MAX CUT with respect to the parameter $p$. Bonnet et al. [8] also gave a parameterized approximation scheme for $(k, n - k)$-MAX CUT with respect to the parameter $k$.

Furthermore, CONNECTED MAX-CUT (CMC), the variant of MAX CUT where $G[A]$ should be a connected graph, has also been investigated in the literature. This variant is of interest, for example, in image segmentation [42]. Essentially, MNH can be defined as the variant of $(k, n - k)$-MAX CUT that adopts the connectivity constraint of CMC. Hajiaghayi et al. [23] studied CMC from the view point of approximation, and obtained an $\Omega(\frac{1}{\log n})$-approximation algorithm for this problem. They explicitly note that since CMC has the flavors of both cut and connectivity problems simultaneously, well-known approaches used to develop algorithms for either connectivity problems or cut problems such as MINIMUM BISECTION are *not* applicable to CMC. Recently, Lee et al. [29] developed a 0.5-approximation algorithm for the special case of CMC where the input graph has bounded treewidth. We remark that the study of the parameterized complexity of natural connectivity variants of well-known problems, such as CONNECTED VERTEX COVER [7, 14, 16, 18, 22, 36], is an active research area that has received considerable attention.

**Our Contribution.** In this paper, we initiate the study of multi-node hubs in general, and of algorithmic aspects of MNH in particular. Since the concept of multi-node hubs is a natural generalization of the concept of hubs, it can be of significant interest in various studies of complex networks where hubs play a central role. We believe that connectivity is the most fundamental condition to demand from multi-node hubs; in particular, it is the most basic requirement that can allow the nodes to act as a single unit. In specialized scenarios, one may want the hub to be “highly-connected” or to be structured in a manner compatible with some application-specific demands. We believe that our paper can lead to several follow-up works, not only from the viewpoint of Parameterized Complexity, on (possibly enriched) multi-node hubs.

While it is easy to observe that MNH is W[1]-hard with respect to the parameter $k$, our main contribution is the first parameterized algorithm that shows that MNH is FPT with respect to $p$ (Section 4). Our algorithm is primarily a classification result and should be viewed as a proof of concept that the problem is FPT with respect to $p$. As a corollary to our algorithm we also get that CMC is FPT with respect to $p$.

Despite the recent breakthrough advances for cut-problems like MULTICUT and MINIMUM BISECTION, MNH is still very challenging. Not only does a *connectivity constraint* have to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a *maximization* problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [15] to solve MINIMUM BISECTION, where we demonstrate how *connectivity constraints* can be replaced by simpler *size constraints*. A more detailed description of this approach can be found in Section 3. We believe that our approach can be relevant to the design of algorithms for other cut-problems of this nature.
## 2 Preliminaries

**Tree Decompositions.** A tree decomposition of a graph $G$ is a pair $(D, \beta)$, where $D$ is a rooted tree and $\beta: V(D) \to 2^{V(G)}$ is a mapping that satisfies the following conditions.

- For each vertex $v \in V(G)$, the set $\{d \in V(D) : v \in \beta(d)\}$ induces a nonempty and connected subtree of $D$.

- For each edge $\{v, u\} \in E(G)$, there exists $d \in V(D)$ such that $\{v, u\} \subseteq \beta(d)$.

The set $\beta(d)$ is called the *bag at d*, while sets $\beta(d) \cap \beta(t)$ for $\{d,t\} \in E(D)$ are called *adhesions*. Furthermore, given a node $d \in V(D)$, we denote $\sigma(d) = \beta(d) \cap \beta(\text{parent}(d))$ in case $d$ is not the root, and $\sigma(d) = \emptyset$ otherwise. We also denote $\gamma(d) = (\bigcup_{t \in \text{des}(d)} \beta(t)) \cup \beta(d)$.

**Unbreakability.** Given a graph $G$, we say that a pair $(A, B)$ such that $A \cup B = V(G)$ is a separation if $E(A \setminus B, B \setminus A) = \emptyset$. The order of the separation is $|A \cap B|$.

Roughly speaking, a vertex-set $U \subseteq V(G)$ is unbreakable in the graph $G$ if every separation of $V(G)$ of a small order must contain a large chunk of $U$ in one of its two sets. Intuitively, this means that the set $U$ is “highly-connected”: any attempt to “break” it severely by using a separation of a small order is futile. Formally, an unbreakable set is defined as follows.

**Definition 1.** Given a graph $G$, a set $U \subseteq V(G)$ is $(q, p)$-unbreakable in $G$ if for any separation $(A, B)$ of order at most $p$, we have that $|(A \setminus B) \cap U| \le q$ or $|(B \setminus A) \cap U| \le q$.

A $(q, p)$-unbreakable tree decomposition, a concept introduced in [15], is a tree decomposition which satisfies several properties relating to the unbreakability and connectendness of the “parts” to which it partitions the graph. These properties will be extremely valuable in Section 4, where we solve the MNH problem. In particular, such a decomposition consists of $(q, p)$-unbreakable bags; thus, for example, if we remove at most $p$ vertices from the graph, and we want to ensure that there remains a path between two vertices that belong to the same bag, it is sufficient to ensure that each of these vertices is contained in a large enough connected component (consisting of vertices from the bag). Formally, an unbreakable tree decomposition is defined as follows.

**Definition 2.** We say that a tree decomposition $(D, \beta)$ of a graph $G$ is $(q, p)$-unbreakable if $|V(D)| \le |V(G)|$ and the following conditions hold.

1. For each $d \in V(D)$, the graph $G[\gamma(d) \setminus \sigma(d)]$ is connected and $N(\gamma(d) \setminus \sigma(d)) = \sigma(d)$.

2. For each $d \in V(D)$, the set $\beta(d)$ is $(q, p)$-unbreakable in $G[\gamma(d)]$.

3. For each non-root $d \in V(D)$, we have that $|\sigma(d)| \le q$ and $\sigma(d)$ is $(2p, p)$-unbreakable in $G[\gamma(\text{parent}(d))]$.

Cygan et al. [15] gave an efficient computation of unbreakable tree decompositions, summarized in the result below.

**Theorem 3.** For some constant $c > 0$, there is an $O^*(2^{O(p^2)})$-time algorithm that, given a connected graph $G$, computes a $(2^{cp}, p)$-unbreakable tree decomposition of $G$.

## 3 Our Technique

To handle the cut constraint ($|E(A, V(G) \setminus A)| \ge p$), we employ the randomized contractions technique [10], for which an excellent high-level description is given in Section 1.1 of [11]. Since our problem also involves a size constraint ($|A| = k$), we also rely on Theorem 3 (Section 2). In short, Cygan et al. [15] showed how to replace the recursion scheme of
## 2 Preliminaries

**Tree Decompositions.** A tree decomposition of a graph $G$ is a pair $(D, \beta)$, where $D$ is a rooted tree and $\beta: V(D) \to 2^{V(G)}$ is a mapping that satisfies the following conditions.

- For each vertex $v \in V(G)$, the set $\{d \in V(D) : v \in \beta(d)\}$ induces a nonempty and connected subtree of $D$.

- For each edge $\{v, u\} \in E(G)$, there exists $d \in V(D)$ such that $\{v, u\} \subseteq \beta(d)$.

The set $\beta(d)$ is called the *bag at d*, while sets $\beta(d) \cap \beta(t)$ for $\{d,t\} \in E(D)$ are called *adhesions*. Furthermore, given a node $d \in V(D)$, we denote $\sigma(d) = \beta(d) \cap \beta(\text{parent}(d))$ in case $d$ is not the root, and $\sigma(d) = \emptyset$ otherwise. We also denote $\gamma(d) = (\bigcup_{t \in \text{des}(d)} \beta(t)) \cup \beta(d)$.

**Unbreakability.** Given a graph $G$, we say that a pair $(A, B)$ such that $A \cup B = V(G)$ is a separation if $E(A \setminus B, B \setminus A) = \emptyset$. The order of the separation is $|A \cap B|$.

Roughly speaking, a vertex-set $U \subseteq V(G)$ is unbreakable in the graph $G$ if every separation of $V(G)$ of a small order must contain a large chunk of $U$ in one of its two sets. Intuitively, this means that the set $U$ is “highly-connected”: any attempt to “break” it severely by using a separation of a small order is futile. Formally, an unbreakable set is defined as follows.

**Definition 1.** Given a graph $G$, a set $U \subseteq V(G)$ is $(q, p)$-unbreakable in $G$ if for any separation $(A, B)$ of order at most $p$, we have that $|(A \setminus B) \cap U| \le q$ or $|(B \setminus A) \cap U| \le q$.

A $(q, p)$-unbreakable tree decomposition, a concept introduced in [15], is a tree decomposition which satisfies several properties relating to the unbreakability and connectendness of the “parts” to which it partitions the graph. These properties will be extremely valuable in Section 4, where we solve the MNH problem. In particular, such a decomposition consists of $(q, p)$-unbreakable bags; thus, for example, if we remove at most $p$ vertices from the graph, and we want to ensure that there remains a path between two vertices that belong to the same bag, it is sufficient to ensure that each of these vertices is contained in a large enough connected component (consisting of vertices from the bag). Formally, an unbreakable tree decomposition is defined as follows.

**Definition 2.** We say that a tree decomposition $(D, \beta)$ of a graph $G$ is $(q, p)$-unbreakable if $|V(D)| \le |V(G)|$ and the following conditions hold.

1. For each $d \in V(D)$, the graph $G[\gamma(d) \setminus \sigma(d)]$ is connected and $N(\gamma(d) \setminus \sigma(d)) = \sigma(d)$.

2. For each $d \in V(D)$, the set $\beta(d)$ is $(q, p)$-unbreakable in $G[\gamma(d)]$.

3. For each non-root $d \in V(D)$, we have that $|\sigma(d)| \le q$ and $\sigma(d)$ is $(2p, p)$-unbreakable in $G[\gamma(\text{parent}(d))]$.

Cygan et al. [15] gave an efficient computation of unbreakable tree decompositions, summarized in the result below.

**Theorem 3.** For some constant $c > 0$, there is an $O^*(2^{O(p^2)})$-time algorithm that, given a connected graph $G$, computes a $(2^{cp}, p)$-unbreakable tree decomposition of $G$.

## 3 Our Technique

To handle the cut constraint ($|E(A, V(G) \setminus A)| \ge p$), we employ the randomized contractions technique [10], for which an excellent high-level description is given in Section 1.1 of [11]. Since our problem also involves a size constraint ($|A| = k$), we also rely on Theorem 3 (Section 2). In short, Cygan et al. [15] showed how to replace the recursion scheme of
the randomized contractions technique with a dynamic programming computation over a
static tree decomposition; this enabled a possibility for a DP state to depend on a few
counters (like sizes of parts in the case of MINIMUM BISECTION of [15]), unachievable in
the pure randomized contractions framework. The randomized contractions framework,
regardless of whether one uses the original recursion scheme or the tree decomposition of
[15], always requires significant technical work, but in most so-far known cases, this work is
not particularly novel – it follows the bumpy but well-paved way of [10]. This is not the case
in the study of the MNH problem.

First, note that the MNH problem asks for a cut of size *at least* *p*, whereas all known uses
of randomized contractions focused on cuts of size bounded-in-parameter. Thus, directly, it
seems that randomized contractions or the decomposition of [15] would not give much. Our
first main insight is that if *n* ≥ *k* + *p*, then a subgraph being a small enough tree with at
least *p* leaves witnesses a YES-instance, in which case the problem becomes similar to the
MAX LEAF SPANNING TREE problem [28], and can be solved using the method of bounded
search trees. Thus we are left with the case where |*V*(*G*) \ *A*| ≤ *p*, that is, we are to delete
bounded-in-parameter number of vertices from the graph (delete *V*(*G*) \ *A*), such that the
graph stays connected, but at least *p* edges “stick out” of the remaining graph. Now we think
of the set *V*(*G*) \ *A* as the “cut-set” for the randomized contractions technique, and finally we
can start up the entire machinery. To this end, we give one more important problem-specific
insight that greatly simplifies the use of randomized contractions: once we know *n* < *k* + *p*,
then it is easy to check if a vertex *v* of degree > 2*p* can be put outside *A* – any set *A* of size
*p* not containing *v* needs to have ≥ *p* edges that touch *v*. Thus, after easy filtering, we can
put all vertices of degree > 2*p* into *A*. By replacing each of these vertices by a binary tree,
we obtain a graph of degree bounded by 2*p*. This degree bound makes the use of “flower
cuts” (see [10]) unnecessary; intuitively, it makes the picture much closer to edge-cuts than
vertex-cuts.

At this point, we finally employ the special form of tree decomposition of Cygan et al. [15]. We use this decomposition in a non-standard manner, which relies on a twist of the understanding of the meaning of a cut-set in the randomized contractions framework, that may be of independent interest. In particular, we demonstrate how this decomposition can be used to tackle difficult connectivity constraints by replacing them by simpler size constraints: since each bag in the tree decomposition is a “highly-connected” subgraph of G (see Section 2), removing a few vertices from G cannot create two (separate) connected components that contain many vertices from the bag. Thus, instead of using direct computations to ensure the existence of paths between certain vertices, which may be very inefficient in case the paths are long, we can sometimes merely verify that the vertices are contained in large connected components.

Each node of the tree decomposition will be associated with a problem reflecting the
“work” that should be performed when handling its bag. The definition is quite technically
involved, since it is has to capture both connectivity and cut constraints, and since it has
to incorporate information provided by solutions for problems associated with the bags of
the children (which also capture both connectivity and cut constraints), while providing
enough information that will next allow us to solve the problem associated with the bag of
the parent. By proving several observations that aim to bound the sizes of “problematic”
sets of vertices (e.g., vertices in the “surroundings” of vertices that should not be put in
A), we can develop a procedure that solves the problem associated with a single bag, based
on the classic color coding method [3]. More precisely, by relying on the properties of an
unbreakable tree decomposition as well as the fact that *n* < *k* + *p* and Δ<sub>G</sub> < 2*p*, we implicitly
the randomized contractions technique with a dynamic programming computation over a
static tree decomposition; this enabled a possibility for a DP state to depend on a few
counters (like sizes of parts in the case of MINIMUM BISECTION of [15]), unachievable in
the pure randomized contractions framework. The randomized contractions framework,
regardless of whether one uses the original recursion scheme or the tree decomposition of
[15], always requires significant technical work, but in most so-far known cases, this work is
not particularly novel – it follows the bumpy but well-paved way of [10]. This is not the case
in the study of the MNH problem.

First, note that the MNH problem asks for a cut of size *at least* *p*, whereas all known uses
of randomized contractions focused on cuts of size bounded-in-parameter. Thus, directly, it
seems that randomized contractions or the decomposition of [15] would not give much. Our
first main insight is that if *n* ≥ *k* + *p*, then a subgraph being a small enough tree with at
least *p* leaves witnesses a YES-instance, in which case the problem becomes similar to the
MAX LEAF SPANNING TREE problem [28], and can be solved using the method of bounded
search trees. Thus we are left with the case where |*V*(*G*) \ *A*| ≤ *p*, that is, we are to delete
bounded-in-parameter number of vertices from the graph (delete *V*(*G*) \ *A*), such that the
graph stays connected, but at least *p* edges “stick out” of the remaining graph. Now we think
of the set *V*(*G*) \ *A* as the “cut-set” for the randomized contractions technique, and finally we
can start up the entire machinery. To this end, we give one more important problem-specific
insight that greatly simplifies the use of randomized contractions: once we know *n* < *k* + *p*,
then it is easy to check if a vertex *v* of degree > 2*p* can be put outside *A* – any set *A* of size
*p* not containing *v* needs to have ≥ *p* edges that touch *v*. Thus, after easy filtering, we can
put all vertices of degree > 2*p* into *A*. By replacing each of these vertices by a binary tree,
we obtain a graph of degree bounded by 2*p*. This degree bound makes the use of “flower
cuts” (see [10]) unnecessary; intuitively, it makes the picture much closer to edge-cuts than
vertex-cuts.

At this point, we finally employ the special form of tree decomposition of Cygan et al. [15]. We use this decomposition in a non-standard manner, which relies on a twist of the understanding of the meaning of a cut-set in the randomized contractions framework, that may be of independent interest. In particular, we demonstrate how this decomposition can be used to tackle difficult connectivity constraints by replacing them by simpler size constraints: since each bag in the tree decomposition is a “highly-connected” subgraph of *G* (see Section 2), removing a few vertices from *G* cannot create two (separate) connected components that contain many vertices from the bag. Thus, instead of using direct computations to ensure the existence of paths between certain vertices, which may be very inefficient in case the paths are long, we can sometimes merely verify that the vertices are contained in large connected components.

Each node of the tree decomposition will be associated with a problem reflecting the
“work” that should be performed when handling its bag. The definition is quite technically
involved, since it is has to capture both connectivity and cut constraints, and since it has
to incorporate information provided by solutions for problems associated with the bags of
the children (which also capture both connectivity and cut constraints), while providing
enough information that will next allow us to solve the problem associated with the bag of
the parent. By proving several observations that aim to bound the sizes of “problematic”
sets of vertices (e.g., vertices in the “surroundings” of vertices that should not be put in
A), we can develop a procedure that solves the problem associated with a single bag, based
on the classic color coding method [3]. More precisely, by relying on the properties of an
unbreakable tree decomposition as well as the fact that *n* < *k* + *p* and Δ<sub>G</sub> < 2*p*, we implicitly
show that only for a bounded-in-parameter number of the problems associated with the bags
of the children we may not simply take all of the vertices of the graph, and that it is sufficient
to classify correctly (via color coding) only a bounded-in-parameter number of vertices in the
"surroundings" of vertices that should not be put in A. We also bound the number of vertices
that surround these "surroundings", and thus, essentially, we obtain connected components
that can be handled in a partially independent manner that relies on dynamic programming.
The solutions to the problems associated with the individual bags are combined by using a
somewhat technically involved procedure that is also based on dynamic programming.

4 Multi-Node Hub is FPT with Respect to p

In this section we prove our main result:

► **Theorem 4.** *The MNH problem is solvable in time* $O^*(2^{O(p))}$.

We first solve simple cases of MNH (Section 4.1), where either the graph *G* contains many vertices (more precisely, *n* ≥ *k* + *p*) or there exists a solution *A* such that *V*(*G*) \ *A* contains a vertex of high-degree. Then, we turn to focus on the difficult instances whose handling relies on the properties of an unbreakable tree decomposition (Section 4.2).

**4.1 The Preprocessing Phase**

We first handle instances where *G* contains many vertices (Lemma 6). Then, we handle the
remaining instances to which there is a solution *A* that excludes a high-degree vertex (Lemma
7). Thus, we overall define special instances (called useful instances) of a new problem (called
SPECIAL MNH (SMNH)), which encapsulates the difficult instances of MNH (Lemma 8).

Assume WLOG that *G* is a connected graph. To solve instances where *n* ≥ *k* + *p*, we need the following notation. Given a rooted tree *T*, *leaves(*T*)* and *internal(*T*)* denote the leaf-set and the set of internal vertices of *T*, respectively. Given two trees, *T* and *T*<sub>*e*</sub>, we say that *T*<sub>*e*</sub> * extends* *T* if *T* is a subtree of *T*<sub>*e*</sub>. Observe that if *T*<sub>*e*</sub> * extends* *T*, then the number of leaves of *T*<sub>*e*</sub> is larger or equal to the number of leaves of *T*. This leads us to the next simple observation.

**Observation 5.** If a graph *G* on at least *k* + *p* vertices contains a subtree *T* with at most *k* internal vertices and at least *p* leaves, then (*G*, *k*, *p*) is a yes-instance of MNH.

**Proof.** Recall that *G* is a connected graph. Thus, since *n* ≥ *k*+*p*, as long as |*internal*(*T*)| < *k* and |*V*(*T*)| < *k* + *p*, we can extend *T* to a tree *T*<sub>*e*</sub> such that |*V*(*T*<sub>*e*</sub>)| = |*V*(*T*)| + 1. At the end of this process, we obtain a tree *T'* with at least *p* leaves (since the original tree *T* had at least *p* leaves) such that |*internal*(*T'*)| ≤ *k* and |*V*(*T'*)| ≥ *k* + *p*. We let *A* = *internal*(*T'* ) ∪ *U* where *U* is an arbitrarily chosen subset of *leaves*(*T'* ) of size exactly *k* − |*internal*(*T'* )|. Thus, we obtain a solution *A* to the instance (*G*, *k*, *p*) of MNH.

◀

We are now ready to handle instances where $n \ge k+p$.

**Lemma 6.** *MNH restricted to instances where n ≥ k + p is solvable in time O*(2*O*(p))*.

**Proof.** Let (*G*, *k*, *p*) be an instance of MNH where *n* ≥ *k* + *p*. The main reason why such an instance is simple lies in Observation 5, which implies that once we find a tree with a small number of internal vertices and a large number of leaves, we are done. This observation is exploited by our bounded search tree-based procedure, called MNH. During its execution, we maintain a tree *T*, and make “difficult” decisions (that is, decisions made by using branching
## 8:6 Parameterized Complexity of Multi-Node Hubs

show that only for a bounded-in-parameter number of the problems associated with the bags of the children we may not simply take all of the vertices of the graph, and that it is sufficient to classify correctly (via color coding) only a bounded-in-parameter number of vertices in the "surroundings" of vertices that should not be put in $A$. We also bound the number of vertices that surround these "surroundings", and thus, essentially, we obtain connected components that can be handled in a partially independent manner that relies on dynamic programming. The solutions to the problems associated with the individual bags are combined by using a somewhat technically involved procedure that is also based on dynamic programming.

# 4 Multi-Node Hub is FPT with Respect to $p$

In this section we prove our main result:

**Theorem 4.** *The MNH problem is solvable in time $O*(2^{2^{O(p)}})$.*

We first solve simple cases of MNH (Section 4.1), where either the graph $G$ contains many vertices (more precisely, $n \ge k+p$) or there exists a solution $A$ such that $V(G) \setminus A$ contains a vertex of high-degree. Then, we turn to focus on the difficult instances whose handling relies on the properties of an unbreakable tree decomposition (Section 4.2).

### 4.1 The Preprocessing Phase

We first handle instances where $G$ contains many vertices (Lemma 6). Then, we handle the remaining instances to which there is a solution $A$ that excludes a high-degree vertex (Lemma 7). Thus, we overall define special instances (called useful instances) of a new problem (called SPECIAL MNH (SMNH)), which encapsulates the difficult instances of MNH (Lemma 8).

Assume WLOG that $G$ is a connected graph. To solve instances where $n \ge k+p$, we need the following notation. Given a rooted tree $T$, **leaves($T$)** and **internal($T$)** denote the leaf-set and the set of internal vertices of $T$, respectively. Given two trees, $T$ and $T_e$, we say that $T_e$ extends $T$ if $T$ is a subtree of $T_e$. Observe that if $T_e$ extends $T$, then the number of leaves of $T_e$ is larger or equal to the number of leaves of $T$. This leads us to the next simple observation.

**Observation 5.** If a graph $G$ on at least $k+p$ vertices contains a subtree $T$ with at most $k$ internal vertices and at least $p$ leaves, then $(G, k, p)$ is a yes-instance of MNH.

**Proof.** Recall that $G$ is a connected graph. Thus, since $n \ge k+p$, as long as $|\text{internal}(T)| < k$ and $|V(T)| < k+p$, we can extend $T$ to a tree $T_e$ such that $|V(T_e)| = |V(T)| + 1$. At the end of this process, we obtain a tree $T'$ with at least $p$ leaves (since the original tree $T$ had at least $p$ leaves) such that $|\text{internal}(T')| \le k$ and $|V(T')| \ge k+p$. We let $A = \text{internal}(T') \cup U$ where $U$ is an arbitrarily chosen subset of **leaves($T'$)** of size exactly $k - |\text{internal}(T')|$. Thus, we obtain a solution $A$ to the instance $(G, k, p)$ of MNH. $\quad \blacksquare$

We are now ready to handle instances where $n \ge k+p$.

**Lemma 6.** *MNH restricted to instances where $n \ge k+p$ is solvable in time $O*(2^{O(p)})$.*

**Proof.** Let $(G, k, p)$ be an instance of MNH where $n \ge k+p$. The main reason why such an instance is simple lies in Observation 5, which implies that once we find a tree with a small number of internal vertices and a large number of leaves, we are done. This observation is exploited by our bounded search tree-based procedure, called MNH. During its execution, we maintain a tree $T$, and make "difficult" decisions (that is, decisions made by using branching
rather than reduction rules) relating to the insertion of vertices into a solution A when
handling vertices that should next be internal vertices with at least two children or fixed as
leaves in the tree T. Since a tree with at most *p* leaves has at most *p* internal vertices with at
least two children, Observation 5 bounds the number of difficult decisions we need to make
(along each branch of the search tree) before we can conclude whether there is a solution.

Each call to MNH has the form $\text{MNH}(G, k, p, T, O, I)$, where $T$ is a rooted subtree of $G$, $O \subseteq \text{leaves}(T)$, and $I \subseteq \text{leaves}(T) \setminus O$ such that $N_G(I) \subseteq V(T)$. Informally, $\text{internal}(T) \cup I$ contains the vertices we decided to insert into the solution $A$ that we attempt to construct, while $O$ contains those we decided to leave outside $A$. We further ensure that for every vertex $v \in \text{internal}(T)$, $T$ contains the entire set $N_G(v)$ (i.e., $N_G(v) \subseteq V(T)$). In other words, given a vertex which we decided to insert into $A$ (by inserting it into either $I$ or $\text{internal}(T)$), we can assume that all of its neighbors belong to $T$. That is, we rely on the following assumption:

For every vertex $v \in I \cup \text{internal}(T)$, we have that $N_G(v) \subseteq V(T)$.

Since $T$, $O$ and $I$ are the only arguments changed during the execution, we use the abbreviation MNH($T, O, I$). The goal of such a call is to accept if there is a solution $A$ to the instance $(G, k, p)$ of MNH such that $\text{internal}(T) \cup I \subseteq A$ and $O \cap A = \emptyset$, and to reject if there is no solution $A$ to this instance (in the other cases, we can either accept or reject). Clearly, we can use MNH to solve MNH in the following manner. We call it with every subtree $T$ of $G$ that consists of exactly one internal vertex along with all of its neighbors as children (which will be leaves), and $O = I = \emptyset$. Then, we accept if and only if at least one of the calls to MNH accepts.

To analyze the rules of MNH, we use the measure $3p - |E(\text{internal}(T) \cup I, O)| - |\text{leaves}(T)| - |I \cup O|$. The necessity of incorporating $|E(\text{internal}(T) \cup I, O)|$ in the measure will be clear at the analysis of the branching vector of our last rule. Initially, the measure is at most $3p$. At the latest, when the measure drops to a non-positive value, we will ensure that MNH returns an answer in polynomial time. We will also ensure that the branching rules performed by MNH are associated with branching vectors whose roots are bounded by a fixed $c$. Thus, we get that the overall running time is bounded by $O^*(2^{O(p)})$. Now, it remains to give the list of rules of MNH($T, O, I$), and prove that they satisfy the above mentioned properties. We note that although our problem resembles the MAX LEAF SPANNING TREE problem [28], there are important differences between the two problems, which forces us to devise a different, somewhat technically involved, set of rules (which is, nevertheless, inspired by the approach of [28]). In particular, recall that our goal is not to accept if and only if $G$ contains a subtree with at least $p$ leaves – however, if we do find a small enough such subtree, we can terminate the execution of our procedure.

Due to lack of space, the list of rules is omitted.

<figure><img src="image_52.png" /></figure>

We are only left with the case $n < k + p$. Next, we show a lemma that will help us in assuming that the maximum degree of the input graph is bounded by $2p$.

**Lemma 7.** *Given an instance $(G, k, p)$ of MNH where $n < k+p$, in polynomial time we can decide whether there exists a solution $A$ that does not contain $\tilde{R} = \{v \in V(G) : |N(v)| \ge 2p\}$.*

**Proof.** Suppose there exists a solution $A$ such that $\tilde{R} \setminus A \neq \emptyset$. Furthermore, let $v^* \in (\tilde{R} \setminus A)$. Then, there is a connected component $C^*$ in $G[V \setminus \{v^*\}]$ on at least $k$ vertices. As long as $|V(C^*)| > k$, compute a tree that spans $C^*$ and remove from $C^*$ a vertex that is a leaf in this tree. At the end of this process, we obtain a connected subgraph $A$ of $G[V \setminus \{v^*\}]$ on exactly $k$ vertices. Since $n < k + p$ and $|N(v)| \ge 2p$, this subgraph contains at least $p$ vertices from $N(v)$. Therefore, $|E(V(A), V(G) \setminus V(A))| \ge p$. Thus, we get that $V(A)$ is a
rather than reduction rules) relating to the insertion of vertices into a solution A when handling vertices that should next be internal vertices with at least two children or fixed as leaves in the tree T. Since a tree with at most *p* leaves has at most *p* internal vertices with at least two children, Observation 5 bounds the number of difficult decisions we need to make (along each branch of the search tree) before we can conclude whether there is a solution.

Each call to MNH has the form $MNH(G, k, p, T, O, I)$, where $T$ is a rooted subtree of $G$, $O \subseteq \text{leaves}(T)$, and $I \subseteq \text{leaves}(T) \setminus O$ such that $N_G(I) \subseteq V(T)$. Informally, $\text{internal}(T) \cup I$ contains the vertices we decided to insert into the solution A that we attempt to construct, while $O$ contains those we decided to leave outside A. We further ensure that for every vertex $v \in \text{internal}(T)$, $T$ contains the entire set $N_G(v)$ (i.e., $N_G(v) \subseteq V(T)$). In other words, given a vertex which we decided to insert into A (by inserting it into either $I$ or $\text{internal}(T)$), we can assume that all of its neighbors belong to $T$. That is, we rely on the following assumption:

> For every vertex $v \in I \cup \text{internal}(T)$, we have that $N_G(v) \subseteq V(T)$.

Since $T$, $O$ and $I$ are the only arguments changed during the execution, we use the abbreviation $\text{MNH}(T, O, I)$. The goal of such a call is to accept if there is a solution A to the instance $(G, k, p)$ of MNH such that $\text{internal}(T) \cup I \subseteq A$ and $O \cap A = \emptyset$, and to reject if there is no solution A to this instance (in the other cases, we can either accept or reject). Clearly, we can use MNH to solve MNH in the following manner. We call it with every subtree $T$ of $G$ that consists of exactly one internal vertex along with all of its neighbors as children (which will be leaves), and $O = I = \emptyset$. Then, we accept if and only if at least one of the calls to MNH accepts.

To analyze the rules of MNH, we use the measure $3p - |E(\text{internal}(T) \cup I, O)| - |\text{leaves}(T)| - |I \cup O|$. The necessity of incorporating $|E(\text{internal}(T) \cup I, O)|$ in the measure will be clear at the analysis of the branching vector of our last rule. Initially, the measure is at most $3p$. At the latest, when the measure drops to a non-positive value, we will ensure that MNH returns an answer in polynomial time. We will also ensure that the branching rules performed by MNH are associated with branching vectors whose roots are bounded by a fixed $c$. Thus, we get that the overall running time is bounded by $O^*(2^{O(p)})$. Now, it remains to give the list of rules of $\text{MNH}(T, O, I)$, and prove that they satisfy the above mentioned properties. We note that although our problem resembles the MAX LEAF SPANNING TREE problem [28], there are important differences between the two problems, which forces us to devise a different, somewhat technically involved, set of rules (which is, nevertheless, inspired by the approach of [28]). In particular, recall that our goal is *not* to accept if and only if $G$ contains a subtree with at least $p$ leaves – however, if we do find a *small enough* such subtree, we can terminate the execution of our procedure.

Due to lack of space, the list of rules is omitted.

<figure><img src="image_55.png" /></figure>

We are only left with the case $n < k + p$. Next, we show a lemma that will help us in assuming that the maximum degree of the input graph is bounded by $2p$.

**Lemma 7.** *Given an instance $(G, k, p)$ of MNH where $n < k + p$, in polynomial time we can decide whether there exists a solution A that does not contain $\tilde{R} = \{v \in V(G) : |N(v)| \ge 2p\}$.*

**Proof.** Suppose there exists a solution A such that $\tilde{R} \setminus A \neq \emptyset$. Furthermore, let $v^* \in (\tilde{R} \setminus A)$. Then, there is a connected component $C^*$ in $G[V \setminus \{v^*\}]$ on at least $k$ vertices. As long as $|V(C^*)| > k$, compute a tree that spans $C^*$ and remove from $C^*$ a vertex that is a leaf in this tree. At the end of this process, we obtain a connected subgraph $A$ of $G[V \setminus \{v^*\}]$ on exactly $k$ vertices. Since $n < k + p$ and $|N(v)| \ge 2p$, this subgraph contains at least $p$ vertices from $N(v)$. Therefore, $|E(V(A), V(G) \setminus V(A))| \ge p$. Thus, we get that $V(A)$ is a
8:8 Parameterized Complexity of Multi-Node Hubs

solution to (G, k, p) of the desired kind. Our argument shows that to decide whether there is
a solution A such that $\tilde{R} \setminus A \neq \emptyset$, we can simply check whether there is a vertex $v \in \tilde{R}$ such
that $G \setminus \{v\}$ has a connected component of size at least k. This can be done in polynomial
time.

◀

When we will solve difficult instances, it will be useful to assume that we handle graphs $G$
such that $\Delta_G < 2p$. To this end, we define the SPECIAL MNH (SMNH) problem as follows.
The input $(G, k, p, R)$ consists of an instance $(G, k, p)$ of MNH and a subset $R \subseteq V(G)$. The
goal is to decide if there is a solution $A$ to the instance $(G, k, p)$ of MNH such that $R \subseteq A$.
We say that an instance $(G, k, p, R)$ for SMNH is useful if $n < k + p$ and $\Delta_G < 2p$. Next, we
show that we can focus on solving useful instances of SMNH rather than instances of MNH.

**Lemma 8.** *Given an instance (G, k, p) of MNH, there is an $O^*(2^{O(p)})$-time algorithm that either solves (G, k, p) or returns a useful instance (G', k', p, R) of SMNH such that (1) $|V(G')| = O(|E(G)|)$, and (2) (G, k, p) is a yes-instance if and only if (G', k', p, R) is a yes-instance.*

**Proof.** Let $\tilde{R} = \{v \in V(G) : |N_G(v)| \ge 2p\}$. By Lemmas 6 and 7, we can assume that (a) $n < k+p$, and (b) there is no solution $A$ for $(G, k, p)$ such that $\tilde{R} \setminus A \ne \emptyset$. For each vertex $v \in \tilde{R}$, let $T_v$ be a binary tree on $|N_G(v)|$ leaves and $|N_G(v)| - 1$ internal vertices. While $G$ contains a vertex $v \in \tilde{R}$, insert $T_v$ into $G$ such that each leaf of $T_v$ is connected by an edge to a distinct vertex in $N_G(v)$, and then remove $v$ (and the edges containing $v$) from $G$. Let the resulting graph be $G'$. Clearly, $\Delta_{G'} < 2p$ and property (1) holds. Let $k' = |V(G')| - (n-k)$, and $R = \cup_{v \in \tilde{R}} V(T_v)$. By assumption (a), $|V(G')| = k' + (n-k) < k' + p$, and thus we conclude that $(G', k', p, R)$ is useful. By assumption (b) and our definition of $G'$, $k'$ and $R$, $A$ is a solution for $(G, k, p)$ if and only if $(A \setminus \tilde{R}) \cup R$ is a solution for $(G', k', p, R)$. Thus, property (2) holds.

◀

**4.2 An Algorithm for the Difficult Instances**

First, we briefly discuss some of the details of the dynamic programming computation that
combines solutions to problems associated with individual bags (Section 4.2.1). Then, we
formally define the problem associated with a single bag (Section 4.2.2). Due to lack of space,
the algorithm that solves it is omitted.

**4.2.1 Combining Individual Bags (Overview)**

Let $(G, k, p, R)$ be a useful instance of SMNH (i.e., $n < k + p$ and $\Delta_G < 2p$). Recall that we assume WLOG that $G$ is a connected graph. Then, by Theorem 3, we can construct a $(2^{O(p)}, p)$-unbreakable tree decomposition $(D, \beta)$ in time $O^*(2^{O(p^2)})$. We let $c$ be the constant such that $(D, \beta)$ is $(2^{cp}, p)$-unbreakable. Let $r \in V(D)$ be the root of $D$, and recall that $\sigma(r) = \emptyset$. As usual for tree decompositions, we will use dynamic programming. Unlike dynamic programming over normal tree decompositions where the size of the bag is bounded, we have that for all $d \in V(D)$, $\beta(d)$ is $(2^{cp}, p)$-unbreakable. Thus, the problem we need to solve even for one bag becomes a problem in itself.

**The Definition of M.** At every node *d* of the tree decomposition we keep a matrix (table)
that stores how an optimal solution *A*\* when restricted to *G*[*γ*(*d*)] could potentially look
like. Towards this we use a matrix *M* that has an entry [*d*,*T*,*q*,*P*\*] for all *d* ∈ *V*(*D*),
*R ∩ β*(*d*) ⊆ *T* ⊆ (*R* ∩ *β*(*d*)) ∪ *σ*(*d*), *q* ∈ {max{0, *k* − |(*V*(*G*) \ *γ*(*d*)) ∪ (*T* ∩ *σ*(*d*))|}, . . . , min{|*γ*(*d*) \
solution to (G, k, p) of the desired kind. Our argument shows that to decide whether there is
a solution A such that $\tilde{R} \setminus A \neq \emptyset$, we can simply check whether there is a vertex $v \in \tilde{R}$ such
that $G \setminus \{v\}$ has a connected component of size at least k. This can be done in polynomial
time.

◀

When we will solve difficult instances, it will be useful to assume that we handle graphs $G$
such that $\Delta_G < 2p$. To this end, we define the SPECIAL MNH (SMNH) problem as follows.
The input $(G, k, p, R)$ consists of an instance $(G, k, p)$ of MNH and a subset $R \subseteq V(G)$. The
goal is to decide if there is a solution $A$ to the instance $(G, k, p)$ of MNH such that $R \subseteq A$.
We say that an instance $(G, k, p, R)$ for SMNH is useful if $n < k + p$ and $\Delta_G < 2p$. Next, we
show that we can focus on solving useful instances of SMNH rather than instances of MNH.

**Lemma 8.** *Given an instance (G, k, p) of MNH, there is an $O^*(2^{O(p)})$-time algorithm that either solves (G, k, p) or returns a useful instance (G', k', p, R) of SMNH such that (1) $|V(G')| = O(|E(G)|)$, and (2) (G, k, p) is a yes-instance if and only if (G', k', p, R) is a yes-instance.*

**Proof.** Let $\tilde{R} = \{v \in V(G) : |N_G(v)| \ge 2p\}$. By Lemmas 6 and 7, we can assume that (a) $n < k+p$, and (b) there is no solution $A$ for $(G, k, p)$ such that $\tilde{R} \setminus A \ne \emptyset$. For each vertex $v \in \tilde{R}$, let $T_v$ be a binary tree on $|N_G(v)|$ leaves and $|N_G(v)| - 1$ internal vertices. While $G$ contains a vertex $v \in \tilde{R}$, insert $T_v$ into $G$ such that each leaf of $T_v$ is connected by an edge to a distinct vertex in $N_G(v)$, and then remove $v$ (and the edges containing $v$) from $G$. Let the resulting graph be $G'$. Clearly, $\Delta_{G'} < 2p$ and property (1) holds. Let $k' = |V(G')| - (n-k)$, and $R = \cup_{v \in \tilde{R}} V(T_v)$. By assumption (a), $|V(G')| = k' + (n-k) < k' + p$, and thus we conclude that $(G', k', p, R)$ is useful. By assumption (b) and our definition of $G'$, $k'$ and $R$, $A$ is a solution for $(G, k, p)$ if and only if $(A \setminus \tilde{R}) \cup R$ is a solution for $(G', k', p, R)$. Thus, property (2) holds.

◀

## 4.2 An Algorithm for the Difficult Instances

First, we briefly discuss some of the details of the dynamic programming computation that
combines solutions to problems associated with individual bags (Section 4.2.1). Then, we
formally define the problem associated with a single bag (Section 4.2.2). Due to lack of space,
the algorithm that solves it is omitted.

### 4.2.1 Combining Individual Bags (Overview)

Let $(G, k, p, R)$ be a useful instance of SMNH (i.e., $n < k + p$ and $\Delta_G < 2p$). Recall that we assume WLOG that $G$ is a connected graph. Then, by Theorem 3, we can construct a $(2^{O(p)}, p)$-unbreakable tree decomposition $(D, \beta)$ in time $O^*(2^{O(p^2)})$. We let $c$ be the constant such that $(D, \beta)$ is $(2^{cp}, p)$-unbreakable. Let $r \in V(D)$ be the root of $D$, and recall that $\sigma(r) = \emptyset$. As usual for tree decompositions, we will use dynamic programming. Unlike dynamic programming over normal tree decompositions where the size of the bag is bounded, we have that for all $d \in V(D)$, $\beta(d)$ is $(2^{cp}, p)$-unbreakable. Thus, the problem we need to solve even for one bag becomes a problem in itself.

**The Definition of $\mathcal{M}$**. At every node $d$ of the tree decomposition we keep a matrix (table) that stores how an optimal solution $A^*$ when restricted to $G[\gamma(d)]$ could potentially look like. Towards this we use a matrix $\mathcal{M}$ that has an entry $[d, T, q, P^*]$ for all $d \in V(D)$, $R \cap \beta(d) \subseteq T \subseteq (R \cap \beta(d)) \cup \sigma(d)$, $q \in \{\max\{0, k - |(V(G) \setminus \gamma(d)) \cup (T \cap \sigma(d))|\}, \dots, \min\{|\gamma(d)\setminus\sigma(d)|\}\}$.
between every two vertices in $E_U$ are located, and exactly $s_U$ vertices from $\gamma(d_i^c) \setminus \beta(d)$ are inserted to the solution. The value assigned by **cut** is the number of edges between vertices in the solution (to the problem already solved) and the other vertices in $\gamma(d_i^c)$ (excluding edges between vertices in $U$).

**Restrictions.** Next, we denote $tSize = |V(H)| + \sum_{U \in \{U^*\} \cup \mathcal{U}} \text{size}(U)$. For the sake of efficiency of our algorithm for SINGLE BAG, we impose several restrictions on an input instance.

1. For all $U \in \mathcal{U} \cup \{U^*\}$: $|U| \le 2^{cp}$, and each vertex in $V(H)$ is contained in at most $2p$ (not necessarily distinct) sets in the multiset $\mathcal{U}$.

2. $tSize = n < k + p$.

3. For all $(U, A_U, E_U, s_U) \in \text{domain}(\text{cut})$ such that $E_U \ne \{\{v, u\} : v, u \in U\}$, $U = A_U$ and $s_U = \text{size}(U): \text{cut}(U, A_U, E_U, s_U) = -\infty$.

The first restriction bounds the size of sets that are part of an input instance, and thus it is clear that this restriction can potentially make the instance easier to solve efficiently. The second restriction will allow us to assume that there are not too many sets $U \in \mathcal{U}$ for which we may not use the default options $A_U = U$ and $s_U = \text{size}(U)$, while the third restriction will overall allow us to conclude that there are not too many sets $U \in \mathcal{U}$ for which we may not use the default option $E_U = \{\{v, u\} : v, u \in U\}$. The claims are made precise in "Goal".

**Output.** For each $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$, we will need to find the "best" triple $(A, f, g)$ that satisfies certain conditions. Thus, we first work towards defining which triples are valid with respect to a given $q$.

**Valid Triples.** A triple $(A, f, g)$ is potentially valid if $T \subseteq A \subseteq V(H) \setminus (U^* \setminus T)$, $f$ is a function such that $f(U) \in \text{edges}(U)$ for all $U \in \mathcal{U}$, and $g$ is a function such that $g(U) \in \{0, 1, \dots, \text{size}(U)\}$ for all $U \in \mathcal{U}$. We say that a set $U \in \mathcal{U}$ is *A-damaged*, *f-damaged* and *g-damaged* if $U \setminus A \ne \emptyset$, $f(U) \ne \{\{v, u\} : v, u \in U\}$ and $g(U) \ne \text{size}(U)$, respectively. Roughly speaking, a set $U \in \mathcal{U}$ is *A-damaged* if we do not "take" all of its vertices, *f-damaged* if we do not "take" all edges between its vertices, and *g-damaged* if we do not "take" all of the vertices "below" $U$. Overall, a set $U \in \mathcal{U}$ is *damaged* if it is *A-damaged*, *f-damaged* or *g-damaged*. We will show below (in "Goal") that only few sets are damaged; the efficiency of our algorithm crucially relies on this observation, which essentially says that only few sets need "special attention". Moreover, we say a vertex $v \in V(H)$ is *damaged* if $v \in A$ and at least one of the two following conditions hold: (1) $v \in U$ for a damaged set $U$; (2) $v \in N_H(u)$ for a vertex $u \in V(H) \setminus A$. Finally, we define the *damage control graph*, $H(A, f)$, as the graph $H[A]$ to which we add the edges in $\cup_{U \in \mathcal{U}} f(U)$. Formally, $V(H(A, f)) = A$ and $E(H(A, f)) = E(H[A]) \cup (\cup_{U \in \mathcal{U}} f(U) \cap \{\{v, u\} : v, u \in A\})$. We say that a connected component is *huge* if it contains at least $2^{cp}$ vertices.

We are now ready to define which triples are valid with respect to a given $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$.

**► Definition 9.** A potentially valid $(A, f, g)$ is *q-valid* if the following conditions hold.

1. For each damaged vertex $v$ such that the connected component $C$ of $H(A, f)$ containing $v$ is not huge, at least one of the following conditions holds.

a. $V(C) \cap (U^* \cap A) \ne \emptyset$.

b. $|V(H)| \le 2^{cp} + p$ and $H(A, f)$ is a connected graph.
between every two vertices in $E_U$ are located, and exactly $s_U$ vertices from $\gamma(d_i^c) \setminus \beta(d)$ are inserted to the solution. The value assigned by **cut** is the number of edges between vertices in the solution (to the problem already solved) and the other vertices in $\gamma(d_i^c)$ (excluding edges between vertices in $U$).

**Restrictions.** Next, we denote $tSize = |V(H)| + \sum_{U \in \{U^*\} \cup \mathcal{U}} \text{size}(U)$. For the sake of efficiency of our algorithm for SINGLE BAG, we impose several restrictions on an input instance.

1. For all $U \in \mathcal{U} \cup \{U^*\}$: $|U| \le 2^{cp}$, and each vertex in $V(H)$ is contained in at most $2p$ (not necessarily distinct) sets in the multiset $\mathcal{U}$.

2. $tSize = n < k + p$.

3. For all $(U, A_U, E_U, s_U) \in \text{domain}(\text{cut})$ such that $E_U \ne \{\{v, u\} : v, u \in U\}$, $U = A_U$ and $s_U = \text{size}(U): \text{cut}(U, A_U, E_U, s_U) = -\infty$.

The first restriction bounds the size of sets that are part of an input instance, and thus it is clear that this restriction can potentially make the instance easier to solve efficiently. The second restriction will allow us to assume that there are not too many sets $U \in \mathcal{U}$ for which we may not use the default options $A_U = U$ and $s_U = \text{size}(U)$, while the third restriction will overall allow us to conclude that there are not too many sets $U \in \mathcal{U}$ for which we may not use the default option $E_U = \{\{v, u\} : v, u \in U\}$. The claims are made precise in "Goal".

**Output.** For each $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$, we will need to find the "best" triple $(A, f, g)$ that satisfies certain conditions. Thus, we first work towards defining which triples are valid with respect to a given $q$.

**Valid Triples.** A triple $(A, f, g)$ is potentially valid if $T \subseteq A \subseteq V(H) \setminus (U^* \setminus T)$, $f$ is a function such that $f(U) \in \text{edges}(U)$ for all $U \in \mathcal{U}$, and $g$ is a function such that $g(U) \in \{0, 1, \dots, \text{size}(U)\}$ for all $U \in \mathcal{U}$. We say that a set $U \in \mathcal{U}$ is *A-damaged*, *f-damaged* and *g-damaged* if $U \setminus A \ne \emptyset$, $f(U) \ne \{\{v, u\} : v, u \in U\}$ and $g(U) \ne \text{size}(U)$, respectively. Roughly speaking, a set $U \in \mathcal{U}$ is *A-damaged* if we do not "take" all of its vertices, *f-damaged* if we do not "take" all edges between its vertices, and *g-damaged* if we do not "take" all of the vertices "below" $U$. Overall, a set $U \in \mathcal{U}$ is *damaged* if it is *A-damaged*, *f-damaged* or *g-damaged*. We will show below (in "Goal") that only few sets are damaged; the efficiency of our algorithm crucially relies on this observation, which essentially says that only few sets need "special attention". Moreover, we say a vertex $v \in V(H)$ is *damaged* if $v \in A$ and at least one of the two following conditions hold: (1) $v \in U$ for a damaged set $U$; (2) $v \in N_H(u)$ for a vertex $u \in V(H) \setminus A$. Finally, we define the *damage control graph*, $H(A, f)$, as the graph $H[A]$ to which we add the edges in $\cup_{U \in \mathcal{U}} f(U)$. Formally, $V(H(A, f)) = A$ and $E(H(A, f)) = E(H[A]) \cup (\cup_{U \in \mathcal{U}} f(U) \cap \{\{v, u\} : v, u \in A\})$. We say that a connected component is *huge* if it contains at least $2^{cp}$ vertices.

We are now ready to define which triples are valid with respect to a given $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$.

**► Definition 9.** A potentially valid $(A, f, g)$ is *q-valid* if the following conditions hold.

1. For each damaged vertex $v$ such that the connected component $C$ of $H(A, f)$ containing $v$ is not huge, at least one of the following conditions holds.

a. $V(C) \cap (U^* \cap A) \ne \emptyset$.

b. $|V(H)| \le 2^{cp} + p$ and $H(A, f)$ is a connected graph.