Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

19.06.2021 | Ausgabe 8/2021 Open Access

Theory of Computing Systems 8/2021

A Parameterized Complexity View on Collapsing k-Cores

Zeitschrift:
Theory of Computing Systems > Ausgabe 8/2021
Autoren:
Junjie Luo, Hendrik Molter, Ondřej Suchý
Wichtige Hinweise
Junjie Luo was partially supported by CAS-DAAD Joint Fellowship Program for Doctoral Students of UCAS and partially supported by the DFG, project AFFA (NI 369/15 and BR 5207/1). Hendrik Molter was supported by the DFG, project MATE (NI 369/17). Ondřej Suchý was supported by grant 17-20065S of the Czech Science Foundation.
An extended abstract of this work appears in the proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) [36].

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

In recent years, modelling user engagement in social networks has received substantial interest [ 44, 45]. 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 [ 6, 15, 16, 25, 37, 46]. 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 [ 42]. 1
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. [ 46] 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|≤ b such that the k-core of GS 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 agains 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. [ 46] showed that Collapsed k-Core is NP-hard for any k ≥ 1 and gave a greedy algorithm to compute suboptimal solutions for the problem. However, for x = 0 and any fixed k ≥ 1, solving Collapsed k-Core is equivalent to finding b vertices such that after removing said vertices, the remaining graph is ( k − 1)-degenerate 2. 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|≤ b such that GS is r-degenerate?
It is easy to see that Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion. In 2010 Mathieson [ 38] 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 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 [ 20, 26]. For Vertex Cover already the first known FPT algorithm is deterministic single exponential linear time and the currently fastest algorithm runs in O(1.2738 b + b n) time [ 11]. For Feedback Vertex Set randomized algorithms with running time of such kind were known [ 19], whereas the running time of single exponential linear time deterministic algorithms was unsatisfactory [ 27, 35]. This changed with the linear time computable polynomial kernel of Iwata [ 29] which, combined with some previously known single exponential algorithms such as the O(3.619 bn O(1)) algorithm of [ 33], produces efficient algorithms of such kind. Very recently native deterministic single exponential linear time algorithms appeared [ 9], achieving O(3.460 bn) running time [ 30]. The aforementioned results concerning r-Degenerate Vertex Deletion in fact imply the hardness results shown by Zhang et al. [ 46] for Collapsed k-Core.
Chitnis and Talmon [ 14] recently studied the Edge k-Core problem: given a graph G, a budget b, and a goal p, can at most b edges be added to G to obtain a k-core containing at least p vertices? They showed the problem to be polynomial time solvable for k ≤ 2, while NP-complete for k ≥ 3. Furthermore, they showed that the problem is W[1]-hard with respect to ( b + k + p) and designed an algorithm with running time ( k + tw) O(tw+b) ⋅poly( n), where tw is the treewidth of the input graph G.
Collapsed k-Core with x = 0 (or r-Degenerate Vertex Deletion) can be also viewed as a special case of the Target Set Selection problem introduced by Kempe et al. [ 31]. Here one is given a graph G, a budget b, and a threshold function \(f: V(G) \to {\mathbb {N}}\). A vertex v gets activated once at least f( v) of its neighbors are activated. The question is whether there is an initial set (target set) of at most b vertices such that, if we initially activate this set, then eventually all vertices of the graph get activated. Collapsed k-Core with x = 0 corresponds to the case that the threshold function f( v) equals \(\deg (v)-k+1\) for every vertex v.
Target Set Selection is known to be NP-hard even for split graphs of diameter 2 [ 40] and the minimum size of a target set is APX-hard to approximate [ 12] and also resistant to parameterized approximation [ 4]. It is W[1]-hard with respect to feedback vertex set (and treewidth) [ 5], W[2]-hard with respect to budget b on split graphs [ 40], and FPT with respect to cluster editing number, vertex cover number, and feedback edge set number [ 40]. More tractability results can be obtained if the thresholds are bounded by a constant [ 5, 17, 28] or equal to half the degree of the vertex (majority constraint) [ 23]. We refer the reader to some of the papers [ 17, 40] for a more detailed survey of the results. A concept similar to Target Set Selection with the majority constraint is studied under the names “local influence”, “majority consensus”, “opinion forming”, etc. [ 41].
A somewhat dual problem to Target Set Selection is Harmless Set, where given the same input, the question is to find a set of at least b vertices in which each vertex has less than f( v) neighbors [ 3].
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, 38] 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 ≤ 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 ≤ 2 and k ≥ 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+ 4bn) time which means that it solves Feedback Vertex Set in O(9.487 bn) time (here, b is the solution size of Feedback Vertex Set). Cao [ 9] 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. A recent, even more thorough, analysis of an algorithm similar to Cao’s algorithm proves it to be the fastest known deterministic algorithm for Feedback Vertex Set [ 30].
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.

2 Hardness Results from the Literature

In this section, we gather and discuss known hardness results for Collapsed k-Core. Recall 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 [ 38] who 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. However, in the proof of Mathieson [ 38] 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 [ 38].

2.1 Counterexamples

Counterexample for Mathieson’s Reduction [ 38].
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 2 r + 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 describe how to repair the reduction (for r = 2) in the proof of Theorem 1.
Counterexample for the Reduction of Abrahamson et al. [ 1]
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.

2.2 Corrected Proof and Corollaries

Theorem 1 (Corrected from 38)
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 2 r + 1.
Proof
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 2 r + 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]. □
The following observation shows that the hardness result by Mathieson [ 38] (Theorem 1) easily transfers to Collapsed k-Core (also in the cases where x≠ 0).
Observation 1
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.
Proof
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). □
With that, we arrive at the following corollary.
Corollary 1
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\}\).
Note that r-Degenerate Vertex Deletion is known to be NP-hard for all r ≥ 0. 3 Hence, we also know that Collapsed k-Core is NP-hard for k ≤ 2 and all x ≥ 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 ≤ 2. Since Corollary 1 only applies for k ≥ 3 we first show in the following that the problem is W[1]-hard with respect to the combination of b and ( nx) for all k ≥ 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).

3.1 W[1]-hardness with Respect to b and nx

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 Corollary 1 even for k ≥ 3.
Proposition 1
Collapsed k-Core is W[1]-hard when parameterized by the combination of b and ( nx) for all k ≥ 1, even if the input graph is bipartite and \(\max \limits \{2,k\}\)-degenerate.
Proof
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 3) 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)| 3) 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 2 k − 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 eE 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 = { eESU W e≠∅}. Note that if e = { x, y}, eS E, and | S ∩{ x, y}|≤ 1, then the whole set U W e ∪{ x, y}∖ S is in the k-core of \(G^{\prime }\setminus S\) as each vertex in U W e ∪{ x, y}∖ S has at least k neighbors in U W e ∪{ x, y}∖ S. This means that each vertex in VS is in the k-core of \(G^{\prime }\setminus S\). Indeed, for an arbitrary vertex v in VS 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 eS E possibly no vertex of U W e is in the k-core of \(G^{\prime } \setminus S\), effectively shrinking it by 2 k − 1 vertices. However, this does not influence the other vertices in V, U, or W, since VS is in the k-core, as we already observed. If e = { x, y} and \(\{x,y\} \subseteq S\), then also the whole set U W e is not in the k-core as observed in the first implication. Thus, if | SV | = 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 + cb = 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 }\). □

3.2 Algorithm for k = 1

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 4 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 2
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.
Algorithm
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 SQ. 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.
Lemma 1
Algorithm 1 runs in O(2 x+ 2b( m + n)) time and in \(O(2^{O(b+\sqrt {bx})}\cdot n)\) time.
Proof
We first show by induction on the size of SQ 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 GS, and then removing isolated vertices in GS. 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( b n + x 2) 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)\). □
Next we show the claimed conditional lower bound on the running time for any algorithm for Collapsed k-Core with k = 1.
Lemma 2
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.
Proof
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. □
Before showing the correctness of Algorithm 1, we first show in the following lemma why in line 2 set Q should be bounded by b + x.
Lemma 3
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.
Proof
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 BQ = ∅. Let \(v_{1},v_{2}, \ldots , v_{r^{\prime }}\) be the vertices of the set SQ 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 BS 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 BS is non-empty and we let \(B \setminus S = \{v_{r^{\prime }+1}, \ldots , v_{r}\}\), i.e., { v 1,…, v r} = BQ. Hence, it always holds that v rB. Let \(G^{\prime }\) be the 1-core of GB 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 iBi < j 0}, deleting vertices in { v iBi > j 0} is not enough to make all vertices in { v jQXjj 0} collapse, which would be a contradiction.
To this end, we construct an injective function f that maps the vertices in B to vertices of QX. Considering the subsequence containing the vertices of QX 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 QX 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 QX 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 1,…, 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 SQ. For vV ( 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 iB we have f( i) < i, then let i 0 = 0 and j 0 = q 0. Otherwise, let i 0 be the largest i such that f( i) > i and j 0 = f( i 0). We consider the graph \(G_{j_{0}}\). Let \(V(G_{j_{0}})=B_{0} \uplus Q_{0} \uplus Y_{0} \uplus X\), where B 0 = { v iBi > j 0}, Q 0 = { v jQXjj 0}, \(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 0 and not contained in Q 0, and X is the 1-core of GB. Note that in \(G_{j_{0}}\) vertex \(v_{j_{0}}\) in the only vertex of Q 0 which is not contained in the image set of f restricted to B 0. Thus, we have
$$ Q_{0}=\{v_{j_{0}}\} \cup \bigcup_{v_{i} \in B_{0}} \{v_{f(i)}\}. $$
(1)
According to our selection of j 0, for every v iB 0 we have i 0 < j 0 < f( i) < i. Thus, for each vertex v iB 0 we have that
$$ \deg_{i}(v_{i})\leq \deg_{f(i)}(v_{f(i)}). $$
(2)
Let us count the number, denoted as N 0, of edges of the form { v i, v j} in \(G_{j_{0}}\) such that v iB 0 and v jQ 0. Since each edge of \(G_{j_{0}}\) incident on a vertex of Q 0 must have the other endpoint in B 0, we have that
$$ N_{0}=\sum\limits_{v_{j} \in Q_{0}} \deg_{j_{0}} (v_{j}) \ge \sum\limits_{v_{j} \in Q_{0}} \deg_{j} (v_{j}). $$
(3)
On the other hand, since edges towards Q 0 are always counted in \(\deg _{t}(v)\), we have that
$$ N_{0} \le \sum\limits_{v_{i} \in B_{0}} \deg_{i} (v_{i}). $$
(4)
Combining ( 3) and ( 4), we have that
$$ \begin{array}{@{}rcl@{}} 0 & \le& \sum\limits_{v_{i} \in B_{0}} \deg_{i} (v_{i}) - \sum\limits_{v_{j} \in Q_{0}} \deg_{j} (v_{j}) \\ & \overset{(1)}{=} &- \deg_{j_{0}} (v_{j_{0}}) + \sum\limits_{v_{i} \in B_{0}} (\deg_{i} (v_{i}) - \deg_{f(i)} (v_{f(i)})) \\ & \overset{(2)}{\le}& - \deg_{j_{0}} (v_{j_{0}}) + \sum\limits_{v_{i} \in B_{0}} 0 <0, \end{array} $$
which is a contradiction. □
Now we have all necessary pieces to prove Proposition 2.
Proof of Proposition 2
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 GS 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 BQ = ∅. 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 GS, is of size more than x, which is the case when line 4 does not apply, then SB 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 BQ = ∅. 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 BQ = ∅ 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. □

3.3 Algorithm for k = 2

Now we show how to adapt the algorithm for k = 1 to an algorithm for Collapsed k-Core with k = 2.
Theorem 2
Collapsed k-Core with k = 2 can be solved in O(1.755 x+ 4bn) 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.
The above theorem in particular yields an O(9.487 bn) 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| > 3 b + 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.
Lemma 4
Algorithm 2 runs in O(1.755 x+ 4bn) time and in \(O(2^{O(b+\sqrt {bx})}\cdot n)\) time.
Proof
We again first show by induction on the size of SQ 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 3 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–14 applies, then we have only one call and | Q|≤ 3 b + 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 GS [ 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( b n + x 2) edges or we are facing a no-instance, we have that the time complexity of the algorithm is O(1.7549 4b+xb 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+xn) and \(O(2^{O(b+\sqrt {bx})}\cdot n)\) as claimed. □
Next we claim the following conditional lower bound on the running time for any algorithm for Collapsed k-Core with k = 2.
Lemma 5
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.
Proof
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. □
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 6
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.
Proof
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 GB 2 is the same as the 2-core of GB 1 and the 2-core of GB 1 is a subset of the 2-core of GB. So the 2-core of GB 2 is a subset of the 2-core of GB, and hence no larger than x. Therefore B 2 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). □
The next lemma helps to show that line 14 is correct.
Lemma 7
If S and Q are realizable and line 14 of Algorithm 2 applies, and for every qQ there is no solution containing the complete set S ∪{ q}, then there is no solution completely containing S.
Proof
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 0 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 = BV ( D) is nonempty and \(x^{\prime }\) is the size of the 2-core of DB 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 = BV ( C 0) is nonempty, then let y be any vertex in B C and C y the connected component of C 0 containing y. By the definition of C 0 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 GB 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 0 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 1)|≥| V ( C 2)|≥… ≥| 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. □
Next, we show that the second part of line 2 of Algorithm 2 is correct.
Lemma 8
If S and Q are realizable and Q is of size more than 3 b + x, then there is no solution containing the complete set S and no vertex from Q.
Proof
Let S and Q be realizable with | Q|≥ 3 b + x + 1. Suppose for contradiction that B is a solution such that | B|≤ b, \(S \subseteq B\) and BQ = ∅. Let \(v_{1},v_{2}, \ldots , v_{r^{\prime }}\) be the vertices of the set SQ 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 BS is non-empty. We let \(B \setminus S = \{v_{r^{\prime }+1}, \ldots , v_{r}\}\), i.e., { v 1,…, v r} = BQ. In particular v rB. Without loss of generality, we can assume that for every vertex v iB, 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 iBS, 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 GB 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 iBi < j 0}, deleting vertices in { v iBi > j 0} is not enough to make all vertices in { v jQXjj 0} 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 QX (see also Fig.  5). Considering the subsequence containing the vertices of QX in the order in which they were added to Q, we split the last 3 b 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 1, j 2, j 3}, 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 1, j 2, j 3}, 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 QX 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 = | QX|− 3| B|≥ 1. There remain p vertices in QX 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 1,…, 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 SQ. For vV ( 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 tQ.
Now we select the special vertex \(v_{j_{0}} \in Q\). If for every vertex v iB we have \(i > \max \limits \{j \mid j \in f(i)\}\), then let i 0 = 0 and j 0 = q p. Otherwise, let i 0 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 0 = { v iBi > j 0}, Q 0 = { v jQXjj 0}, \(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 0 and not contained in Q 0, and X is the 2-core of GB. Note that in \(G_{j_{0}}\) vertex \(v_{j_{0}}\) is the only vertex of Q 0 which is not contained in any image set of f restricted to B 0. Thus, we have
$$ Q_{0}=\{v_{j_{0}}\} \cup \bigcup_{v_{i} \in B_{0}} \bigcup_{j \in f(i)} \{v_{j}\}. $$
(5)
According to our selection of j 0, for every i with v iB 0 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 iB 0 and every jf( i). Together with \(\deg _{t}(v_{t}) \ge 3\) for all v tQ, we have
$$ \deg_{i}(v_{i}) - \sum\limits_{j \in f(i)}\deg_{j}(v_{j})+6 \le 0 $$
(6)
for all v iB 0.
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 1, v 2,…, v r on B 0) or collapsed. It may happen that several vertices in Q 0 or Y 0 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 0Y 0 has at most one outgoing edge.
Then we consider the number, denoted by N 0, of edges of \(G_{j_{0}}\) of the form \(\overrightarrow {v_{i}v_{j}}\) such that the head v j is in Q 0. Since every vertex in Q 0 has at most one outgoing edge and \(\deg _{j_{0}}(v_{j}) \ge \deg _{j}(v_{j})\) for all v jQ 0, we have
$$ N_{0} \ge \sum\limits_{v_{j} \in Q_{0}} (\deg_{j_{0}}(v_{j})-1) \ge \sum\limits_{v_{j} \in Q_{0}} \deg_{j}(v_{j})-|Q_{0}|. $$
(7)
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 1 to M 2. 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
$$ N_{\overrightarrow{Y_{0}Q_{0}}} \le N_{\overrightarrow{B_{0}Y_{0}}}+N_{\overrightarrow{Q_{0}Y_{0}}}. $$
(8)
To show that, note that every vertex in Y 0 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
$$ N_{\overrightarrow{Y_{0}B_{0}}}+N_{\overrightarrow{Y_{0}Q_{0}}}+ N_{\overrightarrow{Y_{0}Y_{0}}}+N_{\overrightarrow{Y_{0}X}} \le N_{\overrightarrow{B_{0}Y_{0}}}+N_{\overrightarrow{Q_{0}Y_{0}}} + N_{\overrightarrow{Y_{0}Y_{0}}}. $$
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 0. Since the edges which have their heads in Q 0 have their tails from B 0Y 0Q 0, we have
$$ \begin{array}{@{}rcl@{}} N_{0} &=& N_{\overrightarrow{B_{0}Q_{0}}}+ N_{\overrightarrow{Y_{0}Q_{0}}} + N_{\overrightarrow{Q_{0}Q_{0}}}\\ &\le& N_{\overrightarrow{B_{0}Q_{0}}}+ N_{\overrightarrow{Y_{0}Q_{0}}} + (|Q_{0}|-N_{\overrightarrow{Q_{0}Y_{0}}})\\ &\overset{(8)}{\le}& N_{\overrightarrow{B_{0}Q_{0}}}+ (N_{\overrightarrow{B_{0}Y_{0}}}+N_{\overrightarrow{Q_{0}Y_{0}}}) + (|Q_{0}|-N_{\overrightarrow{Q_{0}Y_{0}}})\\ &=& N_{\overrightarrow{B_{0}Q_{0}}}+ N_{\overrightarrow{B_{0}Y_{0}}} + |Q_{0}|\\ &\le& {\sum}_{v_{i} \in B_{0}} \deg^{-} (v_{i}) + |Q_{0}|\\ &\le& {\sum}_{v_{i} \in B_{0}} \deg_{i} (v_{i}) + |Q_{0}|. \end{array} $$
(9)
The last inequality holds since for every vertex v iB 0, 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
$$ \begin{array}{@{}rcl@{}} 0 &=& N_{0}-N_{0}\\ & \le& {\sum}_{v_{i} \in B_{0}} \deg_{i} (v_{i})+|Q_{0}| - \left( {\sum}_{v_{j} \in Q_{0}} \deg_{j} (v_{j})-|Q_{0}| \right) \\ & =& {\sum}_{v_{i} \in B_{0}} \deg_{i} (v_{i}) - {\sum}_{v_{j} \in Q_{0}} \deg_{j} (v_{j}) +2|Q_{0}| \\ & =& {\sum}_{v_{i} \in B_{0}} \deg_{i} (v_{i}) - {\sum}_{v_{j} \in Q_{0}} (\deg_{j} (v_{j})-2) \\ & \overset{(5)}{=}& {\sum}_{v_{i} \in B_{0}} \deg_{i} (v_{i}) - \left( {\sum}_{v_{i} \in B_{0}}{\sum}_{j \in f(i)} (\deg_{j} (v_{j})-2) + \deg_{j_{0}}(v_{j_{0}})-2 \right) \\ & \overset{|f(i)|=3}{=}& {\sum}_{v_{i} \in B_{0}} \left( \deg_{i} (v_{i}) - {\sum}_{j \in f(i)} \deg_{j} (v_{j})+6 \right) - \deg_{j_{0}}(v_{j_{0}})+2 \\ &\overset{(6)}{\le} &0 - \deg_{j_{0}}(v_{j_{0}})+2 \\ & < &0, \end{array} $$
which is a contradiction. The last inequality holds since \(\deg _{t}(v_{t}) \geq 3\) for all v tQ. □
Proof of Theorem 2
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 GS 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 GS 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 | QS| for every realizable pair of S and Q, starting from the largest | QS| 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 BQ = ∅, 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 GS. 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 | QS| and v is the vertex selected by the algorithm on line 7. If there is a solution containing S ∪{ v} (in particular if vB), 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. □

3.4 Complexity on Cubic Graphs

Feedback Vertex Set is polynomial time solvable on graphs of maximum degree 3 [ 10, 43]. In fact, this is true even if some vertices of the graph cannot be taken into a solution and the bound on the maximum degree only holds for vertices that can take part in the solution [ 10]. This allows Cao [ 9] to improve his algorithm, which is very similar to Algorithm 2, by directly solving the instance already if the degree of all vertices of \(G^{\prime }\) not in Q is at most 3, achieving a running time of O(8 bn O(1)). 5 If also Collapsed k-Core with k = 2 could be solved in polynomial time on graphs, where all vertices (that can be taken into solution) have degree at most 3, then this would improve also the running time of our algorithm for Collapsed k-Core with k = 2 on general graphs.
In this subsection we show that the result of Cao et al. [ 10] probably does not generalize to Collapsed k-Core with k = 2, at least not in its full generality. To this end, we need the following generalization of our problem:
Collapsed 2-Core with Forbidden Vertices
Input: An undirected graph G = ( V, E), a partition of V into V 1 and V 2, and integers b and x.
Question: Is there a set \(S\subseteq V_{1}\) with | S|≤ b such that the 2-core of GS has size at most x?
Theorem 3
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 1 is 2.
An attentive reader might notice that Algorithm 2 actually deals with instances similar to those produced by Theorem 3 in polynomial time. We postpone the discussion of how this is possible after the proof of the theorem.
Proof of Theorem 3
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, ns + 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 1,…, v n} and E( G) = { e 1, e 2,…, e m}.
We start with \(G^{\prime }\) being a simple cycle on vertices C = { c 1,…, 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 1,…, 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,yy ∈{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 1,…, a n} and connect for each i ∈{1,…, n} the vertices h i and a i by a path P i with Lr + 1 internal vertices, where L = 5 m. The construction is illustrated on Fig.  7. Let us denote \(F=\bigcup _{i=1}^{n} F_{i}\).
To finish the construction, we let V 1 = F, \(V_{2}= V(G^{\prime }) \setminus F\), b = r s, 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 nr = 2 m 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 Lr + 1 internal vertices on each P i. Therefore, for each i, there are r − 1 + ( Lr + 1) = L internal vertices together in T i and P i. Finally, there are n vertices in A. Hence, N = m + m + 2 m + n L + n = 4 m + n + n L 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 iS, 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 + ( Lr + 1) = L vertices which are neither in B nor in \(V(G^{\prime \prime })\) for each i such that v iS.
Furthermore, for each j such that e jE( 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 iB≠∅ and let f i,yF iB. 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 ( Lr + 1) + 2 = Lr + 3 vertices and cannot be shared between different indices i. Let S = { v iF iB = ∅}. If | S| < s, then there are at least ns + 1 indices i such that F iB≠∅. That is,
$$ \begin{array}{@{}rcl@{}} |V(G^{\prime\prime})| &\ge& m+n+(n-s+1)(L-r+3)\\ &>& m + n +(n-s)L + L -(n-s+1)r\\ &\ge& 4m +n - b -\binom{s}{2} + (n-s)L\\ &=&x \end{array} $$
since
$$ L -(n-s+1)r \ge L -nr = 5m -2m > 3m-b -\binom{s}{2}. $$
Hence, | S|≥ s, and, as r s ≥| 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 iS, \(G^{\prime \prime }\) contains F i, T i, and P i by the above argument. This makes r + r − 1 + ( Lr + 1) = L + r vertices for each such i (not counting a i) and ( ns)( L + r) = n rr s + ( ns) L = 2 mb + ( ns) 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
$$ \begin{array}{@{}rcl@{}} |V(G^{\prime\prime})| &>& m +n +2m-b +(n-s)L +\left( m-\binom{s}{2}\right)\\ &=&4m+n-b -\binom{s}{2} +(n-s)L\\ &=&x. \end{array} $$
This would contradict B being a solution.
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,yB and also f y,xB, 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 xS and v yS, i.e., e jE( 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 1 = F have degree 2, and the instances are equivalent, this finishes the proof. □
An instance similar to the one constructed in Theorem 3 might actually occur during the run of Algorithm 2, i.e., \(G^{\prime }\) might be the 2-core of GS produced in step 3 of the algorithm with \(Q = V_{2}= V(G^{\prime }) \setminus F\). In particular, Algorithm 2 imposes no relation between | Q| and b, as the relation is actually between | Q| and | S| + b. The reason Algorithm 2 is able to deal with the instance in polynomial time is that we require it to solve the instance only if there is no solution containing any of the vertices of Q = V 2. Hence, it does not solve the instance, but merely rejects it, or, more precisely, does not search for vertices of the solution in this component (see Lemma 6).
The current algorithm deals with instances where all vertices of degree more than 2 in the 2-core belong to Q, in polynomial time. To generalize this in the most direct way, allowing the algorithm to deal in polynomial time with cases where all vertices of degree more than 3 in the 2-core belong to Q, we would need at least two ingredients:
(i)
If there is a solution to the component and there are vertices of degree at least 4 in the component, then there is a solution containing some vertex of degree at least 4 (an analogue of Lemma 6).
 
(ii)
A solution for each component of maximum degree at most 3, not containing any vertices of Q, can be found in polynomial time (an analogue of steps 8–14 of Algorithm 2).
 
Concerning (i), consider graph obtained from a disjoint union of a cycle C n and K 4 by adding an edge between an arbitrary vertex of the cycle and an arbitrary vertex of the K 4. The resulting graph has exactly one vertex of degree 4 (or more). However, for n ≥ 5, b = 1, and x = 4 this vertex is not part of any solution. Indeed, each solution is formed by a vertex of the cycle C n.
Concerning (ii), note specifically that it is not enough to find a minimum feedback vertex set of the component, as it may contain too many vertices. In particular, considering graph \(G^{\prime }\) constructed in Theorem 3 (without forbidden vertices), removing n vertices of A is sufficient to reduce the 2-core of the graph from Ω( n m) to O( m) vertices, whereas the minimum feedback vertex set is of size Θ( m). The budget spared on this component might help reduce the 2-core more significantly on some other component, which might have similar properties. This was never an issue with components of maximum degree 2, as the minimum feedback vertex set was always of size 1. Nevertheless, we leave open whether (ii) is true.
Hence, significantly new ideas will be needed to improve the running time of Algorithm 2.

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. Corollary 1 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, nx, or nb. 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 when parameterized by the combination of b, nx, 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 2
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 vS or v is part of the k-core of GS.
Proof
Let C be the ( k + b)-core of G. In CS the degree of each vertex is at least k + bb, hence CS is a subgraph of the k-core of GS. □
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 3
Let ( G, b, x, k) be an instance of Collapsed k-Core and \(G^{\prime }\) be the graph obtained from G by adding a universal vertex, then \((G^{\prime },b+1,x,k)\) is an equivalent instance of Collapsed k-Core.
Proof
Let ( G, b, x, k) be an instance of Collapsed k-Core and let \((G^{\prime },b^{\prime },x,k)\) be the instance formed by a graph \(G^{\prime }\) which is obtained from G by adding an universal vertex u, \(b^{\prime }=b+1\), and x and k from the original instance. We claim that the instances are equivalent.
First if S is a solution for ( G, b, x, k), then S ∪{ u} is a solution for \((G^{\prime },b^{\prime },x,k)\), as \(G \setminus S = G^{\prime } \setminus S^{\prime }\). Second, let \(S^{\prime }\) be a solution for \((G^{\prime },b^{\prime },x,k)\). If \(S^{\prime }\) contains u, then \(S^{\prime } \setminus \{u\}\) is a solution for G. Now suppose that \(S^{\prime }\) does not contain u and let v be an arbitrary vertex of \(S^{\prime }\). We claim that \(S^{\prime \prime }=(S^{\prime } \setminus \{v\}) \cup \{u\}\) is also a solution to \((G^{\prime },b^{\prime },x,k)\), since \(G^{\prime } \setminus S^{\prime \prime }\) is isomorphic to a subgraph of \(G^{\prime }\setminus S^{\prime }\). Indeed, consider the bijection φ, which maps each vertex of \(V(G) \setminus S^{\prime }\) to itself and v to u. To show that it is an isomorphism, it is enough to consider edges incident on v, however, as there is an edge between u and every vertex of \(V(G) \setminus S^{\prime }\), these definitely map to edges. Hence the k-core of \(G^{\prime } \setminus S^{\prime \prime }\) is at most as large as the k-core of \(G^{\prime }\setminus S^{\prime }\) and indeed \(S^{\prime \prime }\) is a solution to \((G^{\prime },b^{\prime },x,k)\). Now the equivalence of the instance follows from the case where u is in \(S^{\prime }\). □

4.1 W[1]-hard Cases

Considering a larger parameter than, e.g., the size of the dominating set, namely the clique cover number 6, 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 3
Collapsed k-Core is W[1]-hard when parameterized by the combination of b and the clique cover number of the input graph.
Proof
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 z v y| v zV i, v yV j},1 ≤ i < js. 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).
  • Denote \(k=2\max \limits _{1\leq i< j\leq s} |E_{i,j}|\), n = | V | and set b = s, \(x=N-N^{\prime }\) where \(N=2n^{4}+k+s+n+k\binom {s}{2}\) is the number of vertices in \(G^{\prime }\) we will construct and \(N^{\prime }=s+k\binom {s}{2}\).
  • For every \(V_{i},i=1,2,\dots ,s\), create a clique C i in \(G^{\prime }\), which contains all vertices in V i.
  • For every E i,j,1 ≤ i < js, create a clique C i,j of size k in \(G^{\prime }\), which contains 2 vertices \(v_{z,y},v^{\prime }_{z,y}\) for every edge v z v y in E i,j and k − 2| E i,j| more dummy vertices.
  • For every edge v z v yE i,j, add 4 edges v z,y v z, v z,y v y, \(v^{\prime }_{z,y}v_{z}\) and \(v^{\prime }_{z,y}v_{y}\) to \(G^{\prime }\).
  • Create a clique C of size 2 n 4 + k + s. Pick k + s arbitrary vertices in C, and make all these k + s vertices adjacent to all vertices in \(\bigcup _{i=1}^{s} C_{i}\). For every dummy vertex in \(\bigcup _{i=1}^{s}\bigcup _{j=i+1}^{s}C_{i,j}\), we add edges between this vertex and two distinct vertices in C. The size of C is large enough such that no pair of edges between E i,j and C share the same endpoint in C.
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 yS, where v zV i and v yV j. Since S is a clique, there is an edge v z v 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 2 n 4 + 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 st 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 SC 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 < js 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. □

4.2 Fixed-Parameter Tractable Cases

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 4
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. 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\}\), BXQ 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 qQ 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. □
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, nx, or nb.
Proposition 5
Collapsed k-Core is in FPT when parameterized by the cliquewidth of the input graph combined with k and either b, x, nx, or nb.
Proof
We first develop, for a fixed k a formula
$$ \mathtt{core}(B,X),$$
which should express that the set X contains the whole vertex set of the k-core of the graph GB. 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:
$$ \begin{array}{@{}rcl@{}} \mathtt{smalldeg}_{k}(v,A) &=& \forall x_{1} \in V \forall x_{2} \in V \ldots \forall x_{k} \in V \left( \bigwedge_{i=1}^{k} (x_{i} \in A \wedge \mathtt{adj}(v, x_{i}))\right) \\ &\implies& \bigvee_{1\le i < j \le k} x_{i}=x_{j}. \end{array} $$
Now the sought formula is
$$ \begin{array}{@{}rcl@{}} \mathtt{core}(B,X) &=& \forall A \subseteq V (A \cap B = \emptyset \wedge X\subseteq A \wedge X\neq A) \\ &\implies& \exists v \in V (v \in A) \wedge \mathtt{smalldeg}_{k}(v,A). \end{array} $$
This formula is of length O( k 2). 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:
$$ \begin{array}{@{}rcl@{}} \mathtt{sizeatmost}_{s}(S) &= &\forall x_{1} \in V \forall x_{2} \in V {\ldots} \forall x_{s} \in V \forall x_{s+1} \in V (\bigwedge_{i=1}^{s+1} x_{i} \in S )\\ &\implies& \bigvee_{1\le i < j \le s+1} x_{i}=x_{j}. \end{array} $$
The next formula bounds the size to at most ns:
$$ \begin{array}{@{}rcl@{}} &&\mathtt{sizeatmost}_{n-s}(S) = \\ &&\exists x_{1} \in V \exists x_{2} \in V {\ldots} \exists x_{s} \in V \left( \bigwedge_{i=1}^{s} x_{i} \notin S \right) \wedge \left( \bigwedge_{1\le i < j \le s} x_{i} \neq x_{j}\right). \end{array} $$
Both these formulae have length O( s 2).
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 2 + b 2). 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 2 + x 2). The result for parameterization by the cliquewidth, k, and nx 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 2 + ( nx) 2). Finally, the result for parameterization by the cliquewidth, k, and nb 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 2 + ( nb) 2). □

4.3 Kernelization Lower Bounds

In the final subsection of this section, we show that Collapsed k-Core does not admit a polynomial kernel when parameterized by rather large parameter combinations.
We employ the OR-cross-composition framework by [ 7] to refute the existence of a polynomial kernel for a parameterized problem under the assumption that \({\textsf {NP}}\not \subseteq {{\textsf {coNP}}/poly}\), the negation of which would cause a collapse of the polynomial-time hierarchy to the third level. Informally, in an OR-cross-composition, we have to compose many problem instances of an NP-hard problem into one big instance of the problem we want to investigate. This composition should then have the property that the big instance is a YES-instance if and only if at least one of the input instances is a YES-instance. This then refutes polynomial kernels for the problem under investigation when parameterized by any parameter that only depend on the maximum size of the input instances and only logarithmically on the number of input instances. In order to formally describe the framework, we need some definitions first.
An equivalence relation \(\mathcal {R}\) on the instances of some problem L is a polynomial equivalence relation if
1.
one can decide for each two instances in time polynomial in their sizes whether they belong to the same equivalence class, and
 
2.
for each finite set S of instances, \(\mathcal {R}\) partitions the set into at most \((\max \limits _{x \in S} |x|)^{O(1)}\) equivalence classes.
 
Using this, we can now define OR-cross-compositions.
An OR-cross-composition of a problem \(L\subseteq {\varSigma }^{*}\) into a parameterized problem P (with respect to a polynomial equivalence relation \(\mathcal {R}\) on the instances of L) is an algorithm that takes T \(\mathcal {R}\)-equivalent instances x 1,…, x T of L and constructs in time polynomial in \({\sum }_{i=1}^{T} |x_{i}|\) an instance ( x, k) of P such that
1.
k is polynomially upper-bounded in \(\max \limits _{1\leq i\leq T}|x_{i}|+\log (T)\) and
 
2.
( x, k) is a YES-instance of P if and only if there is an i ∈ [ T] such that x i is a YES-instance of L.
 
If an NP-hard problem L OR-cross-composes into a parameterized problem P, then P does not admit a polynomial kernel, unless \({\textsf {NP}}\subseteq \text {{\textsf {coNP}}/poly}\) [ 7].
We first show an OR-cross composition from Cubic Vertex Cover.
Theorem 4
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}\).
Proof
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≤iT− 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.
  • Set \(b=s+2ks\log {T}\) and \(x=N-N^{\prime }\), 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^{\prime }=s+2ks\log {T}+\frac {3}{2}n\). (Note that \(\frac {3}{2}n\) is integer since each G i is a 3-regular graph and this is the number of its edges.)
  • First for every vertex v p in V, create a vertex v p in G.
  • For all 0 ≤ iT − 1 and 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_{j}^{d}}\) \((0 \leq j \leq \log {T}-1, d \in \{0,1\})\), and all of them have the same size of 2 k s. 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 ∈{0,1} for \(0 \leq j \leq \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}}\) for all 0 ≤ iT − 1 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 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 ≤ iT − 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 ∈{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 2 k s − ( 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 IS| vertices in S with vertices in V IS. 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 SV, 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 SV, we get a vertex set SV which covers all vertices in \({V_{i}^{E}}\) at least once. And | SV |≤ s, since \(V_{I} \subseteq S\) and \(|V_{I}|=2ks\log {T}\). This corresponds to a vertex cover of size s in G i. □
Lastly, we show that there is a simple OR-cross composition [ 7, 20] from Collapsed k-Core onto itself. Note that the parameter combination of the following result is incomparable to that of Theorem 4.
Proposition 6
For all k ≥ 1 Collapsed k-Core does not admit a polynomial kernel when parameterized by the combination of b, nx, and the bandwidth of the input graph unless \({\textsf {NP}}\subseteq \text {{\textsf {coNP}}/poly}\).
Proof
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 1, b 1, x 1, k) and ( G 2, b 2, x 2, k) are \(\mathcal {R}\)-equivalent if | V ( G 1)| = | V ( G 2)|, b 1 = b 2 and x 1 = x 2. 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≤iT 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 ≤ iT 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 2, and add all edges between G i and C i and between C i and \(C_{i}^{\prime }\). Note that G contains T( n + 2 n 2) 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 2 n 2 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 iS 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 iS. Therefore the k-core of GSV ( 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 2 n 2 − 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 | SC i|≥ n 2k and | SC j|≥ n 2k, 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 + 2 n 2) 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 | SV ( G i)|≤ b. If \(|V(G_{i}) \setminus (S \cup S^{\prime })| > x\), which can only happen if | SV ( G i)| < b, then we can remove vertices from S ∖ ( C iV ( G i)) and add vertices from \(G_{i} \setminus (S \cup S^{\prime })\) to S until | SV ( G i)| = b. This will not influence the collapsed vertices in \(S^{\prime }\). Then we get a vertex set S i = SV ( G i), and the k-core of G iS i has size at most x. □

5 Conclusion

Our results highlight a dichotomy in the computational complexity of Collapsed k-Core for k ≤ 2 and k ≥ 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 solvable in polynomial time if there are no forbidden vertices. 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.

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 and to the anonymous referees of IPEC and this journal for detailed comments that helped to significantly improve the presentation of the paper.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://​creativecommons.​org/​licenses/​by/​4.​0/​.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Footnotes
1
Note that the k-core of a graph is uniquely determined.
 
2
A graph G is r-degenerate if every subgraph of G has a vertex with degree at most r [ 21].
 
3
Theorem 1 states NP-hardness of r-Degenerate Vertex Deletion for r ≥ 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 [ 26].
 
4
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.
 
5
Actually, using an analysis similar to that of Lemma 4, one can show that the improved algorithm of Cao runs in O(6.75 bn O(1)) time.
 
6
The clique cover number of a graph G is the minimum number of cliques in G such that their union contains all vertices of G.
 
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 8/2021

Theory of Computing Systems 8/2021 Zur Ausgabe

Premium Partner