A Parameterized Complexity View on Collapsing k-Cores

We refer to the original paper by Mathieson [38] for definitions, notation, and description of the gadgets and the reduction itself. Mathieson provides a reduction from Cyclic Monotone Circuit Activation to r-Degenerate Vertex Deletion [38, Theorem 4.4] showing that r-Degenerate Vertex Deletion is 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 2r + 1. However, for the case of r = 2 it is easy to see that the OR gadget is already 2-degenerate. We illustrate the flawed OR gadget for r = 2 in Fig. 1.

This means that whenever a Cyclic Monotone Circuit Activation instance is activated by the set of all its binary OR gates, the graph produced by the reduction (for r = 2) is already 2-degenerate, which clearly makes the reduction incorrect. We give an example in Fig. 2.

We refer to the original paper by Abrahamson et al. [1] for definitions, notation, and description of the gadgets and the reduction itself. The same reduction (using the same notation) can also be found in the book “Fundamentals of Parameterized Complexity” by Downey and Fellows [22]. Abrahamson et al. provide a reduction from Weighted Monotone Circuit Satisfiability to Degree 3 Subgraph Annihilator, which is equivalent to r-Degenerate Vertex Deletion with r = 2. With this reduction they claim to show that r-Degenerate Vertex Deletion with r = 2 is W[P]-complete when parameterized by the budget b [1, Theorem 3.7 (ii)].

The main idea of their reduction is that once a satisfying assignment is found, all variable gadgets corresponding to variables that are set to false are also removed. However, since in a variable gadget for a variable x[i], the vertex v(i,4) has high degree, it is only removed if sufficiently many of the gate gadgets that it is connected to are also removed. However, an AND gadget combined with a fan-out gadget is only removed if both inputs are removed. This follows from fan-out gadget not being removable from below. This allows us to create a counterexample with b = 1, which we illustrate in Fig. 3. It is easy to check that x[1] = x[2] = false,x[3] = true is the only satisfying assignment that has at most one variable set to true. Furthermore, the AND gates in the red area have two outgoing connections each, hence the corresponding AND gadgets have fan-out gadgets attached to them. Initially, the output of these gates is false for the satisfying assignment so the fan-out gadgets attached to them are only removed if the AND gadgets themselves are removed. An AND gadget is removed if both of its inputs are removed. However, note that the variable gadget for x[1] is not completely removed after v(3,4) is removed from the graph. In particular, the vertex v(1,4) has still degree m(b + 1) > 3 (where m is the maximum fan-out of all variables) after all vertices are removed since the AND gadgets it connects to are not removed. It follows that the graph is not 2-degenerate after removing v(3,4) and hence the reduction is not correct.

We believe that the reduction can be corrected by replacing the high degree vertices v(i, 4) by fan-out gadgets that connect to the gate gadgets. However, we omit a proof of this claim.

For any r ≥ 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.

Mathieson provides a reduction from Cyclic Monotone Circuit Activation to r-Degenerate Vertex Deletion [38, Theorem 4.4] showing that r-Degenerate Vertex Deletion is 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 2r + 1.

While the reduction is incorrect for r = 2 as shown above, there is a way to correct it: We refer to the original paper by Mathieson [38] for definitions, notation, and description of the gadgets and the reduction itself. The only problem is that his OR gadget is 2-degenerate, so the graph sometimes collapses without even deleting a single vertex. Before we introduce the correct gadget, note that the gadget is always used with exactly two inputs (predecessor gates). We can replace the OR gadget for case r = 2 with the graph illustrated in Fig. 4.

To collapse this gadget one can simply delete v^o. The correctness now follows from an analogous argument as given by Mathieson [38]. □

Let \(x^{\prime }>0\) be a positive integer. There is a linear time reduction which transforms instances (G,b,x,k) of Collapsed k-Core with x = 0 into equivalent instances \((G^{\prime },b,x^{\prime },k)\) of Collapsed k-Core. Moreover, the degeneracy of \(G^{\prime }\) is at most \(\max \limits \{d,x^{\prime }-1\}\) if \(x^{\prime } > k\) and d if \(x^{\prime } \le k\), where d is the degeneracy of G.

We distinguish two cases, depending on the relation of \(x^{\prime }\) to k.

If \(x^{\prime }\le k\), then we let \(G^{\prime }=G\). Obviously, if S is a solution for (G,b,x,k), then it is also a solution for \((G^{\prime },b,x^{\prime },k)\). On the other hand, if \(S^{\prime }\) is a solution for \((G^{\prime },b,x^{\prime },k)\), then \(G^{\prime } \setminus S^{\prime } = G \setminus S^{\prime }\) has a k-core with at most k vertices. However, any vertex of a graph with at most k vertices has degree at most k − 1 and, thus, the k-core is empty. Therefore \(S^{\prime }\) is a solution for (G,b,x,k). As \(G^{\prime }=G\), the bound on degeneracy follows for this case.

If \(x^{\prime } \ge k+1\), then we obtain \(G^{\prime }\) as a disjoint union of G and a clique C on \(x^{\prime }\) vertices. As the degeneracy of C is \(x^{\prime }-1\), the bound on degeneracy of \(G^{\prime }\) follows for this case. Again obviously, if S is a solution for (G,b,x,k), then it is also a solution for \((G^{\prime },b,x^{\prime },k)\), since the k-core of \(G^{\prime }\setminus S\) is exactly C.

Now let \(S^{\prime }\) be a solution for \((G^{\prime },b,x^{\prime },k)\). Note that if one vertex of \(C \setminus S^{\prime }\) is part of the k-core of \(G^{\prime } \setminus S^{\prime }\), then all vertices of \(C \setminus S^{\prime }\) are. If indeed \(C \setminus S^{\prime }\) is a part of the k-core of \(G^{\prime } \setminus S^{\prime }\), then the k-core contains at most \(|C \cap S^{\prime }|\) other vertices. If X is the set of vertices in the k-core of \(G^{\prime } \setminus (S^{\prime } \cup C)= G \setminus S^{\prime }\), then \(X \cup (S^{\prime } \setminus C)\) is a solution for (G,b,x,k).

Now if \(C \setminus S^{\prime }\) is not a part of the k-core of \(G \setminus S^{\prime }\), then we know that \(|C \cap S^{\prime }|\) vertices are sufficient to collapse a clique of size \(x^{\prime }\). Since the k-core of \(G^{\prime } \setminus S^{\prime }\), which is the same as the k-core of \(G \setminus S^{\prime }\) is of size at most \(x^{\prime }\), there is a set B of at most \(|C \cap S^{\prime }|\) vertices such that the k-core of \(G \setminus (S^{\prime } \cup B)\) is empty. Hence \(((S^{\prime }\setminus C) \cup B)\) is a solution for (G,b,x,k). □

Collapsed k-Core is NP-hard and W[P]-hard when parameterized by b for all x ≥ 0 and k ≥ 3, even if the degeneracy of the input graph is \(\max \limits \{k,x-1\}\) and the maximum degree of the input graph is \(\max \limits \{2k-1,x-1\}\).

Collapsed k-Core is W[1]-hard when parameterized by the combination of b and (n − x) for all k ≥ 1, even if the input graph is bipartite and \(\max \limits \{2,k\}\)-degenerate.

We reduce from W[1]-hard problem Clique [20], 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^{\prime },b,x,k)\) of Collapsed k-Core as follows. We can assume that p ≤|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. A 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(|V (G)|⋅ p³) time whether there is a clique of size at least p containing any of them. Similarly, we assume that p ≥ 4, so that \(p < \binom {p}2\) as otherwise we can find the answer in O(|V (G)|³) time.

We let \(V(G^{\prime })= 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, \ldots , k\}\}\), and \(W=\{{w_{e}^{i}} \mid e \in E, i \in \{1, \ldots , k-1\}\}\). We also let \(E(G^{\prime })=E_{U} \cup E_{W}\), where \(E_{U}=\{\{v, {u^{i}_{e}}\}\mid e \in E, i \in \{1, \ldots , k\}, v \in e\}\), and \(E_{W}=\{\{{u^{i}_{e}},w^{i^{\prime }}_{e}\}\mid e \in E, i \in \{1, \ldots , k\}, i^{\prime } \in \{1, \ldots , k-1\}\}\). We actually only introduce the sets W and E_W if k ≥ 2.

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

We claim that \((G^{\prime },b,x,k)\) is a yes-instance of Collapsed k-Core if and only if (G,p) is a yes-instance of Clique.

⇒: If S is a clique of size at least p in G, then we claim that deleting S from \(G^{\prime }\) results in a k-core of size at most x. Let e be an edge between two vertices of S in G. Then for any i ∈{1,…,k} vertex \({u_{e}^{i}}\) has only vertices \({w_{e}^{1}},{\ldots } w_{e}^{k-1}\) as neighbors in \(G^{\prime }\setminus S\). Hence, it has degree k − 1 in this graph and it is not part of the k-core of the graph. Since this holds for each i, vertices \({w_{e}^{1}},{\ldots } w_{e}^{k-1}\) do not have any neighbors in the k-core of \(G^{\prime }\setminus S\) and, hence, they are also not in the k-core of the graph. This makes 2k − 1 vertices per each edge of the clique which are not deleted and not in the k-core, showing that the size of the k-core is at most x.

⇐: Now let S be a set of vertices of \(V(G^{\prime })\) of size at most b such that \(G^{\prime }\setminus S\) has k-core of size at most x. For e ∈ E let \(UW_{e}=\{{u_{e}^{i}} \mid i \in \{1, \ldots , k\}\} \cup \{{w_{e}^{i}} \mid i \in \{1, \ldots , k-1\}\}\). Let S_E = {e ∈ E∣S ∩ UW_e≠∅}. Note that if e = {x,y}, e∉S_E, and |S ∩{x,y}|≤ 1, then the whole set UW_e ∪{x,y}∖ S is in the k-core of \(G^{\prime }\setminus S\) as each vertex in UW_e ∪{x,y}∖ S has at least k neighbors in UW_e ∪{x,y}∖ S. This means that each vertex in V ∖ S is in the k-core of \(G^{\prime }\setminus S\). Indeed, for an arbitrary vertex v in V ∖ S the degree of v in G is at least p + 1 and, thus, there is at least one edge e incident to v which is not in S_E. Hence v is in the k-core of \(G^{\prime }\setminus S\) by the above argument.

For e ∈ S_E possibly no vertex of UW_e is in the k-core of \(G^{\prime } \setminus S\), effectively shrinking it by 2k − 1 vertices. However, this does not influence the other vertices in V, U, or W, since V ∖ S is in the k-core, as we already observed. If e = {x,y} and \(\{x,y\} \subseteq S\), then also the whole set UW_e is not in the k-core as observed in the first implication. Thus, if |S ∩ V | = a and |S_E| = c, then there are at most \((2k-1)(\binom {a}{2}+c)\) vertices of \(G^{\prime }\) which are neither in S nor in the k-core of \(G^{\prime } \setminus S\). As S is a solution, this number has to be at least \((2k-1)\binom {p}{2}\), while a + c ≤ b = p. It follows that a = p and S is a clique of size p in G.

Note that graph \(G^{\prime }\) is bipartite and for k ≥ 2 it is also k-degenerate, as all vertices in W have degree k, after removing them the vertices of U have degree 2, and, finally, V forms an independent set in \(G^{\prime }\). □

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)n^f(x) time algorithm for Collapsed k-Core with k = 1, for any function f.

We present a recursive algorithm (see Algorithm 1 for pseudocode) that maintains two sets S and Q. Initially, Algorithm 1 is called with S = Q = ∅ and we call all pairs of sets S and Q on which a recursive call is made during an execution starting from empty sets as realizable. In particular, in such a case, there is an order in which the vertices were added to S ∪ Q. From now on, we only consider realizable sets S and Q.

For realizable 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 indeed obtained by calling the recursive function with both sets S and Q empty.

We start by showing that Algorithm 1 has the claimed running time.

Algorithm 1 runs in O(2^x+ 2b(m + n)) time and in \(O(2^{O(b+\sqrt {bx})}\cdot n)\) time.

We first show by induction on the size of S ∪ Q starting with the largest size achieved that a call with S and Q results in at most \(2\binom {2b+x+1-|S|-|Q|}{b-|S|}-1\) calls to the function in total. Indeed, the size of |Q| never exceeds b + x + 1 and the size of |S| never exceeds b since the sizes grow by one at a time and if they achieve the bound, then line 2 or line 5 applies. Hence, if any of the lines 2–6 applies, then we have only one call and |Q|≤ b + x + 1 and |S|≤ b implies \(2\binom {2b+x+1-|S|-|Q|}{b-|S|}-1 \ge 1\), making the basic cases. If the call makes recursive calls, then in one of them S is one larger than in the current one, and if the second one is made, then Q is one larger in it. Hence the number of calls is at most \(1+ 2\binom {2b+x+1-|S|-|Q|-1}{b-|S|-1}-1+2\binom {2b+x+1-|S|-|Q|-1}{b-|S|}-1 \le 2\binom {2b+x+1-|S|-|Q|}{b-|S|}-1\), finishing the induction.

Since we call the algorithm with sets S and Q empty, it follows that the total number of calls is at most \(2\binom {2b+x+1}{b} \le 2^{2b+x+1} = O(2^{2b+x})\). In particular, if b = 0, then the algorithm makes only one call and if x = 0 then \(2b=2b+x = 2(b +\sqrt {bx})\). Hence, in both these cases the algorithm makes at most \(O(2^{2(b +\sqrt {bx})})\) recursive calls. Otherwise, by a lemma of Fomin et al. [24, Lemma 9] we have that \(\binom {2b+x+1}{b} \le 2^{2\sqrt {b(b+x+1)}}\) which is at most \(2^{2(b +\sqrt {bx})}\) as \(b(b+x+1)=b^{2}+xb +b \le b^{2}+xb +2b\sqrt {bx} = (b+\sqrt {bx})^{2}\). So we have that the number of recursive calls is at most O(2^2b+x) and at most \(2^{O(b+\sqrt {bx})}\).

Now we analyze the time complexity of a single call. Lines 2, 4, 5, 6, 7, and 9 can be done in O(n) time. In line 3 the 1-core \(G^{\prime }\) can be found in O(n + m) time by first removing vertices in S and edges incident with them to get G ∖ S, and then removing isolated vertices in G ∖ S. Thus except for line 8 and 10, all steps can be done in O(m + n) time. Therefore, the algorithm runs in O(2^2b+x(m + n)) time. Since there are at most O(bn + x²) edges or we are facing a no-instance, we have that the time complexity of the algorithm is also \(O(2^{O(b +\sqrt {bx})}\cdot b^{O(1)}x^{O(1)}n)\), which is \(O(2^{O(b+\sqrt {bx})}\cdot n)\). □

Assuming the Exponential Time Hypothesis, there is no 2^o(b)n^f(x) time algorithm for Collapsed k-Core with k = 1, for any function f.

Since Collapsed k-Core with k = 1 and x = 0 is equivalent to Vertex Cover, and assuming the Exponential Time Hypothesis, there is no 2^o(k)n^O(1) time algorithm for Vertex Cover [34], we have that assuming the Exponential Time Hypothesis, there is no 2^o(b)n^f(x) time algorithm for Collapsed k-Core with k = 1, where f can be an arbitrary function. □

If S and Q are realizable and Q is of size more than b + x, then there is no solution containing the complete set S and no vertex from Q.

Let S and Q be realizable with |Q|≥ b + x + 1. Suppose for contradiction that B is a solution such that |B|≤ b, \(S \subseteq B\) and B ∩ Q = ∅. Let \(v_{1},v_{2}, \ldots , v_{r^{\prime }}\) be the vertices of the set S ∪ Q in the order as they were added to the set by successive recursive calls. If \(v_{r^{\prime }} \in S\), then line 2 would have applied in the parent call and the current call would never have been executed contradicting realizability of S and Q. Hence \(v_{r^{\prime }} \in Q\). If B ∖ S was empty, then S would be a solution and line 4 would have applied in the parent call, again contradicting realizability of S and Q. Therefore B ∖ S is non-empty and we let \(B \setminus S = \{v_{r^{\prime }+1}, \ldots , v_{r}\}\), i.e., {v₁,…,v_r} = B ∪ Q. Hence, it always holds that v_r ∈ B. Let \(G^{\prime }\) be the 1-core of G ∖ B and let \(X = V(G^{\prime })\). Since B is a solution, we know that |X|≤ x. Our aim is to show that there exists a vertex \(v_{j_{0}} \in Q\) such that after deleting all vertices in {v_i ∈ B∣i < j₀}, deleting vertices in {v_i ∈ B∣i > j₀} is not enough to make all vertices in {v_j ∈ Q ∖ X∣j ≥ j₀} collapse, which would be a contradiction.

To this end, we construct an injective function f that maps the vertices in B to vertices of Q ∖ X. Considering the subsequence containing the vertices of Q ∖ X in the order in which they were added to Q, we assign the last vertex in this sequence to the last vertex of B, the second-to-last to the second-to-last of B, and so on. More formally, for v_r, the last vertex in B, let f(r) be \({\max \limits } \{j \mid v_{j} \in Q \setminus X\}\). Now let v_i be the vertex from B with the largest i such that f(i) was not set yet and \(v_{i^{\prime }}\) be the vertex from B with the least \(i^{\prime }\) such that \(i^{\prime }>i\). We set \(f(i) = {\max \limits } \{j \mid j < f(i^{\prime }) \wedge v_{j} \in Q \setminus X\}\). Since the set Q ∖ X contains at least b + 1 vertices, while B contains at most b, this way we find a mapping for every vertex in B. Moreover, there remains at least one vertex in Q ∖ X not being in the image of f. Denote the one with the largest index \(v_{q_{0}}\).

For t ∈{1,…,r} let G_t be the 1-core of the graph G ∖ (B ∩{v₁,…,v_t− 1}), i.e., for \(t \le r^{\prime }\), graph \(G^{\prime }\) obtained on line 3 in the call where v_t was added to S ∪ Q. For v ∈ 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 know that \(\deg _{t}(v_{t}) \ge \deg _{t} (v_{t^{\prime }}) \ge \deg _{t^{\prime }} (v_{t^{\prime }})\) for every \(t < t^{\prime }\) with \(t \le r^{\prime }\). Note also that since G_t is a 1-core, we have \(\deg _{t}(v_{t}) \ge 1\) for all t.

Now we select the special vertex \(v_{j_{0}} \in Q\). If for every vertex v_i ∈ B we have f(i) < i, then let i₀ = 0 and j₀ = q₀. Otherwise, let i₀ be the largest i such that f(i) > i and j₀ = f(i₀). We consider the graph \(G_{j_{0}}\). Let \(V(G_{j_{0}})=B_{0} \uplus Q_{0} \uplus Y_{0} \uplus X\), where B₀ = {v_i ∈ B∣i > j₀}, Q₀ = {v_j ∈ Q ∖ X∣j ≥ j₀}, \(Y_{0}= V(G_{j_{0}}) \setminus (B_{0} \cup Q_{0} \cup X)\) is the set of vertices in \(V(G_{j_{0}})\) that will eventually collapse after the deletion of B₀ and not contained in Q₀, and X is the 1-core of G ∖ B. Note that in \(G_{j_{0}}\) vertex \(v_{j_{0}}\) in the only vertex of Q₀ which is not contained in the image set of f restricted to B₀. Thus, we have

According to our selection of j₀, for every v_i ∈ B₀ we have i₀ < j₀ < f(i) < i. Thus, for each vertex v_i ∈ B₀ we have that Let us count the number, denoted as N₀, of edges of the form {v_i,v_j} in \(G_{j_{0}}\) such that v_i ∈ B₀ and v_j ∈ Q₀. Since each edge of \(G_{j_{0}}\) incident on a vertex of Q₀ must have the other endpoint in B₀, we have that On the other hand, since edges towards Q₀ are always counted in \(\deg _{t}(v)\), we have that Combining (3) and (4), we have that

which is a contradiction. □

To show the correctness of the Algorithm 1, we first show that whenever the algorithm outputs a solution, then this solution is indeed correct. Then we show that whenever there exists a solution, the algorithm also finds a solution.

We show correctness of a returned solution by a leaf-to-root induction on the recursion tree. If Algorithm 1 returns S as a solution in line 4, then it is of size at most b since line 2 does not apply and the 1-core of G ∖ S is of size at most x. This constitutes the base case of the induction.

If the solution is obtained from recursive calls on lines 8-10, then we know that it is correct by induction hypothesis.

Next, we show by a leaf-to-root induction on the recursion tree that if there is a solution then Algorithm 1 returns a solution. In particular, we show that if there is a recursive call of Algorithm 1 with realizable sets S and Q such that there is a solution containing all of S and there is no solution containing the whole set S and any vertex from Q, then the algorithm either directly outputs a solution or it invokes a recursive call with sets \(S^{\prime }\) and \(Q^{\prime }\) such that there is a solution containing all of \(S^{\prime }\) and there is no solution containing the whole set \(S^{\prime }\) and any vertex from \(Q^{\prime }\).

Let S and Q be two realizable input sets of a recursive call of Algorithm 1 and let B be a solution such that \(S \subseteq B\) and B ∩ Q = ∅. First we show that none of lines 2, 5, and 6 applies. Line 2 will not apply since we have |S|≤|B|≤ b and by Lemma 3 we also know that we have |Q|≤ b + x. If \(G^{\prime }\), the 1-core of G ∖ S, is of size more than x, which is the case when line 4 does not apply, then S≠B and line 5 does not apply. If, in this case, line 6 applies, then \(G^{\prime }\) is also the 1-core of G[Q] and no set \(B^{\prime }\) with \(B^{\prime } \cap Q= \emptyset \) can make the 1-core of \(G\setminus B^{\prime }\) of size at most x, which is a contradiction to B being a solution with B ∩ Q = ∅. It follows that the current recursive call of Algorithm 1 does not output “No Solution”.

If B = S, then line 4 applies and the algorithm outputs B. Otherwise, we know that any vertex v is either in B and hence \(S\cup \{v\}\subseteq B\), or we have that B ∩{Q ∪{v}} = ∅. In particular, if the recursive call on line 8 does not return a solution, then, by induction hypothesis, there is no solution containing S ∪{v}, i.e., there is no solution containing S and anything of Q ∪{v} and the call on line 10 must return a solution by induction hypothesis. It follows that the algorithm invokes a recursive call with the desired properties in line 8 or in line 10.

Since Algorithm 1 starts with S = Q = ∅ we have that for any solution B the conditions \(S \subseteq B\) and B ∩ Q = ∅ are initially fulfilled. Furthermore, it follows from the complexity analysis in Lemma 1 that the algorithm always terminates. Therefore the algorithm outputs a solution if one exists and hence it is correct.

The running time bound for Algorithm 1 follows from Lemma 1 and the conditional running time lower bound for Collapsed k-Core with k = 1 follows from Lemma 2. □

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

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^{\prime }) \setminus Q\), we need to make sure that this vertex has degree greater than 2. Otherwise, either we can directly select vertices from \(V(G^{\prime }) \setminus Q\) to break cycles in \(G^{\prime }\) and get a 2-core of size at most x, or the algorithm rejects this branch. We again assume through the section that the function is called with realizable sets S and Q, that is, this call is part of an execution of Algorithm 2 initially called with S = Q = ∅.

We start by claiming that Algorithm 2 has the following running time.

Algorithm 2 runs in O(1.755^x+ 4b ⋅ n) time and in \(O(2^{O(b+\sqrt {bx})}\cdot n)\) time.

We again first show by induction on the size of S ∪ Q starting with the largest size achieved that a call with S and Q results in at most \(2\binom {4b+x+1-|S|-|Q|}{b-|S|}-1\) calls to the function in total. Indeed, the size of |Q| never exceeds 3b + x + 1 and the size of |S| never exceeds b since the sizes grow by one at a time and if they achieve the bound, then line 2 or line 5 applies. Hence, if any of the lines 2–14 applies, then we have only one call and |Q|≤ 3b + x + 1 and |S|≤ b implies \(2\binom {4b+x+1-|S|-|Q|}{b-|S|}-1 \ge 1\), making the basic cases. If the call makes recursive calls, then in one of them S is one larger than in the current one, and if the second one is made, then Q is one larger in it. Hence the number of calls is at most \(1+ 2\binom {4b+x+1-|S|-|Q|-1}{b-|S|-1}-1+2\binom {4b+x+1-|S|-|Q|-1}{b-|S|}-1 \le 2\binom {4b+x+1-|S|-|Q|}{b-|S|}-1\), finishing the induction.

Since we again call the algorithm with sets S and Q empty, it follows that the total number of calls is at most \(2\binom {4b+x+1}{b}\). Using, e.g., the lemma of Fomin et al. [24, Lemma 10] (or Stirling’s approximation) one can show that \(\binom {z}{\frac {1}{4}z} = O(1.7549^{z})\). Hence, \(\binom {4b+x+1}{b} \le \binom {4b+x+1}{\frac {1}{4}(4b+x+1)} =O(1.7549^{4b+x+1})\).

If b = 0, then the algorithm makes only one call and if x = 0 then \(4b+1=4b+x+1 = O(b +\sqrt {bx})\). Hence, in both these cases the algorithm makes at most \(2^{O(b +\sqrt {bx})}\) recursive calls. Otherwise, again by the other lemma of Fomin et al. [24, Lemma 9] we have that \(\binom {4b+x+1}{b} \le 2^{2\sqrt {b(3b+x+1)}}\). which is at most \(2^{2\sqrt {3}\cdot (b +\sqrt {bx})}\) as \(b(3b+x+1)=3b^{2}+xb +b \le 3b^{2}+xb +6b\sqrt {bx} +2xb = 3(b+\sqrt {bx})^{2}\). So we have that the number of recursive calls is at most O(1.7549^4b+x) and at most \(2^{O(b+\sqrt {bx})}\).

Now we analyze the time complexity of a single call. In line 3, the 2-core \(G^{\prime }\) can again be found in O(m) time by recursively removing vertices with degree less than 2 in G ∖ S [2]. In line 9, sorting these cycles according to their sizes can be done in O(n) time using counting sort. Thus except for line 15 and 17, all steps can again be done in O(m + n) time. Since there are at most O(bn + x²) edges or we are facing a no-instance, we have that the time complexity of the algorithm is O(1.7549^4b+x ⋅ b^O(1)x^O(1)n) and \(O(2^{O(b +\sqrt {bx})}\cdot b^{O(1)}x^{O(1)}n)\), which is O(1.755^4b+x ⋅ n) and \(O(2^{O(b+\sqrt {bx})}\cdot n)\) as claimed. □

Assuming the Exponential Time Hypothesis, there is no 2^o(b)n^f(x) time algorithm for Collapsed k-Core with k = 2, for any function f.

Since Collapsed k-Core with k = 2 and x = 0 is equivalent to Feedback Vertex Set, and assuming the Exponential Time Hypothesis, there is no 2^o(k)n^O(1) time algorithm for Feedback Vertex Set [34], we have that assuming the Exponential Time Hypothesis, there is no 2^o(b)n^f(x) time algorithm for Collapsed k-Core with k = 2, where f is an arbitrary function. □

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^{\prime }\) for (G,b,x,2) which contains only vertices with degree larger than 2.

Let v be any vertex with degree 2 in B. Let \(v^{\prime }\) be a vertex of degree at least 3 in G such that there is a path P between v and \(v^{\prime }\) with all internal vertices of degree exactly 2 in G. Since no component of G is a cycle, such a vertex must exist. Let \(B_{1}=B \cup \{v^{\prime }\}\) and \(B_{2}=(B \cup \{v^{\prime }\}) \setminus \{v\}\). We have that the 2-core of G ∖ B₂ is the same as the 2-core of G ∖ B₁ and the 2-core of G ∖ B₁ is a subset of the 2-core of G ∖ B. So the 2-core of G ∖ B₂ is a subset of the 2-core of G ∖ B, and hence no larger than x. Therefore B₂ is also a solution for (G,b,x,2). Following the same way, we can replace all degree 2 vertices in B with vertices which have degree larger than 2, and get a new solution \(B^{\prime }\) for (G,b,x,2). □

If S and Q are realizable and line 14 of Algorithm 2 applies, and for every q ∈ Q there is no solution containing the complete set S ∪{q}, then there is no solution completely containing S.

Suppose for contradiction that B is a solution containing S. Note that in this case \(B^{\prime }= B\setminus S\) is a solution for \((G^{\prime },b -|S|, x, 2)\). Let D be the graph formed by the union of connected components of \(G^{\prime }\) containing at least one vertex of degree at least 3 and C₀ be the graph formed by the union of connected components of \(G^{\prime }\) which are cycles and contain vertices of Q, that is, \(V(D) \cup V(C_{0}) = V(G^{\prime }) \setminus \bigcup _{i=1}^{r}V(C_{i})\), where C_i is as stated in the algorithm.

If B^D = B ∩ V (D) is nonempty and \(x^{\prime }\) is the size of the 2-core of D ∖ B^D, then B^D is a solution to the instance \((D,|B^{D}|,x^{\prime },2)\). Hence, by Lemma 6, there is another solution \({B^{D}_{3}}\) to the instance \((D,|B^{D}|,x^{\prime },2)\) which contains only vertices of degree at least 3. However, according to line 8 of Algorithm 2, all vertices of degree at least 3 are in Q, and hence \((B \setminus B^{D}) \cup {B^{D}_{3}}\) is a solution to (G,b,x,2) containing the complete set S and vertices of Q, contradicting our assumption. Hence B^D is empty.

If B^C = B ∩ V (C₀) is nonempty, then let y be any vertex in B^C and C_y the connected component of C₀ containing y. By the definition of C₀ component C_y contains a vertex of Q, let us denote it \(y^{\prime }\). Let \(\widehat {B}= (B \setminus \{y\}) \cup \{y^{\prime }\}\). The 2-cores of G ∖ B and \(G \setminus \widehat {B}\) are the same, since C_y is a cycle. Thus \(\widehat {B}\) is a solution to (G,b,x,2) containing the complete set S and vertices of Q, contradicting our assumption. Hence also B^C is empty.

The components of \(G^{\prime }\) neither in C₀ nor in D are cycles since \(G^{\prime }\) is a 2-core, they contain no vertices of Q, and there are no other vertices of degree at least 3. Since B contains at most \(r^{\prime }= {\min \limits } \{r, b -|S|\}\) vertices out of these components, it can destroy at most \(r^{\prime }\) of these cycles. Since |V (C₁)|≥|V (C₂)|≥… ≥|V (C_r)|, this decreases the size of the 2-core by at most \({\sum }_{i=1}^{r^{\prime }}|V(C_{i})|\). Thus, if \(|V(G^{\prime })|-{\sum }_{i=1}^{r^{\prime }}|V(C_{i})| > x\), then there is no solution containing the complete set S. □

If S and Q are realizable and Q is of size more than 3b + x, then there is no solution containing the complete set S and no vertex from Q.

Let S and Q be realizable with |Q|≥ 3b + x + 1. Suppose for contradiction that B is a solution such that |B|≤ b, \(S \subseteq B\) and B ∩ Q = ∅. Let \(v_{1},v_{2}, \ldots , v_{r^{\prime }}\) be the vertices of the set S ∪ Q in the order as they were added to the set by successive recursive calls. Similarly to the situation when k = 1, it always holds that B ∖ S is non-empty. We let \(B \setminus S = \{v_{r^{\prime }+1}, \ldots , v_{r}\}\), i.e., {v₁,…,v_r} = B ∪ Q. In particular v_r ∈ B. Without loss of generality, we can assume that for every vertex v_i ∈ B, v_i is contained in the 2-core of \(G \setminus (B \cap \{v_{1},v_{2},\dots ,v_{i-1}\})\). For \(i \le r^{\prime }\), this is clear since v_i is selected from \(G^{\prime }\) in line 7. For \(i > r^{\prime }\), v_i ∈ B ∖ S, and if v_i is not contained in the 2-core of \(G \setminus (B \cap \{v_{1},v_{2},\dots ,v_{i-1}\})\), then \(B^{\prime }=B \setminus \{v_{i}\}\) is also a solution such that \(|B^{\prime }| \le b\), \(S \subseteq B^{\prime }\) and \(B^{\prime } \cap Q=\emptyset \). Let \(G^{\prime }\) be the 2-core of G ∖ B and let \(X = V(G^{\prime })\). Since B is a solution, we know that |X|≤ x. Our aim is to show that there exists a vertex \(v_{j_{0}} \in Q\) such that after deleting all vertices in {v_i ∈ B∣i < j₀}, deleting vertices in {v_i ∈ B∣i > j₀} is not enough to make all vertices in {v_j ∈ Q ∖ X∣j ≥ j₀} collapse, which would be a contradiction.

To this end, we construct a function f that maps every vertex of B to a set of three consecutive vertices of Q ∖ X (see also Fig. 5). Considering the subsequence containing the vertices of Q ∖ X in the order in which they were added to Q, we split the last 3b vertices of this sequence into consecutive triples, and assign the last triple to the last vertex of B, the second-to-last to the second-to-last of B, and so on. More formally, for v_r, the last vertex in B, let f(r) be the set {j₁,j₂,j₃}, where \(j_{1}=\max \limits \{j \mid v_{j} \in Q \setminus X\}\), \(j_{2}=\max \limits \{j<j_{1} \mid v_{j} \in Q \setminus X\}\), and \(j_{3}=\max \limits \{j<j_{2} \mid v_{j} \in Q \setminus X\}\). Now let v_i be the vertex from B with the largest i such that f(i) was not set yet and \(v_{i^{\prime }}\) be the vertex from B with the least \(i^{\prime }\) such that \(i^{\prime }>i\). We set f(i) = {j₁,j₂,j₃}, where \(j_{1}=\max \limits \{j< \min \limits \{k \in f(i^{\prime })\} \mid v_{j} \in Q \setminus X\}\), \(j_{2}=\max \limits \{j<j_{1} \mid v_{j} \in Q \setminus X\}\), and \(j_{3}=\max \limits \{j<j_{2} \mid v_{j} \in Q \setminus X\}\). Since the set Q ∖ X contains at least 3b + 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 remain p vertices in Q ∖ X not being in the union of images of f, let us denote them \(v_{q_{1}}, \dots , v_{q_{p}}\).

For t ∈{1,…,r} let G_t be the 2-core of the graph G ∖ (B ∩{v₁,…,v_t− 1}), i.e., for \(t \le r^{\prime }\), graph \(G^{\prime }\) obtained on line 3 in the call where v_t was added to S ∪ Q. For v ∈ 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^{\prime }}) \ge \deg _{t^{\prime }} (v_{t^{\prime }}) \) for every \(t < t^{\prime }\) with \(t \le r^{\prime }\). Note also that \(\deg _{t}(v_{t}) \ge 3\) for all v_t ∈ Q.

Now we select the special vertex \(v_{j_{0}} \in Q\). If for every vertex v_i ∈ B we have \(i > \max \limits \{j \mid j \in f(i)\}\), then let i₀ = 0 and j₀ = q_p. Otherwise, let i₀ be the largest i such that \(i < \max \limits \{j \mid j \in f(i)\}\) and \(j_{0}=\max \limits \{j \mid j \in f(i_{0})\}\). We consider the graph \(G_{j_{0}}\) (see also Fig. 5). Let \(V(G_{j_{0}})=B_{0} \uplus Q_{0} \uplus Y_{0} \uplus X\), where B₀ = {v_i ∈ B∣i > j₀}, Q₀ = {v_j ∈ Q ∖ X∣j ≥ j₀}, \(Y_{0}= V(G_{j_{0}}) \setminus (B_{0} \cup Q_{0} \cup X)\) is the set of vertices in \(V(G_{j_{0}})\) that will eventually collapse after the deletion of B₀ and not contained in Q₀, and X is the 2-core of G ∖ B. Note that in \(G_{j_{0}}\) vertex \(v_{j_{0}}\) is the only vertex of Q₀ which is not contained in any image set of f restricted to B₀. Thus, we have

According to our selection of j₀, for every i with v_i ∈ B₀ we have \(i > \max \limits \{j \mid j \in f(i)\}\). Hence, \(\deg _{i}(v_{i})\leq \deg _{j}(v_{j})\) for every vertex v_i ∈ B₀ and every j ∈ f(i). Together with \(\deg _{t}(v_{t}) \ge 3\) for all v_t ∈ Q, we have for all v_i ∈ B₀.

Now we transform graph \(G_{j_{0}}\) into a partial directed graph by considering the collapsing process (see also Fig. 6). More precisely, for every edge in \(G_{j_{0}}\), except for edges which have both endpoints in X, we will assign it a direction. To this end, we just need to give an order of vertices in \(V(G_{j_{0}}) \setminus X\). Then we direct each edge from the vertex appearing earlier in the order to the one that appears later. We define this order based on the time vertices are being deleted (i.e., respecting the order v₁,v₂,…,v_r on B₀) 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₀ ∪ Y₀ has at most one outgoing edge.

Then we consider the number, denoted by N₀, of edges of \(G_{j_{0}}\) of the form \(\overrightarrow {v_{i}v_{j}}\) such that the head v_j is in Q₀. Since every vertex in Q₀ has at most one outgoing edge and \(\deg _{j_{0}}(v_{j}) \ge \deg _{j}(v_{j})\) for all v_j ∈ Q₀, we have

Now for any two sets \(M_{1},M_{2} \subseteq V(G_{j_{0}})\), let \(N_{\overrightarrow {M_{1}M_{2}}}\) be the number of edges going from M₁ to M₂. Denote \(\deg ^{+}(v)\) and \(\deg ^{-}(v)\) the number of incoming and outgoing edges of vertex v in \(G_{j_{0}}\), respectively. We first claim that To show that, note that every vertex in Y₀ has at least one incoming edge but at most one outgoing edge, implying that \({\sum }_{v \in Y_{0}} \deg ^{-}(v) \le {\sum }_{v \in Y_{0}} \deg ^{+}(v)\). This means that Therefore, \(N_{\overrightarrow {Y_{0}Q_{0}}} \le N_{\overrightarrow {B_{0}Y_{0}}}+N_{\overrightarrow {Q_{0}Y_{0}}}\), as claimed.

Now we give an upper bound for N₀. Since the edges which have their heads in Q₀ have their tails from B₀ ∪ Y₀ ∪ Q₀, we have The last inequality holds since for every vertex v_i ∈ B₀, v_i is contained in the 2-core of \(G_{j_{0}} \setminus (B_{0} \cap \{v_{1},v_{2},\dots ,v_{i-1}\})\), which means all outgoing edges of v_i are counted in \(\deg _{i} (v_{i})\). Thus we have that \({\sum }_{v_{i} \in B_{0}} \deg ^{-} (v_{i}) \le {\sum }_{v_{i} \in B_{0}} \deg _{i} (v_{i})\). Therefore, putting (7), (9), and finally (6) together we have

which is a contradiction. The last inequality holds since \(\deg _{t}(v_{t}) \geq 3\) for all v_t ∈ Q. □

To show the correctness of the algorithm, it is again enough to show that for any realizable pair of S and Q appearing in the recursive process, the set returned by the recursive function is a solution and if there is a solution containing the complete set S and there is no solution containing the whole set S and any vertex from Q, then the function returns a solution. We do this again by induction starting from the leaves of the recursion tree. For simplicity we assume without loss of generality that the input graph is a 2-core.

⇐: If the function returns S as a solution on line 4, then it is of size at most b since line 2 does not apply and the 2-core of G ∖ S is of size at most x. Hence it is obviously a solution and it is fulfilling the constraints. If the solution is obtained from recursive calls on lines 15-17, then it is a solution by induction hypothesis.

If the function returns set \(S^{\prime }\) as a solution on line 13, then for each \(i \in \{1, \ldots , r^{\prime }\}\) set \(S^{\prime }\) contains a vertex of the cycle C_i. Hence the 2-core of \(G \setminus S^{\prime }\) does not contain the cycle C_i. Since the 2-core \(G^{\prime \prime }\) of \(G \setminus S^{\prime }\) differs from the 2-core \(G^{\prime }\) of G ∖ S exactly in these missing cycle components, we have \(V(G^{\prime \prime }) = |V(G^{\prime })|-{\sum }_{i=1}^{r^{\prime }}|V(C_{i})|\). Since this is at most x by line 11 and line 2 does not apply, S is a solution. Hence, if the function returns a solution, then the answer is correct.

⇒: Now we show by induction on |Q ∪ S| for every realizable pair of S and Q, starting from the largest |Q ∪ S| achieved, that if there is a solution containing the complete set S and there is no solution containing the whole set S and any vertex from Q, then the algorithm returns a solution.

If B is a solution such that \(S \subseteq B\) and B ∩ Q = ∅, then line 2 will not apply since |B|≤ b and because of Lemma 8, whereas line 14 does not apply according to Lemma 7.

Let \(G^{\prime }\) be the 2-core of G ∖ S. If B is a solution, then \(S \cup ((B \setminus S) \cap V(G^{\prime }))\) is also a solution, so we can assume that \(B \setminus (S \cup V(G^{\prime }))=\emptyset \). If B = S, then line 4 applies. Otherwise, line 5 does not apply. If there are no vertices of degree at least 3 which are not in Q, then B contains no vertices of the components containing vertices of Q, as we have shown in the proof of Lemma 7 that B^D is empty. Hence B can decrease the size of the 2-core compared to \(G^{\prime }\) by at most \({\sum }_{i=1}^{r^{\prime }}|V(C_{i})|\), where \(r^{\prime }\) is as in the algorithm. As B is a solution, this implies \(|V(G^{\prime })|-{\sum }_{i=1}^{r^{\prime }}|V(C_{i})| \le x\) and a solution containing S is returned on line 13. This finishes the proof for the base cases of the induction.

Now suppose that the claim already holds for all calls with larger |Q ∪ S| and v is the vertex selected by the algorithm on line 7. If there is a solution containing S ∪{v} (in particular if v ∈ B), then the call SolveRec2(G,S ∪{v},Q) must return a solution by induction hypothesis and otherwise there is no solution containing S and anything of Q ∪{v} and the call SolveRec2(G,S,Q ∪{v}) must return a solution by induction hypothesis. Thus the algorithm works correctly.

The running time bound for Algorithm 2 follows from Lemma 4 and the conditional running time lower bound for Collapsed k-Core with k = 2 follows from Lemma 5. □

Collapsed 2-Core with Forbidden Vertices is NP-hard, even on graphs of maximum degree 3, even if the degree of all vertices in V₁ is 2.

We provide a polynomial time reduction from Clique in regular graphs, which is NP-hard [39]. Let (G,s) be an instance of Clique such that G is r-regular for some r. We assume that s ≥ 1 and, hence, n − s + 1 ≤ n, as otherwise the instance is trivial. We construct an instance \((G^{\prime },V_{1},V_{2},b,x)\) of Collapsed 2-Core with Forbidden Vertices as follows. Assume without loss of generality that V (G) = {v₁,…,v_n} and E(G) = {e₁,e₂,…,e_m}.

We start with \(G^{\prime }\) being a simple cycle on vertices C = {c₁,…,c_m}. Then we introduce to \(G^{\prime }\), for every j ∈{1,…m}, a vertex d_j and connect it by an edge to c_j. We let D = {d₁,…,d_m}. For every j ∈{1,…m} let us denote the endpoints of edge e_j as v_x and v_y. We introduce two vertices f_x,y and f_y,x and let both of them be adjacent to d_j. For every i ∈{1,…,n} we let F_i = {f_i,y∣y ∈{1,…,n},{v_i,v_y}∈ E(G)}. We introduce a rooted binary tree T_i with leaves in F_i, root in a new vertex h_i, and all internal vertices (except for h_i) having degree 3. All the internal vertices are newly introduced to \(G^{\prime }\). Finally, we introduce a simple cycle on vertices A = {a₁,…,a_n} and connect for each i ∈{1,…,n} the vertices h_i and a_i by a path P_i with L − r + 1 internal vertices, where L = 5m. The construction is illustrated on Fig. 7. Let us denote \(F=\bigcup _{i=1}^{n} F_{i}\).

To finish the construction, we let V₁ = F, \(V_{2}= V(G^{\prime }) \setminus F\), b = rs, and \(x= N -b-x^{\prime }\), where \(x^{\prime }= s L +\binom {s}{2}\), and \(N=V(G^{\prime })\) is the total number of vertices in the newly constructed graph.

Before we show the correctness of the reduction, let us count the number of vertices in each of the sets. There are m vertices in C and m vertices in D. For each i there are r vertices in F_i (as each vertex of G is incident with r edges) and, hence, there are exactly n ⋅ r = 2m vertices in F in total, by the Handshaking Lemma. As T_i is a rooted binary tree with r leaves, it has r − 1 internal vertices (including the root). There are L − r + 1 internal vertices on each P_i. Therefore, for each i, there are r − 1 + (L − r + 1) = L internal vertices together in T_i and P_i. Finally, there are n vertices in A. Hence, N = m + m + 2m + nL + n = 4m + n + nL and, thus, \(x = 4m + n - b -\binom {s}{2} + (n-s)L\).

We next show that \((G^{\prime },V_{1},V_{2},b,x)\) is a yes-instance of Collapsed 2-Core with Forbidden Vertices if and only if (G,s) is a yes-instance of Clique.

⇒: We start with the “if” direction. Suppose that (G,s) is a yes-instance of Clique and let S be a clique of size s in G. We let \(B = \bigcup _{v_{i} \in S} F_{i}\). As each F_i is of size exactly r, set B is of size exactly rs. Now let \(G^{\prime \prime }\) be the 2-core of \(G^{\prime } \setminus B\) and let us count the number of vertices which are neither in B nor in \(V(G^{\prime \prime })\). For any i such that v_i ∈ S, as the leaves of T_i are in B and all the internal vertices (except for the root) only have neighbors inside the tree, none of them remains in \(G^{\prime \prime }\). Thus, also the vertex h_i would only have one neighbor in \(G^{\prime \prime }\) and, hence, neither it, nor the internal vertices on path P_i are a part of \(G^{\prime \prime }\). This makes (r − 2) + 1 + (L − r + 1) = L vertices which are neither in B nor in \(V(G^{\prime \prime })\) for each i such that v_i ∈ S.

Furthermore, for each j such that e_j ∈ E(G[S]) the vertex d_j would have at most one neighbor in \(G^{\prime \prime }\) and thus it is not part of \(G^{\prime \prime }\). As S is a clique in G, there are \(\binom {s}{2}\) edges in E(G[S]) and, thus, the total number of vertices from D which are not in \(G^{\prime \prime }\) is \(\binom {s}{2}\). Therefore, in total, there are at least \(s \cdot L+ \binom {s}{2} = x^{\prime }\) vertices which are neither in B, nor in \(G^{\prime \prime }\). Hence, \(|V(G^{\prime \prime })| \le N - b -x^{\prime } =x\) and B is a solution to \((G^{\prime },V_{1},V_{2},b,x)\).

⇐: Now for the “only if” direction let us assume that there is a solution B to \((G^{\prime },V_{1},V_{2},b,x)\) and let \(G^{\prime \prime }\) be the 2-core of \(G^{\prime } \setminus B\). First notice that the cycles A and C are always contained in \(G^{\prime \prime }\) as \(B \subseteq F\). Let us now take some i ∈{1,…,n} such that F_i ∖ B≠∅ and let f_i,y ∈ F_i ∖ B. Moreover, let e_j = {v_i,v_y}. The edge between c_j and d_j, the edge connecting d_j and f_i,y, the path in T_i from f_i,y to h_i, and the path P_i form together a path connecting the cycles A and C in \(G^{\prime } \setminus B\) and, hence, also in \(G^{\prime \prime }\). Note that the part of this path between f_i,y and a_i, including f_i,y and h_i, but not including a_i, has at least (L − r + 1) + 2 = L − r + 3 vertices and cannot be shared between different indices i. Let S = {v_i∣F_i ∖ B = ∅}. If |S| < s, then there are at least n − s + 1 indices i such that F_i ∖ B≠∅. That is,

since Hence, |S|≥ s, and, as rs ≥|B|≥ r|S| by the definition of S, we have |S| = s. That is, \(B= \bigcup _{v_{i} \in S} F_{i}\).

For every i such that v_i∉S, \(G^{\prime \prime }\) contains F_i, T_i, and P_i by the above argument. This makes r + r − 1 + (L − r + 1) = L + r vertices for each such i (not counting a_i) and (n − s)(L + r) = nr − rs + (n − s)L = 2m − b + (n − s)L vertices together. Moreover, the cycles on A and C are always contained in \(G^{\prime \prime }\). If there are more than \(m - \binom {s}{2}\) indices j such that d_j is in \(G^{\prime \prime }\), then

Hence, there are at least \(\binom {s}{2}\) indices j such that d_j is not in \(G^{\prime \prime }\). For each such j, letting e_j = {v_x,v_y}, we must have f_x,y ∈ B and also f_y,x ∈ B, as otherwise d_j would have at least 2 neighbors in \(G^{\prime \prime }\) — c_j and at least one of f_y,x and f_x,y. Hence, both v_x ∈ S and v_y ∈ S, i.e., e_j ∈ E(G[S]). It follows that \(|E(G[S])| \ge \binom {s}{2}\), that is S is a clique of size s in G and (G,s) is a yes-instance of Clique.

Since the reduction can be performed in polynomial time, all vertices have degree at most 3 in \(G^{\prime }\), vertices in V₁ = F have degree 2, and the instances are equivalent, this finishes the proof. □

Collapsed k-Core is W[1]-hard when parameterized by the combination of b and the clique cover number of the input graph.

We present a parameterized reduction from the W[1]-hard problem Multicolored Clique parameterized by the solution size [20]. In Multicolored Clique, we are given an integer s and a s-colored graph with color classes \(V_{1}, V_{2}, \dots , V_{s}\), and the task is to find a clique of size s containing one vertex from each color class. Let \((G=(V,E),s,V_{1}, V_{2}, \dots , V_{s})\) be an instance of Multicolored Clique. The edge set E can be partitioned into \(\binom {s}{2}\) subsets: E_i,j = {v_zv_y|v_z ∈ V_i,v_y ∈ V_j},1 ≤ i < j ≤ s. We create an instance \((G^{\prime }=(V^{\prime },E^{\prime }),b,x,k)\) of Collapsed k-Core as follows (see Fig. 8 for an illustration). Notice that the clique cover number of \(G^{\prime }\) is \(s+\binom {s}{2}+1\). We claim that there is a multicolored clique of size s in G if and only if \((G^{\prime },b,x,k)\) is a yes-instance.

⇒: If there is a multicolored clique S of size s in G, we show in the following that the k-core of \(G^{\prime }-S\) has size at most x. Since b = s and \(N^{\prime }=s+k\binom {s}{2}\), it suffices to show that all edge cliques C_i,j collapse. For any clique C_i,j, every vertex in this clique has degree k + 1, since it has k − 1 neighbors in C_i,j and 2 neighbors in C_i and C_j (or in C for dummy vertices). For any C_i,j, suppose v_z,v_y ∈ S, where v_z ∈ V_i and v_y ∈ V_j. Since S is a clique, there is an edge v_zv_y in G, and there are v_z,y and \(v^{\prime }_{z,y}\), both connected to v_z and v_y in \(G^{\prime }\). After deleting v_z and v_y, both v_z,y and \(v^{\prime }_{z,y}\) collapse, which then causes all remaining vertices in C_i,j to collapse. Therefore all edge cliques C_i,j will collapse after deleting S.

⇐: Suppose \((G^{\prime },b,x,k)\) is a yes-instance, we need to show that there is a multicolored clique of size s in G. Let S be the deleted vertex set of size at most b and let \(S^{\prime }\) be the set of all collapsed vertices. Since \(N^{\prime }=s+k\binom {s}{2}\), we have \(|S^{\prime }| \geq k\binom {s}{2}\). Notice that in the subgraph of \(G^{\prime }\) induced by \(C \cup \bigcup _{i=1}^{s} C_{i}\) all vertices in C_i have degree at least k + s and all vertices in C have degree at least 2n⁴ + k + s − 1. Therefore, by Observation 2, these vertices will never collapse and only vertices in \(\bigcup _{i=1}^{s}\bigcup _{j=i+1}^{s}C_{i,j}\) can collapse. Since the number of vertices in \(\bigcup _{i=1}^{s}\bigcup _{j=i+1}^{s}C_{i,j}\) is exactly \(k\binom {s}{2}\), we have that all vertices in \(\bigcup _{i=1}^{s}\bigcup _{j=i+1}^{s}C_{i,j}\) will collapse, S only contains vertices from C and \(\bigcup _{i=1}^{s}C_{i}\), and contains exactly s of them.

Suppose S contains t vertices from C and s − t vertices from \(\bigcup _{i=1}^{s}C_{i}\). On one hand, for every clique C_i,j, the first vertex to collapse must connect to two vertices from S, so overall there must be \(2\binom {s}{2}\) edges between all such vertices and S. On the other hand, each vertex in S ∩ C can provide at most one such edge and each vertex in S from \(\bigcup _{i=1}^{s}C_{i}\) can provide at most s − 1 such edges, so overall the number is strictly less than \(2\binom {s}{2}\) if t > 0. Since all cliques C_i,j,1 ≤ i < j ≤ s will collapse, we have t = 0 and S only contains vertices from \(\bigcup _{i=1}^{s}C_{i}\).

So the firstly collapsed vertex v_z,y in C_i,j must connect to two vertices from S, one v_z from C_i and another v_y from C_j. This means S contains exactly one vertex v_i from each C_i and each pair of vertices v_i and v_j connect to at least one common vertex v_i,j in C_i,j, which means v_i and v_j are connected in G. Therefore, S forms a clique of size s in G. □

Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph.

Let (G,b,x,k) be an instance of Collapsed k-Core. As every graph G is tw(G)-degenerate (see [20, Exercise 7.14]) 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 of G [8, 32] 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 sets 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 (including those already forgotten). This number is always in 0,…,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.

Morex formally, let V_t be a bag of the decomposition and G_t be the subgraph of the input graph induced by the union of all bags that are descendants of V_t (including V_t itself). Let tuple \(b^{\prime }\), \(x^{\prime }\), B, X, Q, \(\preccurlyeq \) and f represent an index of the associated table, that is, \(b^{\prime } \in \{0, \ldots , b\}\), \(x^{\prime } \in \{0, \ldots , x\}\), B ⊎ X ⊎ Q is a partition of V_t, \(\preccurlyeq \) is a total order on Q, and f : Q →{0,…,k − 1}. Then we set the corresponding table entry to true if and only if there is a partition \(B^{\prime } \uplus X^{\prime } \uplus Q^{\prime }\) of V (G_t) and a total order \(\trianglelefteq \) on \(Q^{\prime }\) satisfying the following conditions: \(B^{\prime } \cap V_{t} =B\), \(Q^{\prime } \cap V_{t} =Q\), \(X^{\prime } \cap V_{t} =X\), \(\preccurlyeq \) is the restriction of \(\trianglelefteq \) to Q, \(|B^{\prime } \setminus B|=b^{\prime }\), \(|X^{\prime } \setminus X|=x^{\prime }\) and for every \(q \in Q^{\prime }\) we have \(k>|\{r \mid \{q,r\} \in E \wedge (r \in X^{\prime } \vee (r \in Q^{\prime } \wedge q \trianglelefteq r))\}|\), and, in particular, for q ∈ Q we have \(f(q)=|\{r \mid \{q,r\} \in E \wedge (r \in X^{\prime } \vee (r \in Q^{\prime } \wedge q \trianglelefteq r))\}|\).

It is straightforward to compute the content of the table for a particular bag based on the tables for the children bags.

There are 3^tw(G) ⋅tw(G)^O(tw(G)) ⋅ k^tw(G) = tw(G)^O(tw(G)) possible indices for each bag. Hence the slightly superexponential running time of tw(G)^O(tw(G)) ⋅ n^O(1) follows. □

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.

We first develop, for a fixed k a formula which should express that the set X contains the whole vertex set of the k-core of the graph G − B. The formula thus says that no graph induced by a set larger than X, but not containing anything from B is a core. In other words, each such graph contains a vertex of degree at most k − 1, i.e., not having k distinct neighbors in the set considered. For that purpose we use the following subformula:

Now the sought formula is

This formula is of length O(k²). Combined with some of the following formulae it gives the result for all parameter combinations promised. The following formula bounds a set S passed to be of size at most s:

The next formula bounds the size to at most n − s:

Both these formulae have length O(s²).

Now the result follows from the theorem of Courcelle et al. [18] as it allows for optimization over the size of one free set variable. Hence, the result for parameterization by the cliquewidth, k, and b is obtained by minimizing the size of X satisfying \(\exists B \subseteq V \mathtt {core}(B,X) \wedge \mathtt {sizeatmost}_{b}(B)\) in the input graph, where the formula is of size O(k² + b²). The result for parameterization by the cliquewidth, k, and x is obtained by minimizing the size of B satisfying \(\exists X \subseteq V \mathtt {core}(B,X) \wedge \mathtt {sizeatmost}_{x}(X)\), where the formula is of size O(k² + x²). The result for parameterization by the cliquewidth, k, and n − x is obtained by minimizing the size of B satisfying \(\exists X \subseteq V \mathtt {core}(B,X) \wedge \mathtt {sizeatmost}_{n-(n-x)}(X)\), where the formula is of size O(k² + (n − x)²). Finally, the result for parameterization by the cliquewidth, k, and n − b is obtained by minimizing the size of X satisfying \(\exists B \subseteq V \mathtt {core}(B,X) \wedge \mathtt {sizeatmost}_{n-(n-b)}(B)\) in the input graph, where the formula is of size O(k² + (n − b)²). □

For all k ≥ 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 \({\textsf {NP}}\subseteq \text {{\textsf {coNP}}/poly}\).

We apply an OR-cross composition from the NP-hard problem Cubic Vertex Cover [26]. 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 ≥|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^{\prime },s^{\prime })\) are \(\mathcal {R}\)-equivalent if \(|V(G)|=|V(G^{\prime })|\) and \(s=s^{\prime }\). 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≤i≤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 ≥ 2 as follows.

Notice that the vertex cover number of G is at most \(n+4ks\log {T}+k+b+\frac {3}{2}n(k-2)\) as \(V \cup \bigcup _{j=0}^{\log T-1}\bigcup _{d=0}^{1}{C_{j}^{d}} \cup C\) forms a vertex cover of the graph. The construction is illustrated in Fig. 9. 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 \(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^{\prime }\) be the set of all collapsed vertices. Since \(N^{\prime }=s+2ks\log {T}+\frac {3}{2}n\), we have \(|S^{\prime }| \geq \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 Observation 2 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^{\prime }\) from different sets of \({V_{i}^{E}}\) (0 ≤ i ≤ 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,1} and \(v^{\prime }\) 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^{\prime }\) 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^{\prime }| \geq \frac {3}{2}n\) and \(|{V_{i}^{E}}|=\frac {3}{2}n\), we have \(S^{\prime }={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 ∖ S| vertices in S with vertices in V_I ∖ 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 ∩ 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^{\prime }={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 ∩ V, we get a vertex set S ∩ V which covers all vertices in \({V_{i}^{E}}\) at least once. And |S ∩ V |≤ s, since \(V_{I} \subseteq S\) and \(|V_{I}|=2ks\log {T}\). This corresponds to a vertex cover of size s in G_i. □

For all k ≥ 1 Collapsed k-Core does not admit a polynomial kernel when parameterized by the combination of b, n − x, and the bandwidth of the input graph unless \({\textsf {NP}}\subseteq \text {{\textsf {coNP}}/poly}\).

We apply an OR-cross composition from Collapsed k-Core to Collapsed k-Core.

We say an instance of Collapsed k-Core is malformed if the string does not represent a quadruple (G,b,x,k), where G is a graph and b, x are non-negative integers. It is trivial, if b ≥|V (G)|, x ≥|V (G)|, or k ≥|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₁,b₁,x₁,k) and (G₂,b₂,x₂,k) are \(\mathcal {R}\)-equivalent if |V (G₁)| = |V (G₂)|, b₁ = b₂ and x₁ = x₂. Observe that \(\mathcal {R}\) is a polynomial equivalence relation.

Let the input consist of T \(\mathcal {R}\)-equivalent instances of Collapsed k-Core. If the instances are malformed or trivial, we return a constant size no- or yes- instance of Collapsed k-Core, respectively. Let (G_i,b_i,x_i,k)_1≤i≤T be well-formed non-trivial \(\mathcal {R}\)-equivalent instances of Collapsed k-Core. Since all instances have the same b_i,x_i and all G_i with 1 ≤ i ≤ T have the same size of vertex set, we denote b = b_i,x = x_i and n = |V (G_i)|. If n ≤ 3, then we solve all the instances in O(T) time and output a constant-size instance with the appropriate answer.

Now we create an instance \((G,b^{\prime },x^{\prime },k)\) of Collapsed k-Core. We start by making G a disjoint union of all G_i. For each i ∈{1,…,T}, we add to G two cliques C_i and \(C_{i}^{\prime }\), each of size n², and add all edges between G_i and C_i and between C_i and \(C_{i}^{\prime }\). Note that G contains T(n + 2n²) vertices in total. Set \(b^{\prime }=b+n^{2}\) and \(x^{\prime }=(n+2n^{2})(T-1)+n^{2}+x\).

Notice that the bandwidth [13] of G is upper bounded by 2n² and \(|V(G)|-x^{\prime }=T(n+2n^{2})-(T-1)(n+2n^{2})-n^{2}-x\le n^{2}+n\). We now show that at least one instance (G_i,b,x,k) is a yes-instance if and only if the instance \((G,b^{\prime },x^{\prime },k)\) of Collapsed k-Core constructed above is a yes-instance.

⇒: If (G_i,b,x,k) is a yes-instance, then there is a subset \(S \subseteq V(G_{i})\) such that the k-core of G_i − S has size at most x. If we delete all vertices from S and the whole clique C_i in G, then at most x vertices remain in the k-core of G_i − S. Therefore the k-core of G − S − V (C_i) has size at most \(x^{\prime }\).

⇐: If \((G,b^{\prime },x^{\prime },k)\) is a yes-instance, then let S be the set of deleted vertices of size at most \(b^{\prime }\) and let \(S^{\prime }\) be the set of all collapsed vertices. Since the degree of vertices in C_i and \(C_{i}^{\prime }\) is at least 2n² − 1 which is more than \(n^{2}+2n \ge b^{\prime }+k\) for n ≥ 3, these vertices will never collapse by Observation 2. So \(S^{\prime }\) only contains vertices from \(\bigcup _{i=1}^{T} V(G_{i})\). Furthermore, it is impossible for two vertices v_i and v_j from different sets V (G_i) and V (G_j) to collapse after deleting S. Indeed, suppose they do collapse, then |S ∩ C_i|≥ n² − k and |S ∩ C_j|≥ n² − k, which means \(|S| \geq 2n^{2}-2k \ge 2n^{2}-2n \ge n^{2}+n > n^{2}+b=b^{\prime }\), where the middle inequality follows from n ≥ 3. Therefore \(S^{\prime }\) only contains vertices from a single graph, say G_i.

Since G contains T(n + 2n²) vertices in total, \(x^{\prime }=(n+2n^{2})(T-1)+n^{2}+x\), and \(b^{\prime }=b+n^{2}\), we have \(|S^{\prime }| \geq n-b-x\). To make vertices in G_i collapse, it is always better to choose vertices from C_i into S, as vertices from C_i connect to all vertices in G_i. Thus we can assume \(C_{i} \subseteq S\). Then |S ∩ V (G_i)|≤ b. If \(|V(G_{i}) \setminus (S \cup S^{\prime })| > x\), which can only happen if |S ∩ V (G_i)| < b, then we can remove vertices from S ∖ (C_i ∪ V (G_i)) and add vertices from \(G_{i} \setminus (S \cup S^{\prime })\) to S until |S ∩ V (G_i)| = b. This will not influence the collapsed vertices in \(S^{\prime }\). Then we get a vertex set S_i = S ∩ V (G_i), and the k-core of G_i − S_i has size at most x. □