Improved FPT Algorithms for Deletion to Forest-Like Structures

Abstract

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset $S\subseteq V(G)$ of size at most k such that $G-S$ is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time ${\mathcal {O}}^{\star }(2.7^k)^{*}$. In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in $G-S$ has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers $k,\ell \in {{\mathbb {N}}}$, and the objective is to test whether there exists a vertex subset S of size at most k, such that $G-S$ is $\ell$ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms.

• 1. Independent Feedback Vertex Set can be solved in time ${\mathcal {O}}^{\star }(2.7^k)$.

• 2. Pseudo Forest Deletion can be solved in time ${\mathcal {O}}^{\star }(2.85^k)$.

• 3. Almost Forest Deletion can be solved in time ${\mathcal {O}}^{\star }(\min \{2.85^k \cdot 8.54^\ell ,2.7^k \cdot 36.61^\ell ,3^k \cdot 1.78^\ell \})$.

1 Introduction

Feedback Vertex Set (FVS) is a classical NP-complete problem and has been extensively studied in all subfields of algorithms and complexity. In this problem we are given an undirected graph G and a non-negative integer k as input, and the goal is to check whether there exists a subset $S\subseteq V(G)$ (called feedback vertex set or in short fvs) of size at most k such that $G-S$ is a forest. This problem originated in combinatorial circuit design and found its way into diverse applications such as deadlock prevention in operating systems, constraint satisfaction and Bayesian inference in artificial intelligence. We refer to the survey by Festa et al. [1] for further details on the algorithmic study of feedback set problems in a variety of areas like approximation algorithms, linear programming and polyhedral combinatorics.

FVS has played a pivotal role in the development of the field of Parameterized Complexity. The earliest known FPT algorithms for FVS go back to the late 80 s and the early 90 s [2, 3] and used the seminal Graph Minor Theory of Robertson and Seymour. These algorithms are quite impractical because of large hidden constants in the run-time expressions. Raman et al. [4] designed an algorithm with running time $\mathcal {O}^\star (2^{\mathcal {O}(k\log \log k)})$ which basically branched on short cycles in a bounded search tree approach. For FVS, the first deterministic $\mathcal {O}^\star (c^k)$ algorithm was designed only in 2005; independently by Dehne et al. [5] and Guo et al. [6]. It is important to note here that a randomized algorithm for FVS with running time $\mathcal {O}^\star (4^k )$ was known in as early as 1999 [7]. The deterministic algorithms led to the race of improving the base of the exponent for FVS algorithms and several algorithms [8,9,10,11,12,13,14], both deterministic and randomized, have been designed. Until recently, the best known deterministic algorithm for FVS ran in time $\mathcal {O}^\star (3.619^k)$ [13], while the Cut & Count technique by Cygan et al. [11] gave the best known randomized algorithm running in time $\mathcal {O}^\star (3^k)$. However, both these algorithms have been improved; Iwata and Kobayashi [12] designed the fastest known deterministic algorithm with running time $\mathcal {O}^\star (3.460^k)$ and Li and Nederlof [14] designed the fastest known randomized algorithm with running time $\mathcal {O}^\star (2.7^k)$. The success on FVS has led to the study of many variants of FVS in literature such as Connected FVS [11, 15], Independent FVS [16,17,18], Simultaneous FVS [19, 20], Subset FVS  [21,22,23,24,25], Pseudoforest Deletion [26, 27], Generalized Pseudoforest Deletion [27], and Almost Forest Deletion [28, 29].

1.1 Our Problems, Results and Methods

In this paper we study three problems around FVS, namely, Independent FVS, Almost Forest Deletion, and Pseudoforest Deletion. We first define the generalizations of forests that are considered in these problems. We say that a graph F is an $\ell$-forest, if we can delete at most $\ell$ edges from F to get a forest. That is, F is at most $\ell$ edges away from being a forest. On the other hand, a pseudoforest is an undirected graph, in which every connected component has at most one cycle. Now, we are ready to define our problems.

Independent FVS (IFVS): Given a graph G and a non-negative integer k, does there exist a fvs S of size at most k, that is also an independent set in G? Almost Forest Deletion (AFD): Given a graph G and two non-negative integers k and $\ell$, does there exist a vertex subset S of size at most k such that $G-S$ is an $\ell$-forest? Pseudoforest Deletion (PDS): Given a graph G and a non-negative integer k, does there exist a vertex subset S of size at most k such that $G-S$ is a pseudoforest?

Given an instance of FVS, by subdividing every edge we get an instance of Independent FVS, which is a reduction from FVS to Independent FVS leaving k unchanged showing that it generalizes FVS. On the other hand setting $\ell =0$ in Almost Forest Deletion results in FVS. The best known algorithms for Independent FVS, Almost Forest Deletion, and Pseudoforest Deletion are ${\mathcal {O}}^{\star }(3.619^k)$ [17], ${\mathcal {O}}^{\star }(5^k4^\ell )$ [29], and ${\mathcal {O}}^{\star }(3^k)$ [26], respectively. Our main objective is to improve over these running times for the corresponding problems. Our paper can be briefly summarized as follows.

Table 1 Summary of existing and new results

To achieve improvements and tackle Independent FVS and Almost Forest Deletion at once, we propose a more generalized version of the Almost Forest Deletion problem.

Setting $\ell = 0, R = \varnothing$ we get the Independent FVS problem. A simple polynomial time reduction, where we subdivide every edge and add all the subdivision vertices to R, yields an instance of RIAFD, given an instance of Almost Forest Deletion. The reduction leaves $\ell$ and k unchanged.

To describe our results, we first summarize the method of Li and Nederlof [14](for FVS) which we adopt accordingly. The main observation guiding the method is the fact that after doing some simple preprocessing on the graph, we can ensure that a large fraction of edges are incident on every solution to the problem. This leads to two-step algorithms, one for the dense case and the other for the sparse case. In particular, if we are aiming for an algorithm with running time $\mathcal {O}^\star (\alpha ^k)$, then we do as follows.

• Dense Case: In this case, the number of edges incident to any FVS of size k is superlinear (in k), and we select a vertex into our solution with probability at least $\frac{1}{\alpha }$.

• Sparse Case: Once the dense case is done, we know that we have selected vertices, say $k_1$, with probability $( \frac{1}{\alpha })^{k_1}$. Now, we know that the number of edges incident to an FVS of the graph is $\mathcal {O}(k)$ and the existence of solution S of size at most k, implies that the input graph has treewidth at most $k+1$. Now, using this fact and the fact that deleting the solution leaves a graph of constant treewidth, we can actually show that graph has treewidth $(1-\Omega (1))k=\gamma k$ (in [14] as well as our paper, this is referred to as the small separator lemma). This implies that if we have an algorithm on graphs of treewidth ($\textbf{tw}$) with running time $\beta ^\textbf{tw}$, such that $\beta ^\gamma \le \alpha$, then we get the desired algorithm with running time $\mathcal {O}^\star (\alpha ^k)$.

So a natural approach for our problems which are parameterized by solution size is to devise an algorithm using another algorithm parameterized by treewidth with an appropriate base in the exponent, along with probabilistic reductions with a good success probability. However, to get the best out of methods of Li and Nederlof [14], it is important to have an algorithm parameterized by treewidth that is based on Cut & Count method [11]. However, for all the problems we consider, only non Cut & Count algorithms were known. Thus, our first result is as follows.

Theorem 1.1

There exists an ${\mathcal {O}}^\star \left( 3^{\textbf{tw}}\right)$ time Monte-Carlo algorithm that given a tree decomposition of the input graph of width $\textbf{tw}$ solves the following problems:

• 1. Restricted-Independent Almost Forest Deletion in exponential space.

• 2. Pseudoforest Deletion in exponential space.

Note that a yes-instance of RIAFD has treewidth $k+\ell +1$. Thus, as our first result, we design a randomized algorithm based on Theorem 1.1 and iterative compression with running time ${\mathcal {O}}^{\star }(3^k\cdot 3^\ell )$ for RIAFD. This yields ${\mathcal {O}}^{\star }(3^k)$ and ${\mathcal {O}}^{\star }(3^k \cdot 3^\ell )$ running time algorithms for Independent FVS and Almost Forest Deletion, respectively, which take polynomial space (though, these do not appear in literature). Next, we devise probabilistic reduction rules to implement the first step in the method of Li and Nederlof [14]. We analyze these rules by modifying the analysis of their lemmas to get an $\mathcal {O}^\star (2.85^k \cdot 8.54^\ell )$ time algorithm that takes polynomial space, and an $\mathcal {O}^\star (2.7^k\cdot 36.61^\ell )$ time algorithm that takes exponential space for solving RIAFD. All these algorithms, while progressively improving the dependence on k slightly, significantly worsen the dependence on $\ell$. Therefore, to obtain an algorithm with an improved dependence on $\ell$, we describe a procedure to construct a tree decomposition of treewidth at most $k + \frac{3}{5.769}\ell +\mathcal {O}(\log (n))$ given a solution of size k to an instance of RIAFD. This procedure, when combined with an iterative compression routine, yields an $\mathcal {O}^\star (3^k \cdot 1.78^\ell )$ algorithm for RIAFD. This brings us to the following result.

Theorem 1.2

There exist Monte-Carlo algorithms that solves the RIAFD problem in

• 1. ${\mathcal {O}}^{\star }(3^k \cdot 3^\ell )$ time and polynomial space.

• 2. ${\mathcal {O}}^{\star }(2.85^k \cdot 8.54^\ell )$ time and polynomial space.

• 3. ${\mathcal {O}}^{\star }(2.7^k \cdot 36.61^\ell )$ time and exponential space.

• 4. ${\mathcal {O}}^{\star }(3^k \cdot 1.78^\ell )$ time and exponential space.

As a corollary to Theorem 1.2, we get the following result about Independent FVS.

Theorem 1.3

There exist Monte-Carlo algorithms that solves the Independent FVS in:

• 1. ${\mathcal {O}}^\star (3^{\textbf{tw}})$ time, given a tree decomposition of width $\textbf{tw}$.

• 2. ${\mathcal {O}}^{\star }(2.85^k)$ time and polynomial space.

• 3. ${\mathcal {O}}^{\star }(2.7^k)$ time and exponential space.

Although we have a deterministic ${\mathcal {O}}^{\star }({3^k})$ algorithm for Pseudoforest deletion given by Bodlaender et al. [26] which runs in exponential space, to make use of the techniques from [14] we develop our Cut & Count algorithm which has the same asymptotic running time. However, even with our Cut & Count algorithm, we cannot make full use of the methods of Li and Nederlof [14] and only get the following improvement.

Theorem 1.4

There exists a Monte-Carlo algorithm that solves Pseudoforest Deletion in ${\mathcal {O}}^{\star }(2.85^k)$ time and polynomial space.

2 Preliminaries

For a set A, $\left( {\begin{array}{c}A\\ \cdot ,\cdot ,\cdot \end{array}}\right)$ denotes the set of all partitions of A into three subsets. Let $G=(V,E)$ be an undirected graph, where V is the set of vertices and E is the set of edges. We also denote V(G) to be the vertex set and E(G) to be the edge set of graph G. Also, $|V| = n$ and $|E|= m$. For a vertex subset $S\subseteq V(G)$, G[S] denotes the subgraph induced on the vertex set S, and E[S] denotes the set of edges in G[S]. For $S,T \subseteq V$, E[S, T] denotes the edges intersecting both S and T, i.e. the “cut edges”. For a vertex subset $V'$, the graph $G - V'$ denotes the graph $G[V{\setminus } V']$. For an edge subset $E'$, the graph $G - E'$ denotes the graph $G'=(V,E{\setminus } E')$. For a vertex $v\in V$, deg(v) denotes the degree of the vertex, i.e., the number of edges incident on v. For a vertex subset $S\subseteq V(G)$, $deg(S)=\sum _{v\in S}deg(v)$. Given an edge $e=(u,v)$, the subdivision of the edge e is the addition of a new vertex between u and v, i.e., the edge e is replaced by two edges (u, w) and (w, v), where w is the newly added vertex. Here, w is called a “subdivision vertex”. Now, we make note of the following lemma on the number of connected components of a forest.

Lemma 2.1

([11]) A graph with n vertices and m edges is a forest iff it has at most $n-m$ connected components.

Definition 2.2

([11]) A tree decomposition of a graph $G=(V,E)$ is a pair ${\mathbb {T}}=(\{B_x\; | \; x \in I \},\; T=(I,F))$, where T is a tree and $\{B_x\;|\;x\in I\}$ is a collection of subsets (called bags) of V such that,

• 1. $\bigcup _{x\in I}B_x=V$

• 2. For all $(u,v)\in E$ there is an $x\in I$ with $\{u,v\}\subseteq B_x$

• 3. For all $v\in V$, the set of nodes $\{x\in I\;|\,v\in B_x\}$ forms a connected subtree in $T=(I,F)$.

The width of the tree decomposition ${\mathbb {T}}$ is $\text {max}_{x\in I}\,|B_x|-1$. The treewidth of a graph G, denoted by $\textbf{tw}(G)$, is the minimum width over all tree decompositions of G.

We sometimes abuse notation and use $\textbf{tw}({\mathbb {T}})$ to denote the width of the tree decomposition ${\mathbb {T}}$. For the definition above, if there are parallel edges or self loops we can just ignore them, i.e., a tree decomposition of a graph with parallel edges and self loops is just the tree decomposition of the underlying simple graph (obtained by keeping only one set of parallel edges and removing all self loops).

There is also the notion of a nice tree decomposition which is used in this paper. In literature, there are a few variants of this notion that differ in details. We use the one described by Cygan et al. [11], with introduce edge nodes and root bag and leaf bags of size zero. A nice tree decomposition is a tree decomposition $(\{B_x\;|\;x\in I\}$, $T=(I,F))$ where T is a rooted tree and the nodes are one of the following five types. With each bag in the tree decomposition, we also associate a subgraph of G; the subgraph associated with bag x is denoted $G_x = (V_x, E_x)$. We give each type together with how the corresponding subgraph is formed.

• Leaf nodes x. x is a leaf of T; $|B_x|=0$ and $G_x=(\varnothing ,\varnothing )$ is the empty graph.

• Introduce vertex nodes x. x has one child, say y. There is a vertex v with $B_x=B_y\cup \{v\}$, $v\notin B_y$ and $G_x=(V_y\cup \{v\},E_y)$, i.e., $G_x$ is obtained by adding an isolated vertex v to $G_y$.

• Introduce edge nodes x. x has one child, say y. There are two vertices $v,w\in B_x$, $B_x=B_y$ and $G_x=(V_y,E_y\cup \{(v,w)\})$, i.e., $G_x$ is obtained from $G_y$ by adding an edge between these two vertices in $B_x$. If we have parallel edges, we have one introduce edge node for each parallel edge. A self loop with endpoint v is handled in the same way, i.e., there is an introduce edge node with $v\in B_x$ and $G_x$ is obtained from $G_y$ by adding the self loop on v.

• Forget vertex nodes x. x has one child, say y. There is a vertex v such that $B_x=B_y \setminus \{v\}$ and $G_x$ and $G_y$ are the same graph.

• Join nodes x. x has two children, say y and z. $B_x=B_y=B_z$, $V_y\cap V_z=B_x$ and $E_y\cap E_z=\varnothing$. $G_x=(V_y\cup V_z,E_y\cup E_z)$, i.e., $G_x$ is the union of $G_y$ and $G_z$, where the vertex set $B_x$ is the intersection of the vertex sets of these two graphs.

For the Cut & Count algorithms, the following lemma is essential. For a family of sets ${{\mathcal {F}}}$ over a universe U, we say that a weight function $w :U \mapsto {{\mathbb {N}}}$ isolates ${{\mathcal {F}}}$, if there is a unique set S in ${{\mathcal {F}}}$ with minimum weight w(S). Here, $w(S)=\sum _{x\in S} w(x)$.

Lemma 2.3

([30, Isolation Lemma]) Let ${\mathcal {F}} \subseteq 2^U$ be a non-empty set family over a universe U. For each $u\in U$, choose a weight $\omega \in \{1, 2, \ldots W\}$ uniformly and independently at random. Then $\Pr [\omega \text { isolates } {\mathcal {F}}] \ge 1 - |U|/W$.

In the Cut & Count algorithms and proofs, for a function $f: S \rightarrow T$, given a set R, $f|_R$ refers to the function f with its domain restricted to R. Formally, $f|_R$ is a function from R to a subset of T such that $f|_R(r) = f(r)$ for all $r \in R$. Given values u and v, $f[u \rightarrow v]$ refers to a function with u in domain and v in range with all mappings from S to T preserved and u mapped to v. Formally, $f[u \rightarrow v]$ is a function from $S \cup \{u\}$ to $T \cup \{v\}$ such that $f[u \rightarrow v](s) = f(s)$ for all $s \in S$ and $f[u \rightarrow v](u) = v$. Also, we define $f^{-1}(s):= \{x | x \in S \wedge f(x) = s\}$. We use the Iverson’s bracket notation [b] for a Boolean predicate [b] which denotes 1 if b is True and 0 otherwise.

In this paper, we will be dealing with randomized algorithms with one-sided error-probability, i.e. only false negatives are possible. The success-probability of an algorithm is the probability that the algorithm finds a solution, given that at least one such solution exists. We define high-probability to be probability at least $1 - \frac{1}{2^{c|x|}}$ or sometimes $1 - \frac{1}{|x|^{c}}$, where $\vert x\vert$ is the input size and c is a constant. Given an algorithm with constant success-probability, we can boost it to high-probability by performing ${\mathcal {O}}^{\star }(1)$ independent trials. We cite the following folklore observation:

Lemma 2.4

([14, Folklore]) If a problem can be solved with success probability $\frac{1}{S}$ and in expected time T, and its solutions can be verified for correctness in polynomial time, then it can also be solved in ${\mathcal {O}}^{\star }(S \cdot T )$ time with high probability.

We will use the following notion of separations in a graph from [14]:

Definition 2.5

([14, Simple Separator]) Given a graph $G=(V,E)$, a partition $(A,B,S) \in \left( {\begin{array}{c}V(G)\\ \cdot ,\cdot ,\cdot \end{array}}\right)$ of V is a (simple) separation if there are no edges between A and B.

Definition 2.6

([14, Three-Way Separator]) Given a graph $G = (V, E)$, a three-way separator is a partition $(S_{\{1\}}, S_{\{2\}}, S_{\{3\}}, S_{\{1,2\}}, S_{\{1,3\}},$ $S_{\{2,3\}}, S_{\{1,2,3\}})$ of V such that there are no edges between any two sets $S_I$, $S_J$ whose sets I and J are disjoint.

A $\beta$-separator for a graph $G=(V,E)$ is a set of vertices whose removal from G leaves no connected component of size larger than $\frac{|V|}{\beta }$, where $\beta > 0$ is some constant. Thus, a $\beta$-separator is a balanced separator of the graph. More generally, one can define a $\beta$-separator with respect to a weight function on the vertices. It is a well-known fact that a $\beta$-separator of cardinality $\beta$ exists for forests and can be computed in polynomial time (for e.g., see Lemma 3.1 in [14]). We now give a method, which is a simple extension to the aforementioned construction, to construct a $\beta$-separator of a graph G given a tree decomposition of width $\textbf{tw}$.

Lemma 2.7

Given a graph $G=(V,E)$ on n vertices with vertex weights $\omega (v)$ and its tree decomposition ${\mathbb {T}}$ of width $\textbf{tw}$, for any $\beta > 0$, we can delete a set S of $\beta (\textbf{tw}+1)$ vertices so that every connected component of $G - S$ has weight at most $\frac{\omega (V)}{\beta }$, in polynomial time.

Proof

Given a bag x of ${\mathbb {T}}$, we define the weight of the subtree rooted at x (w(x)) to be the sum of weights of vertices present in the set formed by union of all bags in the subtree of x. Formally, $w(x):= \sum \limits _{v \in V_x} \omega (v)$. Start with an empty set S.

Exhaustively, select a bag x of maximal depth such that $w(x) > \frac{\omega (V)}{\beta }$, then remove the bag x and its subtree and add all vertices in $B_x$ to the set S. Also, delete the vertices in $B_x$ from all other bags. Note that the maximality condition assures us that the subtrees rooted at the children of x have total weight at most $\frac{\omega (V)}{\beta }$ each. Moreover, by deleting the subtree rooted at x, we remove at least $\frac{\omega (V)}{\beta }$ weight, which can happen at most $\beta$ times. Since each bag has size at most $\textbf{tw}+1$, the total number of vertices added to S is at most $\beta (\textbf{tw}+1)$.

To see how there are no connected components of weight more than $\frac{\omega (V)}{\beta }$ in $G - S$, suppose that the tree decomposition ${\mathbb {T}}$ is reduced to the tree decomposition $\mathbb {T'}$ after the above algorithm. Now, assume that a connected component C of weight more than $\frac{\omega (V)}{\beta }$ exists in $G - S$. Then all of its vertices in their entirety must lie inside ${\mathbb {T}}'$ (since all children of a deleted bag have weight at most $\omega (V)/\beta$). Now, take the vertex of C which is at the least depth in ${\mathbb {T}}'$ and say it belongs to the bag c. Then, all the members of its connected component have to appear in the subtree rooted at c. Therefore, $w(c) > \frac{\omega (V)}{\beta }$ which would mean that this is not the terminal condition for our algorithm.

From the description of the algorithm it is easy to see that it runs in polynomial time. $\square$

In [14], the authors presented a method involving randomized reductions and small separators to get faster randomized algorithms for FVS. It turns out that this method can be generalized to work for a certain set of “vertex-deletion problems”. We will now describe the basic structure of this method and will follow this outline wherever this method is used in the rest of the paper.

Throughout this outline, assume that we are working on some vertex-deletion problem ${\mathcal {P}}$. Let $G=(V,E)$ be the graph involved in a given instance of ${\mathcal {P}}$. A valid solution $S\subseteq V$ is a set of vertices of G which solves the given problem instance of ${\mathcal {P}}$.

The method is divided into two cases: a dense case and a sparse case.

Dense Case: The algorithm goes into this case when for a given instance all the existing solution sets are of high average degree. In formal terms, every set $S \subseteq V$ of size k which is a valid solution of the given instance satisfies $deg(S) > c\cdot k$, where $c = \Theta (1)$.

To handle this case, a vertex $v\in V$ is sampled randomly based on a weight function $\omega (v)$ which depends on deg(v), deletes v and makes appropriate updates to the parameters. In this paper, we use $\omega (v) = deg(v) - 2$ for all the problems discussed. This process acts like a probabilistic reduction rule for the problem as it may fail with certain probability.

Sparse Case: The algorithm goes into this case when for a given instance there exists a solution set which has low average degree. In formal terms, there exists a vertex subset $S \subseteq V$ of size k which is a valid solution of the given instance and satisfies $deg(S) \le c \cdot k$, where $c = {\mathcal {O}}(1)$. Due to this reason, the number of edges in the given graph can be bounded, thus the input graph G is sparse.

The proof for the small separator lemma in [14] doesn’t require the remaining graph, i.e. the graph obtained by deleting the solution set, to be a forest only. As long as there is a good $\beta$-separator of the graph $G-S$, the proof works. Lemma 2.7 helps to construct such a $\beta$-separator of size $\beta (\textbf{tw}+1)$ for a graph with given tree decomposition of width $\textbf{tw}$.

The small separator helps to construct a tree decomposition of small width, given a solution set with bounded degree. The idea suggested in [14] was to use iterative compression techniques to construct a solution utilizing the small separator. This also requires solving a bounded degree version of the problem, which can be done using Cut & Count based algorithms. Specific details for each problem will be explained in the corresponding sections in due course.

3 Restricted-Independent Almost Forest Deletion

In this section we give our algorithm for RIAFD and prove Theorem 1.2 and the first part of Theorem 1.1. We first formally show that RIAFD is a generalization of Almost Forest Deletion. For any instance G of Almost Forest Deletion, subdivide the edges of G and add all the newly created subdivision vertices to R. The parameters k and $\ell$ remain the same.

Lemma 3.1

Given an instance of Almost Forest Deletion $(G=(V,E),k,\ell )$, an equivalent instance of RIAFD, $(G'(V',E'),k',\ell ',R)$, can be constructed as follows:

• 1. Start with $V' = V, E' = \varnothing , R = \varnothing$.

• 2. For each $e=(u,v) \in E$, add a vertex $v_e$ to $V'$ as well as to R. Add edge $(u,v_e)$ and $(v_e,v)$ to $E'$ (Essentially, subdivide e).

• 3. $k' = k, \ell ' = \ell$.

In this section, we present fast randomized algorithms for RIAFD. In Sect. 3.1 we present an ${\mathcal {O}}^{\star }(3^{\textbf{tw}})$ running time algorithm based on the Cut & Count paradigm. Using this, we give an ${\mathcal {O}}^{\star }(3^k3^\ell )$ time and polynomial space algorithm in Sect. 3.2. In Sect. 3.3, we further improve the dependency on k by using modified techniques from [14] to get an algorithm with running time ${\mathcal {O}}^{\star }(2.85^k8.54^\ell )$ and polynomial space as well as an algorithm with running time ${\mathcal {O}}^{\star }(2.7^k36.61^\ell )$ but exponential space. Finally, in Sect. 3.4, we improve the dependency on $\ell$ by creating a tree decomposition of width $k + \frac{3}{5.769}\ell + {\mathcal {O}}(log(\ell ))$ to get an algorithm with running time ${\mathcal {O}}^{\star }(3^k1.78^\ell )$ (with help of the Cut & Count algorithm presented in Sect. 3.1). Henceforth, the term riafd-set corresponds to a solution for given instance of RIAFD and the term afd-set corresponds to a solution for given instance of AFD.

3.1 $3^{\textbf{tw}}$ Algorithm

We use the Cut & Count technique [11] to solve RIAFD in ${\mathcal {O}}^\star (3^{\textbf{tw}})$ time. First of all, we require the following lemma,

Lemma 3.2

A graph $G = (V, E)$ with n vertices and m edges and a non-negative integer $\ell$ is an $\ell$-forest if and only if it has at most $n-m+\ell$ connected components.

Proof

Forward Direction: By definition of an $\ell$-forest, if we are given an $\ell$-forest with n vertices and m edges, there exists a set S of $\ell$ edges whose removal leaves a forest with n vertices and $m - \ell$ edges. By Lemma 2.1, this remaining forest has at most $n - (m - \ell )$ connected components. Adding back the edges from the set S to the remaining forest cannot result in an increase in the number of connected components. Therefore, the $\ell$-forest also has at most $n - m + \ell$ connected components.

Reverse Direction: We are given a graph $G = (V, E)$ with n vertices, m edges and at most $n - m + \ell$ connected components. Let the r connected components be $C_1, C_2, \ldots C_{r}$ having $n_1, n_2, \ldots n_{r}$ vertices each respectively. The subgraph consisting of only the spanning trees of the connected components is a forest with $\sum \limits _{i =0}^{r} (n_i - 1) = n - r \ge n - (n- m + \ell ) \ge m - \ell$ edges. Let the edge set of the subgraph be $E'$. Therefore, $E \setminus E'$ of cardinality at most $\ell$ is the set of edges to be removed from G to obtain a forest. Therefore, G is an $\ell$-forest. $\square$

Moving on to the Cut & Count Algorithm. Firstly, we define the set $U = V$. We assume that we are given a weight function $\omega : U \rightarrow \{1,\ldots , N\}$, where N is some fixed integer.

The Cut Part: For integers A, B, W we define:

• 1. ${\mathcal {R}}_W^{A, B}$ to be the family of solution candidates: ${\mathcal {R}}_W^{A, B}$ is the family of sets X, where $X \subseteq V$, $|X| = A$, G[X] contains exactly B edges, $(V {\setminus } X) \cap R = \varnothing$, $G[V {\setminus } X]$ is an independent set and $\omega (V \setminus X) = W$;

• 2. $S_W^{A, B}$ to be the set of solutions: the family of sets X, where $X \in {\mathcal {R}}_W^{A, B}$ and G[X] is an $\ell$-forest;

• 3. ${\mathcal {C}}_W^{A, B}$ to be the family of pairs $\big (X, (X_L,X_R)\big )$, where $X \in {\mathcal {R}}_W^{A, B}$ and $(X_L, X_R)$ is a consistent cut¹ of G[X].

Observe that the graph G admits an Restricted Independent Almost Forest Deletion set $F \subseteq V$ of size k if and only if there exist integers B, W such that the set $S_W^{n-k, B}$ is non-empty.

The Count Part: Note that for any non-negative integers A, B, W and set $X \in {\mathcal {R}}_W^{A, B}$, there are $2^{cc(G[X])}$ cuts $(X_L, X_R)$ such that $\big (X, (X_L, X_R)\big ) \in {\mathcal {C}}_W^{A, B}$, where by cc(G[X]) we denote the number of connected components of G[X].

Now we describe a procedure that, given a nice tree decomposition ${\mathbb {T}}$, weight function $\omega$ and integers A, B, W, t, computes $|{\mathcal {C}}_W^{A, B}|$ modulo $2^t$ using dynamic programming.

For every bag $x \in {\mathbb {T}}$, integers $0 \le a \le |V|$, $0 \le b < |V|$, $0 \le w \le \omega (V)$ and $s \in \{{{\textbf {F}}},{{\textbf {L}}}, {{\textbf {R}}}\}^{B_x}$ (called the coloring), define:

$$\begin{aligned} {\mathcal {R}}_x(a,b,w)= & {} \Big \{ X \;\big | \;X\subseteq V_x \wedge |X| = a \wedge |E_x\cap E[X]|=b \wedge \\{} & {} \left( V_x \setminus X\right) \cap R = \varnothing \wedge |E[V_x \setminus X]| = 0 \wedge \; \omega (V_x \setminus X) = W \Big \}\\ {\mathcal {C}}_x(a,b,w)= & {} \Big \{ \big (X, (X_L,X_R)\big )\; \big | \; X \in {\mathcal {R}}_x(a,b,w) \wedge \\{} & {} \big (X, (X_L, X_R)\big ) \text { is a consistently cut subgraph of }G_x \Big \}\\ A_x(a,b,w,s)= & {} \Big |\Big \{ \big (X, (X_L,X_R)\big ) \in {\mathcal {C}}_x(a,b,w) \; \big | \; \\{} & {} \big (s(v) \in \{{{\textbf {L}}},{{\textbf {R}}}\} \implies v \in X_{s(v)} \big ) \wedge \big (s(v)={{\textbf {F}}} \implies v \notin X \big ) \Big \}\Big | \end{aligned}$$

The algorithm computes $A_x(a,b,w,s)$ for all bags $x \in {\mathbb {T}}$ in a bottom-up fashion for all reasonable values of a, b, w and s. We now define the recurrence for $A_x(a,b,w,s)$ that is used by the dynamic programming algorithm. Let v denote the vertex introduced (resp. forgotten) and contained in an introduce (resp. forget) vertex bag, (u, v) the edge introduced in the introduce edge bag, and let y, z stand for the left and right child of $x \in {\mathbb {T}}$. Assume all computations to be modulo $2^t$.

• Leaf bag:

  $$\begin{aligned} A_x(0,0,0,\varnothing )&= 1 \end{aligned}$$

• Introduce vertex bag:

  $$\begin{aligned} A_x(a,b,w,s \cup \{(v,{{\textbf {F}}})\})&= [v \notin R] \; A_y(a,b,w - \omega (v),s) \\ A_x(a,b,w,s \cup \{(v,{{\textbf {L}}})\})&= A_y(a-1, b, w, s)\\ A_x(a,b,w,s \cup \{(v,{{\textbf {R}}})\})&= A_y(a-1, b, w, s) \end{aligned}$$

• Introduce edge bag:

  $$\begin{aligned} A_x(a,b,w,s)&= [Z] \cdot A_y(a,b-[s(u) = s(v) \ne {{\textbf {F}}}], w, s)\\ \text {where } Z&:= (s(u)\ne s(v) \iff (s(u)={{\textbf {F}}} \vee s(v)={{\textbf {F}}})) \end{aligned}$$

• Forget bag:

  $$\begin{aligned} A_x(a,b,c,w,s)&= \sum \limits _{\alpha \in \{{{\textbf {F}}}, {{\textbf {L}}}, {{\textbf {R}}}\}} A_x(a,b,w,s[v\rightarrow \alpha ]) \end{aligned}$$

• Join bag:

  $$\begin{aligned} A_x(a,b,w,s)&= \sum \limits _{{\begin{array}{c} a_1 + a_2 = a + |s^{-1}(\{{{\textbf {L}}},{{\textbf {R}}}\})|\\ b_1 + b_2 = b \\ w_1 + w_2 = w + \omega (s^{-1}(\{{{\textbf {F}}}\})) \end{array}}}A_y(a_1, b_1, w_1, s)\cdot A_z(a_2, b_2, w_2, s) \end{aligned}$$

Let $r \in {\mathbb {T}}$ be the root bag. Therefore, $A_r(A,B,W,\varnothing ) \equiv |{\mathcal {C}}_W^{A, B}| \ (\text {mod} \ 2^t)$ which is our required answer.

Lemma 3.3

Let $G=(V,E)$ be a graph and d be an integer. Pick $\omega '(v)$ $\in$ $\{1,$ $\ldots ,$ $2 |V|\}$ uniformly and independent at random for every $v \in V$, and define $\omega (v):= |V|^2\omega '(v) + deg(v)$ and $n = |V|$. The following statements hold:

• 1. If for some integers $m'$, $W = i|V|^2 + d$, we have that $|{\mathcal {C}}_W^{n-k,m'}| \not \equiv 0\ (\text {mod}$ $2^{n-k-m'+l + 1})$, then G has a riafd-set F of size k satisfying $deg(F) = d$.

• 2. If G has a riafd-set F of size k satisfying $deg(F) = d$, then with probability at least 1/2 for some $m'$, $W = i|V|^2 + d$, we have that $|{\mathcal {C}}_W^{n-k,m'}| \not \equiv 0\ (\text {mod} \ 2^{n-k-m'+\ell + 1})$.

Proof

This proof is similar to the one for fvs in [14].

Item 1: Note that if $|{\mathcal {C}}_W^{n-k,m'}| \not \equiv 0\ (\text {mod} \ 2^{n-k-m'+\ell + 1})$, then there must be some vertex subset F of size k such that $F \cap R = \varnothing$, G[F] is an independent set and the number of choices of $X_L$, $X_R$ with $(V {\setminus } F, (X_L, X_R)) \in {\mathcal {C}}_W^{n-k,m'}$ is not a multiple of $2^{n-k-m'+\ell + 1}$. Due to independency in choice of cuts for connected components of $G[V \setminus F]$ on whether to put it in $X_L$ or $X_R$, $G[V {\setminus } F]$ must have at most $n-k-m'+\ell$ connected components. Therefore, by Lemma 3.2, $G[V \setminus F]$ must be an $\ell$-forest, making F a riafd-set of size k. The condition on degree follows from the weighting.

Item 2: First apply Lemma 2.3 with $U = V$ and the set family ${\mathcal {F}}$ being the set of all riafd-set F satisfying $deg(F) = d$ with weighting done based on $\omega '$. With probability 1/2, there will be some weight i such that there is a unique riafd-set F with $deg(F) = d$ and weight i. Therefore, for the weight function $\omega$, we have $W = \omega (F) = i|V|^2 + d$. Since $\omega '$ isolated F out of ${\mathcal {F}}$ and $d < |V|^2$ (for $k >0$), this is the only F which has a contribution in ${\mathcal {C}}_W^{n-k,m'}$ that is not a multiple of $2^{n-k-m'+\ell + 1}$ as it has $2^{cc(G[V {\setminus } F])} \le 2^{n-k-m'+\ell }$ valid cuts. $\square$

While it is clear from the DP and Lemma 3.3 that we can get ${\mathcal {O}}^\star \left( 3^{\textbf{tw}}\right)$ running time, we will provide the details of a slightly more generalized algorithm which is able to utilize additional structure in the tree decomposition and improves the space bound.

3.2 $3^{k+\ell }$ Algorithm in Polynomial Space

The above Cut & Count algorithm utilizes exponential space. Notice that in all the problems discussed in this paper, the tree decomposition that we have always has a large set which is present in all bags of the tree decomposition. We will exploit this structure to obtain a polynomial space algorithm.

Definition 3.4

Given a set $S \subseteq V$ and a function $f: S \rightarrow \left\{ {{\textbf {F}}},{{\textbf {L}}},{{\textbf {R}}}\right\}$, we define the quantity ${\mathcal {C}}_{W,f}^{A, B}$ as follows:

$$\begin{aligned} {\mathcal {C}}_{W,f}^{A, B}= & {} \Big \{\big (X, (X_L,X_R)\big )\, \Big |\, X \in {\mathcal {R}}_W^{A, B} \wedge (X_L, X_R) \text { is a consistent cut of } G\big [X\big ] \wedge \\{} & {} \big (\forall v \in S, v \text { agrees with } f\big ) \Big \}. \end{aligned}$$

where “v agrees with f” means that $v \in V \setminus X$ if $f(v) = {{\textbf {F}}}$, $v \in X_L$ if $f(v) = {{\textbf {L}}}$ and $v \in X_R$ if $f(v) = {{\textbf {R}}}$.

Claim 3.5

Given a tree decomposition ${\mathbb {T}}$ with a set $S\subseteq V$ which is present in all its bags, a fixed integer t and a function $f: S \rightarrow \left\{ {{\textbf {F}}},{{\textbf {L}}},{{\textbf {R}}}\right\}$, there is a routine RIAFD-FCCount(${\mathbb {T}},R,A,B,W,f,t$) which can compute $|{\mathcal {C}}_{W,f}^{A, B}| \;(\text {mod} \; 2^t)$ in time ${\mathcal {O}}^\star \left( 3^{\textbf{tw}- |S|}\right)$.

Proof

We will give a brief description of the routine RIAFD-FCCount as that will suffice to prove this claim. In every entry of the DP table described for $|{\mathcal {C}}_W^{A, B}|$, just compute all values of $A_x(a,b,w,s)$, where $s|_{B_x \cap S} = f|_{B_x \cap S}$ and ignore all computations that do not agree to this condition. This means per bag, only ${\mathcal {O}}^\star (3^{\textbf{tw}- |S|})$ computations are required (since in all bags at most $\textbf{tw}+1 - |S|$ values of s are not “fixed” by f). The required answer is in the root bag r as the entry $A_r(A,B,W,\varnothing ) \equiv |{\mathcal {C}}_{W,f}^{A, B}| \ (\text {mod} \ 2^t)$. $\square$

Now, given a tree decomposition ${\mathbb {T}}$ with a set $S\subseteq V$ which is present in all its bags, we can see that,

$$\begin{aligned} |C_W^{A,B}| = \sum \limits _{\text {All possible } f: S \rightarrow \left\{ {{\textbf {F}}},{{\textbf {L}}},{{\textbf {R}}}\right\} } |{\mathcal {C}}_{W,f}^{A, B}|. \end{aligned}$$

Now, we define a procedure $\texttt{RIAFDCutandCount}$ which given a tree decomposition ${\mathbb {T}}$, a set $S\subseteq V$ present in all bags of ${\mathbb {T}}$ uses the above fact to improve the space bound from ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}}\right)$ to ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$.

Algorithm 1

$\texttt{RIAFDCutandCount}(\mathbb {T},R,k,\ell ,S)$

Theorem 3.6

Given a tree decomposition ${\mathbb {T}}$, a set $S\subseteq V$ present in all bags of ${\mathbb {T}}$, a set R and parameters k and $\ell$, $\texttt{RIAFDCutandCount}$ solves RIAFD in ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}}\right)$ time and ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$ space with high probability.

Proof

We first prove the probability bound. By Lemma 3.3 Item (2) if a riafd-set of size at most k exists, then for some values satisfying $n-k \le A \le |V|$, $0 \le B \le A +\ell +1$ and $0 \le W \le 2|V|^4 + 2|E|$, in each iteration of the for block starting at Line 3, count $\not \equiv 0 \ (\text {mod}\ 2^t)$ with probability 1/2. Lemma 3.3 Item (1) makes it so that whenever we have count $\not \equiv 0 \ (\text {mod}\ 2^t)$, there is guaranteed to be a riafd-set, i.e., there are no false positives. Therefore, in $n^{\mathcal {O}(1)}$ iterations, we obtain the required riafd-set, if it exist, with high probability and if such a set doesn’t exist, $\texttt{RIAFDCutandCount}$ will always return Infeasible.

Now, to prove the time and space complexity bounds, we first take note of the fact that by Claim 3.5, Line 7 takes ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$ time and ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$ space. Since the number of possible $f: S \rightarrow \left\{ {{\textbf {F}}},{{\textbf {L}}},{{\textbf {R}}}\right\}$ is $3^{|S|}$, Line 6 runs for ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}}\right)$ time but since each run is independent it still requires only ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$ space. All other lines contribute at most polynomial cost overall to the total running time and space. Therefore, the time and space bounds for Line 6 are the ones for the complete algorithm. $\square$

Lemma 3.7

Given a graph $G=(V,E)$ and a riafd-set F of size k one can construct a tree-decomposition ${\mathbb {T}}$ which contains a set $S \supseteq F$ of size at most $k+\ell$ in all bags and has width at most $|S|+1$ in polynomial time.

Proof

Initially the set $S = F$. $G[V \setminus F]$ is an $\ell$-forest. Now, find any spanning tree of each connected component. We can see that the union of the spanning trees is the forest with maximum number of edges that spans $G[V \setminus F]$. Therefore, there can be at most $\ell$ edges that were left out from the forest since $G[V \setminus F]$ is an $\ell$-forest. Add one end-point from each of these leftover edges to the set S. This set S is now an fvs of G of size at most $k+\ell$. Therefore, we can construct a tree decomposition ${\mathbb {T}}$ of width 1 of the forest $G[V {\setminus } S]$. Add the set S to all bags of ${\mathbb {T}}$. Therefore, width of ${\mathbb {T}}$ is now at most $|S| + 1$. This completes our construction. It’s easy to see from the description of the construction procedure that it takes polynomial time. $\square$

Algorithm 2

$\texttt{RIAFD3k3l}(G,R,k,\ell )$

Now, we prove the following theorem, which is a restatement of Theorem 1.2 (1). Also, note that we set $R=\varnothing$ in all the cases except for when there is an explicit requirement of a restricted set of vertices.

Theorem 3.8

(Restatement of Theorem 1.2 (1))

The randomized algorithm $\texttt{RIAFD3k3l}$ solves Almost Forest Deletion in ${\mathcal {O}}^{\star }\left( 3^{k}3^{\ell }\right)$ time and polynomial space with high probability.

Proof

Suppose that there exists a riafd-set $F^\star$ of size at most k. Let $\left( v_1, \ldots , v_i\right)$ be the ordering from Line 1, and define $V_i:= \left\{ v_1, \ldots , v_i\right\}$. Observe that $F^\star \cap V_i$ is a riafd-set of $G[V_i]$, so RIAFD problem on Line 7 is feasible. Line 7 correctly computes a riafd-set with high probability on any given iteration. Therefore, with high probability, such a riafd-set for G is returned by a union bound.

We now bound the running time and space complexity. On Line 4, the current set F is a riafd-set of $G[V_{i-1}]$, so Lemma 3.7 guarantees a tree decomposition ${\mathbb {T}}$ of width at most $k+\ell +1$, and adding $v_i$ to each bag on Line 6 increases the width by at most 1. Also Lemma 3.7 guarantees a set S with $|S| \le k+\ell$ such that $\textbf{tw}({\mathbb {T}}) - |S| \le 1$ and adding $v_i$ to the set S increases its size by 1. Therefore, by Theorem 3.6, Line 7 runs in time ${\mathcal {O}}^\star (3^{k+\ell })$ and space ${\mathcal {O}}^\star (1)$ as desired. $\square$

3.3 Improving the Dependency on k

In this subsection, we try to reduce the dependency on k by allowing an increase in dependency on $\ell$. We use the method of [14] using the outline described in Sect. 2. Following are some trivial reduction rules for RIAFD:

Definition 3.9

(Reduction 1) Apply the following rules exhaustively, until the remaining graph has minimum vertex degree at least 2:

• 1. Delete all vertices of degree at most one in the input graph.

• 2. If $k<0$, then we have a no instance. If $k > 0$ and G is an $\ell$-forest, we have a yes instance. If $k=0$, we have a yes instance iff G is an $\ell$-forest.

3.3.1 Dense Case

Now we give a probabilistic reduction for RIAFD that capitalizes on the fact that a large number of edges are incident to the riafd-set. In particular, for a yes instance we focus on obtaining a probabilistic reduction that succeeds with probability strictly greater than 1/3 so as to achieve a randomized algorithm running in time ${\mathcal {O}}^{\star }\left( (3-\epsilon )^{k}\right)$ with high probability.

Definition 3.10

(Reduction 2 (P)) Assume that Reduction 1 does not apply and G has a vertex of degree at least 3. Sample a vertex $v \in V$ proportional to $\omega (v):= (deg(v)-2)$ if $v \notin R$, else $\omega (v):= 0$. That is, select each vertex with probability $\frac{\omega (v)}{\omega (V)}$. Delete v and add its neighbours to R. Decrease k by 1.

Claim 3.11

Let G be a graph, F an afd-set of G. Denote ${\overline{F}}:= V \setminus F$. We have that,

$$\begin{aligned} deg({\overline{F}}) \le deg(F) + 2(|{\overline{F}}|-1+\ell ) \end{aligned}$$

Proof

This proof is based on simple observations. Notice that $deg({\overline{F}}) = 2|E[{\overline{F}}]|+ |E[{\overline{F}},F]|$. As $G[{\overline{F}}]$ is an $\ell$-forest, $|E[{\overline{F}}]| \le |{\overline{F}}|-1+\ell$. Also, $|E[{\overline{F}},F]|\le deg(F)$. Therefore,

$$\begin{aligned} deg({\overline{F}})\le 2(|{\overline{F}}|-1+\ell )+deg(F) \end{aligned}$$

$\square$

Lemma 3.12

Given a graph G, if there exists a riafd-set F of size k such that $deg(F) \ge \frac{4-2\epsilon }{1-\epsilon }(k+\ell )$, then success of Reduction 2, which is the event of sampling a vertex $v\in F$, occurs with probability at least $\frac{1}{3-\epsilon }$.

Proof

Let $F \subseteq V$ is a riafd-set of G of size exactly k. For Reduction 2 to succeed with probability at least $\frac{1}{3-\epsilon }$, we need $\frac{\omega (F)}{\omega ({\overline{F}})} \ge \frac{1}{2-\epsilon }$.

The value of $\omega (F)$ can be rewritten as,

$$\begin{aligned} \omega (F) = \sum _{v \in F} (deg(v) - 2) = deg(F)-2k. \end{aligned}$$

By Claim 3.11 (as riafd-set is also an afd-set),

$$\begin{aligned} \omega ({\overline{F}})\le & {} \sum _{v \in {\overline{F}}}(deg(v)-2) = deg({\overline{F}}) - 2|{\overline{F}}|\\{} & {} \le deg(F) + 2(|{\overline{F}}|- 1 + \ell ) - 2|{\overline{F}}| \le deg(F) + 2\ell . \end{aligned}$$

Therefore,

$$\begin{aligned} \frac{\omega (F)}{\omega ({\overline{F}})} \ge \frac{deg(F)-2k}{deg(F)+2\ell } = 1 - \frac{2(k+\ell )}{deg(F)+2\ell } \mathop {{\ge }}\limits ^{(\ell \ge 0)} 1 - \frac{2(k+\ell )}{deg(F)}. \end{aligned}$$

Hence, we need

$$\begin{aligned} 1-\frac{2(k+\ell )}{deg(F)} \ge \frac{1}{2-\epsilon } \iff deg(F) \ge \frac{4-2\epsilon }{1-\epsilon }(k+\ell ). \end{aligned}$$

$\square$

3.3.2 Sparse Case

For the sparse case, we first construct a small separator. Due to the presence of two variables (k and $\ell$), we have to modify the small separator lemma in [14, Lemma 3.2] with a bivariate analysis. Also, though we are discussing RIAFD, we will show how to construct a small separator assuming that we are given an afd-set, as a riafd-set is also an afd-set.

Small Separator

The main idea, as presented in [14], is to convert an afd-set with small average degree into a good tree decomposition. In particular, suppose a graph G has an afd-set F of size k with $deg(F) \le {\overline{d}}(k+\ell )$, where ${\overline{d}} = {\mathcal {O}}(1)$. We show how to construct a tree decomposition of width $(1 - \Omega (1))k + (2 - \Omega (1))\ell$. Note that ${\overline{d}}$ is not exactly the average degree of F. This definition helps us to bound the width of the tree decomposition well.

Before constructing this separator, we will first see a construction of a $\beta$-separator of an $\ell$-forest. We could use Lemma 2.7, but the size of the separator obtained would be $\ell \cdot o(k)$ which is huge (treewidth $\le \ell$). We now give a method to construct a $\beta$-separator of size $\ell + o(k)$.

Lemma 3.13

Given an $\ell$-forest T(V, E) on n vertices with vertex weights $\omega (v)$, for any $\beta > 0$, we can delete a set S of $\beta + \ell$ vertices in polynomial time so that every connected component of $T - S$ has total weight at most $\frac{\omega (V)}{\beta }$.

Proof

Construct some spanning tree for each connected component of T, call this resultant forest $T'$. Let X be the set of remaining edges which are not in $T'$. For each edge in X, delete one vertex from $T'$. As $|X| \le \ell$, we will delete at most $\ell$ vertices. The resultant will still be a forest, call it $T''$.

Using [14, Lemma 3.1], there exists a set $S'$ with $|S'|=\beta$ in $T''$ such that every connected component of $T'' - S$ has total weight at most $\frac{\omega (V)}{\beta }$. Thus, we delete at most $\beta + \ell$ vertices overall. We present the proof of the aforementioned lemma for the sake of completeness.

Root every component of the forest $T''$ at an arbitrary vertex. Iteratively select a vertex v of maximal depth whose subtree has total weight more than $\frac{\omega (V)}{\beta }$, and then remove v and its subtree. The subtrees rooted at the children of v have total weight at most $\frac{\omega (V)}{\beta }$, since otherwise, v would not satisfy the maximal depth condition. Moreover, by removing the subtree rooted at v, we remove at least $\frac{\omega (V)}{\beta }$ total weight, and this can only happen $\beta$ times. $\square$

With the help of Lemma 3.13, we will now proceed to the small separator lemma.

Lemma 3.14

(Small Separator) Given an instance $(G, k, \ell )$ and an afd-set F of G of size k, define ${\overline{d}}:= \frac{deg(F)}{k+\ell }$, and suppose that ${\overline{d}} = {\mathcal {O}}(1)$. There is a randomized algorithm running in expected polynomial time that computes a separation (A, B, S) of G such that:

• 1. $|A \cap F|, |B \cap F| \ge (2^{-{\overline{d}}}-o(1))(k+\ell ) - \ell$

• 2. $|S| \le (1 + o(1))(k+\ell ) - |A \cap F| - |B \cap F|$

Proof

The proof will be similar to [14] (Lemma 4). First, we fix a parameter $\epsilon := (k+\ell )^{-0.01}$ throughout the proof. Apply Lemma 3.13 to the $\ell$-forest $G - F$ with $\beta = \epsilon (k+\ell )$ and every vertex $v \in V {\setminus } F$ weighted by |E[v, F]|. Let $S_{\epsilon }$ be the output. Observe that:

$$\begin{aligned} |S_{\epsilon }| \le \ell +\epsilon (k+\ell ) = \ell + o(k+\ell ), \end{aligned}$$

and every connected component C of $G - F - S_{\epsilon }$ satisfies,

$$\begin{aligned} |E[C, F]| \le \frac{|E[{\overline{F}},F]|}{\epsilon (k+\ell )} \le \frac{deg(F)}{\epsilon (k+\ell )} \le \frac{{\overline{d}}(k+\ell )}{\epsilon (k+\ell )} = \frac{{\overline{d}}}{\epsilon } \end{aligned}$$

Now form a bipartite graph H, as in [14], i.e., on the vertex bipartition $F \uplus {\mathcal {R}}$, where F is the afd-set, and there are two types of vertices in ${\mathcal {R}}$, the component vertices and the subdivision vertices. For every connected component C in $G - F - S_{\epsilon }$, there is a component vertex $v_C$ in ${\mathcal {R}}$ that represents that component, and it is connected to all vertices in F adjacent to at least one vertex in C. For every edge $e = (u, v)$ in E[F], there is a vertex $v_e$ in ${\mathcal {R}}$ with u and v as its neighbours. Observe that:

• $|{\mathcal {R}}| \le |E[{\overline{F}}, F]| + 2|E[F]| = deg(F)$.

• every component vertex in ${\mathcal {R}}$ has degree at most $\frac{{\overline{d}}}{\epsilon }$.

• the degree of a vertex $v \in F$ in H is at most deg(v).

The algorithm that finds a separator (A, B, S) works as follows. For each vertex in ${\mathcal {R}}$, color it red or blue uniformly and independently at random. Every component C in $G - F - S_{\epsilon }$ whose vertex $v_C$ is colored red is added to A in the separation (A, B, S), and every component whose vertex $v_C$ is colored blue is added to B. Every vertex in F whose neighbors are all colored red joins A, and every vertex in F whose neighbors are all colored blue joins B. The remaining vertices in F, along with the vertices in $S_{\epsilon }$, comprise S. It is easy to see that (A, B, S) is a separation.

Claim 3.15

(A, B, S) is a separation.

We now show with good probability both conditions (1) and (2) hold. The algorithm can then repeat the process until both conditions hold.

Claim 3.16

With probability at least $1-\frac{1}{k^{{\mathcal {O}}(1)}}$ condition (1) holds for (A, B, S).

Proof

Firstly, notice that F has at most $\epsilon (k+\ell )$ vertices with degree at least $\frac{{\overline{d}}}{\epsilon }$. These can be ignored as they affect condition (1) only by an additive $\epsilon (k+\ell ) = o(k+\ell )$ factor. Let $F'$ be the vertices with degree at most $\frac{{\overline{d}}}{\epsilon }$. Now, consider the intersection graph I on vertices of $F'$ formed by connecting two vertices if they share a common neighbour (in ${\mathcal {R}}$). Since every vertex in $F'$ and all the component vertices have degree at most $\frac{{\overline{d}}}{\epsilon }$, the maximum degree of I is at most $\left( \frac{{\overline{d}}}{\epsilon }\right) ^2$. Color the vertices of $F'$ with $\left( \frac{{\overline{d}}}{\epsilon }\right) ^2+1$ colors such that the vertices of the same color class form an independent set in I, using the standard greedy algorithm. Note that, within each color class, the outcome of each vertex whether it joins A, B or S is independent across vertices.

Let $F'_i$ be the set of vertices colored i. If $|F'_i| \le k^{0.9}$, then this color class can be ignored since the sum of all such $|F'_i|$ is at most $\left( \left( \frac{{\overline{d}}}{\epsilon }\right) ^2+1\right) k^{0.9} = o(k)$ and this affects condition (1) by an additive o(k) factor. Henceforth, assume $|F'_i| \ge k^{0.9}$. Each vertex $v \in F'_i$ has at most deg(v) neighbours in H. So, it can join A with an independent probability of at least $2^{-deg(v)}$. Let $X_i = |F'_i \cap A|$, then by Hoeffding’s inequality,²

$$\begin{aligned} \Pr [X_i \le E[X_i] - k^{0.8}]\le 2\cdot exp\left( -2\cdot \frac{\left( k^{0.8}\right) ^2}{|F'_i|}\right) \le 2\cdot exp\left( -2\cdot \frac{k^{1.6}}{k}\right) \le \frac{1}{k^{{\mathcal {O}}(1)}} \end{aligned}$$

for large enough k.

By a union bound over all the $\le k^{0.1}$ such color classes with $|F'_i| \ge k^{0.9}$, the probability that $|F'_i \cap A| \ge E[|F'_i \cap A|] - k^{0.8}$ for each $F'_i$ is at least $1 - \frac{1}{k^{{\mathcal {O}}(1)}}$. In this case,

$$\begin{aligned} |F \cap A|\ge & {} \sum \limits _{i:|F'_i|\ge k^{0.9}} \left( E[|F'_i \cap A|] - k^{0.8}\right) \\\ge & {} \sum \limits _{i:|F'_i|\ge k^{0.9}} \sum \limits _{v\in F'_i} \left( 2^{-deg(v)}\right) - k^{0.1}\cdot k^{0.8}\\= & {} \sum \limits _{v \in F'} 2^{-deg(v)} + \sum \limits _{j = 1}^{\ell } 2^{0} - \ell - o(k)\\\ge & {} \left( |F'|+\ell \right) \cdot 2^{-\frac{deg(F')}{|F'|+\ell }} - \ell - o(k), \end{aligned}$$

where the last inequality follows from convexity of the function $2^{-x}$. Recall that $|F'| \ge k - o(k+\ell )$, and observe that $\frac{deg(F')}{|F'|+\ell } \le \frac{deg(F)}{k+\ell } = {\overline{d}}$ since the vertices in $F {\setminus } F'$ are vertices with degree greater than some threshold. Thus,

$$\begin{aligned} |F \cap A| \ge \left( k+\ell - o(k+\ell )\right) \cdot 2^{-{\overline{d}}} - l - o(k) \ge \left( 2^{-{\overline{d}}} - o(1)\right) (k+\ell ) - \ell , \end{aligned}$$

proving condition (1) for A. The argument for $|B \cap F|$ is analogous. $\square$

Claim 3.17

With probability at least $1-\frac{1}{k^{{\mathcal {O}}(1)}}$ condition (2) holds for (A, B, S).

Proof

Note that at most $\ell + o(k+l)$ vertices in S are from $S_{\epsilon }$, and the other vertices in S are from the set $F {\setminus } ((F\cap A) \cup (F \cap B))$ which has size $k - |A \cap F|-|B \cap F|$. Thus, $|S| \le \left( 1+o(1)\right) (k+\ell )-|A\cap F|-|B\cap F|$ $\square$

$\square$

Lemma 3.18

Let G be a graph and F be a afd-set of G of size k, and define ${\overline{d}}:= \frac{deg(F)}{k+\ell }$. There is a randomized algorithm that, given G and F, computes a tree decomposition of G of width at most $(1-2^{-{\overline{d}}}+o(1))k + (2-2^{-{\overline{d}}}+o(1))\ell$, and runs in polynomial time in expectation.

Proof

Compute a separation (A, B, S) following Lemma 3.14. Notice that $G[A \cup S] - (F \cup S)$ is a forest, as $S_{\epsilon }$ (from proof of Lemma 3.14) includes the $\ell$ vertices corresponding to the $\ell$ extra edges of the $\ell$-forest $G-F$. Thus, $(A \cap F) \cup S$ is a fvs of $A \cup S$. The size of this fvs is,

$$\begin{aligned} |(A \cap F) \cup S|&= |A \cap F|+ |S|\\&\le (1+o(1))(k+\ell ) - |B \cap F| \\&\le (1 - 2^{-{\overline{d}}}+o(1))k + (2 - 2^{-{\overline{d}}}+o(1))\ell . \end{aligned}$$

Therefore, we can compute a tree decomposition of $G[A \cup S]$ of width $(1 - 2^{-{\overline{d}}}+o(1))k + (2 - 2^{-{\overline{d}}}+o(1))\ell$ as follows: start with a tree decomposition of width 1 of the forest $G[A\cup S] - (F \cup S)$, and then add all vertices in $(A \cap F) \cup S$ to each bag. Call this tree decomposition of $G[A \cup S]$ as ${\mathbb {T}}_1$. Similarly, compute a tree decomposition of $G[B\cup S]$ in the same way, call it ${\mathbb {T}}_2$.

Since there is no edge connecting A and B, and S is present in all bags of ${\mathbb {T}}_1$ and ${\mathbb {T}}_2$, we can construct the tree decomposition ${\mathbb {T}}$ of G by simply adding an edge between an arbitrary node from ${\mathbb {T}}_1$ and ${\mathbb {T}}_2$. Thus, it is evident from the construction procedure that ${\mathbb {T}}$ is a valid tree decomposition of G and it takes polynomial time to compute it. $\square$

Note 3.19

Using the tree decomposition obtained in Lemma 3.18, we can run the Cut & Count algorithm from Sect. 3.1. But this will utilize exponential space. To get polynomial space, we use the idea from Claim 3.5. In the proof of Lemma 3.18, observe that the set $(A \cap F) \cup S$ is present in every bag of ${\mathbb {T}}_1$. Similarly, $(B\cap F) \cup S$ is present in every bag of ${\mathbb {T}}_2$. This observation is crucial for the proof of Lemma 3.20.

As we are in the sparse case, there exists a riafd-set F of size k with bounded degree, i.e., $deg(F) \le {\overline{d}}k$. We call this bounded version of the problem BRIAFD. As we saw, the small separator helps in constructing a tree decomposition of small width, but requires that we are given an afd-set of size k and bounded degree. To attain this, we use an Iterative Compression based procedure which at every iteration constructs a riafd-set of size at most k with bounded degree and uses it to construct the small separator. Using this small separator we construct a tree decomposition of small width and run a Cut & Count based procedure to solve bounded RIAFD problem for the current induced subgraph, i.e, get a riafd-set of size at most k with bounded degree.

Now, we give the claimed BRIAFD1 algorithm, which is a Cut & Count based algorithm which solves BRIAFD given a small separator.

Algorithm 3

BRIAFD1$(G,R,k,\ell ,F,A,B,S,\overline{d})$

Lemma 3.20

Given a graph G, a set R, an afd-set F of G of size at most $k+1$, parameter ${\overline{d}}$, and a separation (A, B, S) as given by Lemma 3.14, the Algorithm BRIAFD1 outputs an riafd-set $F^{\star }$ of size at most k satisfying $deg(F^{\star }) \le {\overline{d}}(|F^{\star }|+\ell )$, or Infeasible if none exists. The algorithm uses ${\mathcal {O}}^{\star }(3^{(1-2^{-{\overline{d}}}+o(1))k}\cdot 3^{(2-2^{-{\overline{d}}}+o(1))\ell })$ time and polynomial space and succeeds with high probability.

Proof

For the time bound, firstly notice that Lines 11 and 15 take polynomial time due to the observation given in Note 3.19 and Claim 3.5. All other steps listed in the algorithm BRIAFD1 are polynomial time except lines 7, 10 and 14, which jointly give rise to $3^{|S|+|A \cap F|} + 3^{|S|+|B \cap F|}$ iterations. By the conditions (1) and (2) of the separator (A, B, S) in Lemma 3.14, we get the desired time bound. The space bound is evident from the description of the algorithm BRIAFD1 and Claim 3.5. Also, by Line 3 and Lemma 2.4, the algorithm succeeds with high probability.

For the correctness, first we claim that at Line 15, count $= |{\mathcal {C}}_W^{n-k,B}|$ for some A, B and $W = i\cdot n^2 + d$ (from Lemma 3.3). To see the claim, observe that we are iterating over all possible mappings of S. For each mapping and every possible split of the parameters W and B, the algorithm computes the number countA (resp. countB) denoting the “extensions” of the mapping in $G[A \cup S]$ (resp. $G[B \cup S]$) that respect the split, and then multiplies countA and countB. To see why these counts are multiplied, notice that there are no edges between A and B. So, extending into $G[A \cup S]$ is independent to extending into $G[B \cup S]$. This along with the correctness of RIAFD-FCCount proves the claim, thereby proving the correctness. $\square$

And now we give the Iterative Compression routine RIAFD_IC1, as explained above, which solves BRIAFD.

Algorithm 4

$\mathtt {RIAFD\_IC1}(G,R,k,\ell ,\overline{d})$

Lemma 3.21

Algorithm $\mathtt {RIAFD\_IC1}$ solves BRIAFD in time ${\mathcal {O}}^{\star }(3^{(1 - 2^{-{\overline{d}}}+o(1))k}$ $\cdot$ $3^{(2 - 2^{-{\overline{d}}}+o(1))\ell })$ with high probability and polynomial space.

Proof

Suppose there exists a riafd-set F of size k satisfying $deg(F) \le {\overline{d}}(k+\ell )$. Let $\left( v_1, \ldots , v_i\right)$ be the ordering from Line 1, and define $V_i:= \left\{ v_1, \ldots , v_i\right\}$. Observe that $F \cap V_i$ is a riafd-set of $G[V_i]$ of size at most k. Let $F_i = F \cap V_i$ and $|F_i| = k_i \le k$. Due to the ordering from Line 1, $F_i$ are the vertices of least degrees in F. Thus, $\frac{deg(F_i)}{k_i+\ell } \le \frac{deg(F)}{k+l} \le {\overline{d}}$. Hence, BRIAFD problem on Line 7 is feasible.

Line 7 correctly computes a bounded degree riafd-set of size at most k with high probability, by Lemma 3.20. Therefore, with high probability, a riafd-set of size k is returned.

We now bound the running time. On Line 5, the current set $F^\star$ is a riafd-set of $G[V_{i-1}]$ satisfying $deg(F^\star ) \le {\overline{d}}(|F^\star |+\ell )$, so Lemma 3.18 guarantees tree decompositions ${\mathbb {T}}_1$ and ${\mathbb {T}}_2$ of width at most $(1 - 2^{-{\overline{d}}} + o(1))k + (2 - 2^{-{\overline{d}}} + o(1))\ell$, and adding $v_i$ to each bag on Line 6 increases the width by at most 1. By Lemma 3.20, Line 7 runs in time ${\mathcal {O}}^{\star }\left( 3^{(1-2^{-{\overline{d}}}+o(1))k}\cdot 3^{(2-2^{-{\overline{d}}}+o(1))\ell }\right)$, as desired. The space bound is evident from the description of RIAFD_IC1 and Lemma 3.20. $\square$

Three-Way Separator Similar to small separator, a bivariate analysis has to be done in the case of the three-way separator too. The outline of the analysis is similar to Lemma 3.14.

Lemma 3.22

(Three-Way Separator). Given an instance (G, k) and an afd-set F of size k, define ${\overline{d}}:= \frac{deg(F)}{k+\ell }$, and suppose that ${\overline{d}} = {\mathcal {O}}(1)$. There is a randomized algorithm running in expected polynomial time that computes a three-way separation $(S_1, S_2, S_3, S_{1,2}, S_{1,3}, S_{2,3}, S_{1,2,3})$ of G such that there exists values $f_1, f_2$ satisfying:

• 1. $f_1 k \ge (3^{-{\overline{d}}}-o(1))(k+\ell )-\ell$

• 2. $f_1 k - o(k+\ell ) \le |S_i \cap F| \le f_1 k + o(k+\ell )$ for all $i \in [3]$

• 3. $(f_2 + 2f_1)k \ge \big ((\frac{2}{3})^{{\overline{d}}} - o(1)\big )(k+\ell ) - \ell$

• 4. $f_2 k - o(k+\ell ) \le |S_{i,j}| \le f_2 k + o(k+\ell )$ for all $1 \le i < j \le 3$

Proof

This proof is similar to [14](Lemma 14) and uses the idea from Lemma 3.14. Indeed, the same choice of values for $f_1$ and $f_2$ considered by [14] works. Firstly, we start out the same: fix $\epsilon := (k+\ell )^{-0.01}$, apply Lemma 3.13 on $G - F$ (to construct $S_\epsilon$), and construct the bipartite graph H on the bipartition $F \uplus {\mathcal {R}}$ in the same way as in Lemma 3.14. Recall that,

• $|{\mathcal {R}}| \le |E[{\overline{F}}, F]| + 2|E[F]| = deg(F)$.

• every component vertex in ${\mathcal {R}}$ has degree at most $\frac{{\overline{d}}}{\epsilon }$.

• the degree of a vertex $v \in F$ in H is at most deg(v).

Now, instead of randomly two-coloring the vertex set ${\mathcal {R}}$, the algorithm three-colors it. That is, for each vertex in ${\mathcal {R}}$, color it with a color in $\{1, 2, 3\}$ chosen uniformly and independently at random. For each subset $I \subseteq 2^{[3]}{\setminus } \{\varnothing \}$, create a vertex set $S_I$ consisting of all vertices $v \in F$ whose neighborhood in H sees the color set I precisely. More formally, let c(v) and N(v) be the color of $v \in {\mathcal {R}}$ and the neighbors of v in H, and define $S_I = \{v \in F: \bigcup _{u\in N(v)} c(u) = I\}$. Furthermore, if I is a singleton set $\{i\}$, then add (to $S_I$) all vertices in the connected components C whose component vertex in ${\mathcal {R}}$ is colored i. We also add $S_{\epsilon }$ to $S_{\{1,2,3\}}$. Henceforth, we abuse notation, referring to sets $S_{\{1\}}, S_{\{1,2\}},$ etc. as $S_1, S_{1,2},$ etc. Let $F'$ denote the set of vertices in F whose degree are at most ${\overline{d}}/\epsilon$, same as before. For each $d \le {\overline{d}}/\epsilon$, let $F_d'$ denote the set of degree d vertices in $F'$. Further, let $p_{1,d}$ be the probability that a vertex of degree d joins $S_1$, WLOG (since we will have the same values for $S_2$ and $S_3$). Also, let $p_{2,d}$ be the probability that a vertex of degree d joins $S_{1,2}$, WLOG. Observe that $p_{1,d}=3^{-d}$.

Claim 3.23

$(S_1, S_2, S_3, S_{1,2}, S_{1,3}, S_{2,3}, S_{1,2,3})$ is a three-way separator.

Claim 3.24

For $f_1:= \frac{\sum \limits _{d=1}^{{\overline{d}}/\epsilon } p_{1,d} |F'_d|}{|F'|}$, condition (2) holds with probability at least $1 - \frac{1}{k^{{\mathcal {O}}(1)}}$.

Claim 3.25

For $f_2:= \frac{\sum \limits _{d=1}^{{\overline{d}}/\epsilon } p_{2,d} |F'_d|}{|F'|}$, condition (4) holds with probability at least $1 - \frac{1}{k^{{\mathcal {O}}(1)}}$.

The proofs of Claim 3.23, Claim 3.24 and Claim 3.25 are very similar to the proofs in [14] and the proof of Lemma 3.14. Hence, they are omitted.

Claim 3.26

For the value of $f_1$ defined in Claim 3.24, condition (1) holds with probability at least $1 - \frac{1}{k^{{\mathcal {O}}(1)}}$

Proof

Observe that $\frac{deg(F')}{|F'|+\ell } \le \frac{deg(F)}{k+\ell } = {\overline{d}}$, since the vertices in $F{\setminus } F'$ are precisely vertices with degree exceeding some threshold, and $|F'| \ge k - o(k+\ell )$. Also, due to the convexity of the function $3^{-x}$, we get

$$\begin{aligned} f_1k \ge f_1|F'|= & {} \sum \limits _{d} |F'_d|\cdot p_{1,d}\\= & {} \sum \limits _{d} |F'_d|\cdot 3^{-d}\\= & {} \sum \limits _{v \in F'} 3^{-deg(v)} + \sum \limits _{j = 1}^{\ell }3^{0} - \ell \\\ge & {} (|F'| + \ell )3^{-\frac{deg(F')}{|F'|+\ell }} - \ell \\\ge & {} (3^{-{\overline{d}}} - o(1))(k+\ell ) - \ell , \end{aligned}$$

proving condition (1). $\square$

Claim 3.27

For the values of $f_1$ and $f_2$ defined in Claim 3.24 and Claim 3.25, respectively, condition (3) holds.

Proof

Let $q_d$ be the probability that a vertex v of degree d joins one of $S_1$, $S_2$ or $S_{1,2}$ (WLOG). Since this is also the probability that no neighbour of v is colored 3, we have $q_d = \big (\frac{2}{3}\big )^{d}$. Also, observe that $q_d = 2p_{1,d} + p_{2,d}$. Therefore,

$$\begin{aligned} 2f_1 k + f_2 k \ge 2f_1|F'| + f_2|F'|= & {} 2\cdot \sum \limits _{d} p_{1,d}\cdot |F'_d| + \sum \limits _{d} p_{2,d}\cdot |F'_d|\\= & {} \sum \limits _{d}|F_d'|\cdot q_d\\= & {} \sum \limits _{v \in F'} \left( \frac{2}{3}\right) ^{deg(v)} + \sum \limits _{j = 1}^{\ell }3^{0} - \ell \\\ge & {} (|F'| + \ell )\left( \frac{2}{3}\right) ^{\frac{deg(F')}{|F'|+\ell }} - \ell , \end{aligned}$$

where the last inequality follows from convexity of $\left( \frac{2}{3}\right) ^x$. Again, we have $\frac{deg(F')}{|F'|+\ell } \le \frac{deg(F)}{k+\ell } = {\overline{d}}$, and $|F'| \ge k - o(k+\ell )$. So,

$$\begin{aligned} (f_2 + 2f_1)k \ge \left( \left( \frac{2}{3}\right) ^{{\overline{d}}} - o(1)\right) (k+\ell ) - \ell , \end{aligned}$$

proving condition (3). $\square$

$\square$

We now describe the structure of the three-way separator in more detail which will help in designing the algorithm utilizing it. Let’s say we are given a graph $G=(V,E)$, an afd-set F of size at most $k+1$ and a three-way separation $(S_1, S_2, S_3, S_{1,2}, S_{2,3}, S_{2,3},$ $S_{1,2,3})$ as in Lemma 3.22. Let $f_1$ and $f_2$ be from the conditions of Lemma 3.22. Define $f_3:=1-3f_1-3f_2$, so that $f_3k +\ell - o(k+\ell ) \le |S_{1,2,3}|\le f_3k + \ell + o(k+\ell )$.

Notice that $G[S_1 \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}] - (F \cup S_{1,2,3})$ is a forest, as $S_{\epsilon }$ (from Lemma 3.22) includes the $\ell$ vertices corresponding to the $\ell$ extra edges of the $\ell$-forest $G-F$. Thus, $(S_1 \cap F)\cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}$ is an fvs of $S_1 \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}$. The size of this fvs is,

$$\begin{aligned} |(S_1 \cap F)\cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}|&= |S_1 \cap F|+ |S_{1,2}|+|S_{1,3}|+ |S_{1,2,3}| \\&\le (f_3+2f_2+f_1)k+\ell +o(k+\ell ) \end{aligned}$$

Therefore, we can compute a tree decomposition of $G[S_1 \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}]$ of width $(f_3+2f_2+f_1)k+\ell +o(k+\ell )$ as follows: start with a tree decomposition of width 1 of the forest $G[S_1 \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}] - (F \cup S_{1,2,3})$, and then add all vertices in $(S_1 \cap F) \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}$ to each bag. Call this tree decomposition ${\mathbb {T}}_1$. Similarly, we can compute a tree decomposition of $G[S_2 \cup S_{1,2}\cup S_{2,3} \cup S_{1,2,3}]$ and $G[S_3 \cup S_{1,3}\cup S_{2,3} \cup S_{1,2,3}]$ in the same way, call them ${\mathbb {T}}_2$ and ${\mathbb {T}}_3$ respectively. It is evident from the construction procedure it takes polynomial time to compute these tree decompositions.

Note 3.28

Observe that there is no edge connecting any pair among $S_1$, $S_2$ and $S_3$, and $S_{i,j}$ has neighbours only in $S_i$ and $S_j$. Also, the set $(S_1 \cap F) \cup S_{1,2}\cup S_{1,3} \cup S_{1,2,3}$ is present in every bag of ${\mathbb {T}}_1$. Similarly, $(S_2 \cap F) \cup S_{1,2}\cup S_{2,3} \cup S_{1,2,3}$ and $(S_3 \cap F) \cup S_{1,3}\cup S_{2,3} \cup S_{1,2,3}$ are present in every bag of ${\mathbb {T}}_2$ and ${\mathbb {T}}_3$ respectively. This observation and the three decompositions obtained will be crucial for the proof of Lemma 3.30.

Similar to the two-way separator case, we now describe the routines BRIAFD2. and RIAFD_IC2 which will utilize the three-way separator.

Note 3.29

In BRIAFD2, values of some variables are not assigned to maintain clarity. In the algorithm, w, a, b are variables to account for overcounting in $S_{1,2,3}$. If we define $s_1 = f^{-1}(\{{{\textbf {L}}}, {{\textbf {R}}}\})$ then $w = 2 \cdot \omega (S_{1,2,3} {\setminus } s_1)$, $a = 2 \cdot |s_1|$ and $b = 2 \cdot |E[s_1,s_1]|$. For the overcounting that takes place within $S_{1,2}$, $S_{2,3}$ and $S_{1,3}$, we define the variables $w_i$, $a_i$ and $b_i$ for $i \in [3]$. We take $w_1 = a_1 = b_1 = 0$. If we define $s_2 = f_2^{-1}(\{{{\textbf {L}}}, {{\textbf {R}}}\})$, then $w_2 = \omega (S_{1,2} {\setminus } s_2)$, $a_2 = |s_2|$, $b_2 = |E[s_2,s_2]|$. If we define $s_3 = f_1^{-1}(\{{{\textbf {L}}}, {{\textbf {R}}}\}) \uplus f_2^{-1}(\{{{\textbf {L}}}, {{\textbf {R}}}\})$, then $w_3 = \omega ((S_{2,3} \uplus S_{1,3}) {\setminus } s_3)$, $a_3 = |s_3|$, $b_3 = |E[s_3,s_3]|$.

Algorithm 5

BRIAFD2$(G,R,k,\ell ,F,S_1, S_2, S_3, S_{1,2}, S_{1,3}, S_{2,3}, S_{1,2,3},\overline{d})$

Lemma 3.30

Given a graph G, an afd-set F of G of size at most $k+1$, parameter ${\overline{d}}$, and a three-way separation $(S_1, S_2, S_3, S_{1,2}, S_{1,3}, S_{2,3},S_{1,2,3})$ as given by Lemma 3.22, the Algorithm $\texttt{BRIAFD2}$ outputs a riafd-set of size at most k satisfying $deg(F) \le {\overline{d}}(|F|+\ell )$, or Infeasible if none exists, with high probability. The algorithm runs in time ${\mathcal {O}}^{\star }(3^{(1-min\{\left( \frac{2}{3}\right) ^{{\overline{d}}}, (3-\omega )\left( \frac{2}{3}\right) ^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}}\}+o(1))k}\cdot 3^{(1+\omega -((3-\omega )\left( \frac{2}{3}\right) ^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})+o(1))\ell })$, where $\omega$ is the exponent of the matrix multiplication algorithm used.

Proof

For the time bound, firstly notice that lines 14 takes polynomial time due to the observation given in Note 3.28 and Claim 3.5. Let $f_1,f_2$ and $f_3$ be from Lemma 3.22 and Note 3.28. For each of the ${\mathcal {O}}^{\star }(3^{f_3k + \ell + o(k+\ell )})$ iterations on Line 7, building the graph H (Lines $9-19$) takes time ${\mathcal {O}}^{\star }(3^{(2f_2+f_1)k+o(k+\ell )})$, and running matrix multiplication on Line 20 on a graph with ${\mathcal {O}}^{\star }(3^{f_2k+o(k+\ell )})$ vertices to compute the sum over product of weights on the three edges of all triangles takes time ${\mathcal {O}}^{\star }(3^{\omega f_2 k + o(k+\ell )})$. Therefore, the total running time is

 ${\mathcal {O}}^{\star }(3^{f_3k+\ell +o(k+\ell )}(3^{(2f_2+f_1)k+o(k+\ell )} + 3^{\omega f_2 k + o(k+\ell )}))$

$$\begin{aligned}= & {} {\mathcal {O}}^{\star }(3^{(f_3+2f_2+f_1)k+\ell +o(k+\ell ))} + 3^{(f_3+\omega f_2)k+l+o(k+\ell )})\\= & {} {\mathcal {O}}^{\star }(3^{(1-f_2-2f_1)k+\ell +o(k+\ell ))} + 3^{(1-(3-\omega ) f_2-3f_1)k+l+o(k+\ell )})\\= & {} {\mathcal {O}}^{\star }(3^{(1-(f_2+2f_1))k+\ell +o(k+\ell ))} + 3^{(1-(3-\omega )(f_2+2f_1)-(2\omega -3)f_1)k+l+o(k+\ell )})\\\le & {} {\mathcal {O}}^{\star }((3^{(1-(\frac{2}{3})^{{\overline{d}}}+o(1))k} + 3^{(1-((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}}+o(1))k})\cdot \\{} & {} \,\,\,\,\,\,\,\,\,3^{(1+\omega -((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})+o(1))\ell }), \end{aligned}$$

where the last inequality uses the conditions (1) and (3) of Lemma 3.22, and the fact that $2\omega -3 \ge 0$. This gives the desired time bound. Also, by Line 3 and Lemma 2.4, the algorithm succeeds with high probability.

The proof of correctness is similar to proof of Lemma 15 in [14]. We claim that at Line 21, count $= |{\mathcal {C}}_W^{n-k,B}|$ for some A, B and $W = i\cdot n^2 + d$ (from Lemma 3.3). First observe that there is no edge between $S_1$ and $S_{2,3}$. So, number of extensions of $S_1$ only depend on $S_{1,2}$ and $S_{1,3}$. For each mapping of $S_{1,2} \cup S_{1,3}$, imagine adding an edge between the respective mappings in the graph H, with weight as the number of extensions in $S_1$. Proceed analogously in $S_2$ and $S_3$. Thus, H will be a tripartite graph. Now, merging the solutions, i.e. finding the total number of extensions (for a fixed mapping of $S_{1,2,3}$), amounts to computing the sum over product of weights of three edges forming triangles in H, which can be solved using a standard matrix multiplication routine. This along with correctness of RIAFD-FCCount completes the proof of the claim, thereby completing the proof of correctness. $\square$

Algorithm 6

$\mathtt {RIAFD\_IC2}(G,R,k,\ell ,\overline{d})$

Lemma 3.31

Algorithm $\mathtt {RIAFD\_IC2}$ solves BRIAFD with high probability, in

${\mathcal {O}}^{\star }(3^{(1-min\{(\frac{2}{3})^{{\overline{d}}},(3-\omega )(\frac{2}{3}) ^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}}\}+o(1))k}\cdot 3^{(1+\omega -((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})+o(1))\ell })$ time.

The proof is similar to the proof of Lemma 3.21, hence it is omitted.

3.3.3 Algorithms for RIAFD

Having described the Dense and the Sparse Cases, we now combine them to give the final randomized algorithms.

${\mathcal {O}}^\star (2.85^k8.54^\ell )$ Algorithm in Polynomial Space Now, we give the Algorithm RIAFD1, which is the complete randomized algorithm combining the Dense and the Sparse Cases (small separator).

Algorithm 7

RIAFD1$(G,R,k,\ell )$

Lemma 3.32

Fix the parameter $\epsilon \in (0,1)$ and ${\overline{d}}:=\frac{4-2\epsilon }{1-\epsilon }$, let $c_k:=max\big \{3-\epsilon ,3^{1-2^{-{\overline{d}}}}\big \}$ and $c_\ell :=3^{2-2^{-{\overline{d}}}}$. Then $\texttt{RIAFD1}$ succeeds with probability at least $\frac{c_k^{-k}c_\ell ^{-\ell }}{k+1}$ and has ${\mathcal {O}}^{\star }(3^{o(k+\ell )})$ expected running time and uses polynomial space.

Proof

We will focus on running time for each iteration of the outer loop. The computation till line 5 takes $n^{{\mathcal {O}}(1)}$ time. Line 6 is executed with probability $3^{-(1 - 2^{{\overline{d}}})k'} \cdot 3^{-(2 - 2^{{\overline{d}}})\ell }$ and takes time ${\mathcal {O}}^{\star }(3^{(1 - 2^{{\overline{d}}}+o(1))k'} \cdot 3^{(2 - 2^{{\overline{d}}}+o(1))\ell })$. So, in expectation, the total computation cost of Line 6 is ${\mathcal {O}}^{\star }(3^{o(k+\ell )})$ per value of $k'$, and also ${\mathcal {O}}^{\star }(3^{o(k+\ell )})$ overall. Note here that for all values of $\epsilon \in (0,1)$, $c_k\ge 2$ and $c_l\ge 1$. The space bound follows from Lemma 3.21.

Now, we prove that RIAFD1$(G,k,\ell )$ succeeds with probability at least $\frac{c_k^{-k}\cdot c_\ell ^{-\ell }}{k+1}$. We use induction on $k'$. The statement is trivial when $k'=0$, since no probabilistic reduction is used and hence it succeeds with probability 1. For the inductive step, consider an instance RIAFD1$(G,k',\ell )$. Let $(G', k',\ell )$ be the reduced instance after Line 2. Suppose that every riafd-set F of G of size $k'$ satisfies the condition $deg(F) \le {\overline{d}}(k'+l)$; here, we only need the existence of one such F. In this case, if Line 6 is executed, then it will correctly output a riafd-set F of size at most $k'$, with high probability by Lemma 3.21. This happens with probability at least

$$\begin{aligned} 3^{-(1-2^{{\overline{d}}})k'} \cdot 3^{-(2-2^{{\overline{d}}})\ell } \cdot \left( 1 - \frac{1}{n^{{\mathcal {O}}(1)}}\right) \ge c_k^{-k'}\cdot c_\ell ^{-\ell } \cdot \frac{1}{k+1} \ge \frac{c_k^{-k}\cdot c_\ell ^{-\ell }}{k+1}, \end{aligned}$$

as desired.

Otherwise, suppose that the above condition doesn’t hold for every riafd-set F of $G'$ of size $k'$. This means that there exists a riafd-set F of size $k'$ such that $deg(F) \ge {\overline{d}}(k'+l)$. In this case, by Lemma 3.12, Reduction 2 succeeds with probability at least $\frac{1}{3-\epsilon }$. This is assuming, of course, that Line 6 is not executed, which happens with probability $1 - c_k^{-k'}\cdot c_\ell ^{-\ell } \ge 1 - c_k^{-k'} \ge 1 - 2^{-k'} \ge 1 - \frac{1}{k'}$, since $c_l \ge 1$ and $c_k \ge 2$. By induction, the recursive call on Line 9 succeeds with probability at least $\frac{c_k^{-(k'-1)}\cdot c_\ell ^{-\ell }}{(k'-1)}$. So, the overall probability of success is at least,

$$\begin{aligned} \left( 1-\frac{1}{k'}\right) \cdot \frac{1}{3-\epsilon }\cdot \frac{c_k^{-(k'-1)}\cdot c_\ell ^{-\ell }}{(k'-1)}&\ge \left( \frac{k'-1}{k'}\right) \cdot \frac{1}{c_k}\cdot \frac{c_k^{-(k'-1)}\cdot c_\ell ^{-\ell }}{(k'-1)}\\&= \frac{c_k^{-k'}\cdot c_\ell ^{-\ell }}{k'} \\&\ge \frac{c_k^{-k}\cdot c_\ell ^{-\ell }}{k+1}, \end{aligned}$$

as desired. Note that on line 9 adding the neighbours of v to $R'$ in the recursive call ensures that F is independent on addition of v to it. $\square$

Unless R is explicitly nonempty, we set $R=\varnothing$ to solve RIAFD. To optimize for $c_k$, we set $\epsilon \approx 0.155433$, giving $c_k \le 2.8446$ and $c_\ell \le 8.5337$. Theorem 1.2 (2) now follows by combining Lemma 3.32 and Lemma 2.4.

${\mathcal {O}}^\star (2.7^k36.61^\ell )$ Using Lemma 3.30 and Lemma 3.31 and the Dense Case, we now prove the main result, Theorem 1.2 (3), restated below.

Theorem 3.33

(Restatement of Theorem 1.2 (3)) There is a randomized algorithm that solves RIAFD in time ${\mathcal {O}}^{\star }(2.7^k36.61^\ell )$, with high probability.

Proof

We run RIAFD1, replacing every occurrence of RIAFD_IC1 with RIAFD_IC2. We define ${\overline{d}}:= \frac{4-2\epsilon }{1 - \epsilon }$ for some $\epsilon > 0$ (to be determined later); note that ${\overline{d}} \ge 4$ for any $\epsilon > 0$. By Lemma 3.31, RIAFD_IC2 runs in time ${\mathcal {O}}^{\star }(3^{(1-((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})+o(1))k}\cdot 3^{(1+\omega -((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})+o(1))\ell })$. Hence, RIAFD1 runs in time ${\mathcal {O}}^{\star }(c_k^k\cdot c_\ell ^\ell )$, by Lemma 2.4 to get a high success probability, for $c_k:= max\big \{ 3-\epsilon , 3^{1-((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})}\big \}$ and

$c_\ell := 3^{1+\omega -((3-\omega )(\frac{2}{3})^{{\overline{d}}}+(2\omega -3)3^{-{\overline{d}}})}$. Since $\omega < 2.3728639$ [31], we set $\omega = 2.3728639$ and optimize for $c_k$ and $c_\ell$. By setting $\epsilon \approx 0.3000237$, we get $c_k \le 2.699977$ and $c_\ell \le 36.602$, as desired. $\square$

3.4 Improving Dependency on $\ell$

In this subsection, we will try to reduce the dependency on $\ell$ in the Cut & Count algorithm. To achieve this, we will construct a tree decomposition with reduced dependency on $\ell$.

Lemma 3.34

Given a graph $G=(V,E)$ and an riafd-set F of size k, there exists a tree decomposition of width at most $k + \frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$ for G and it can be constructed in polynomial time.

Proof

Given a graph $G=(V,E)$ with n vertices and m edges, we define the graph $G'(V',E')$ $:= G[V/F]$. $G'$ is an $\ell$-forest from the definition of riafd-set. We apply the following reduction rules exhaustively on $G'$:

• $R_0$: If there is a $v\in V'$ with $deg(v)=0$, then remove v.

• $R_1$: If there is a $v\in V'$ with $deg(v)=1$, then remove v.

• $R_2$: If there is a $v\in V'$ with $deg(v)=2$, then contract v, i.e. remove v and insert a new edge between its two neighbors, if no such edge exists.

For the safeness of the above reduction rules refer to [32]. Let the reduced graph be called $G''(V'',E'')$. If $G''$ is an empty graph, $\textbf{tw}(G') \le 2$ [32, Lemma 4.1] and a tree decomposition of width at most $O(\log n)$ can be computed in polynomial time [32, Lemma 4.3].

Otherwise, we have $\textbf{tw}(G')>2$. It is trivial to see that after applying the above reduction rules the $G''$ we get is also an $\ell$-forest. Therefore, after removing at most $\ell$ edges from $G''$, we are left with at most $|V''| - 1$ edges (since the remaining graph is a forest). Therefore, we get that $|E''| \le |V''|+\ell -1$. Since the degree of each vertex in $G''$ is at least 3, $|E''| \ge 3|V''|/2$. Therefore, $1.5|V''| \le |V''| + \ell - 1$ from which we obtain the bounds $|V''| \le 2\ell$ and $|E''| \le 3\ell$. We need to use the following results from [32].

Theorem 3.35

[32, Theorem 4.7] Given a graph G(V, E), we can obtain a tree decomposition of G of width at most $|E|/5.769 + {\mathcal {O}}(log(|V|))$ in polynomial time.

This implies that, $G''$ has a tree decomposition of width at most $\frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$ (since $\ell = O(n^2)$) which can be computed in polynomial time.

Lemma 3.36

[32, Lemma 4.2] Given a connected graph G, with $\textbf{tw}(G)>2$ and let $G'$ be a graph obtained from G by applying $R_0$, $R_1$ and $R_2$ then $\textbf{tw}(G) = \textbf{tw}(G')$

Also, from proof of Lemma 4.2 of [32], it’s easy to see that this also works on graphs which might not be connected. Given these facts, we see that we can obtain a tree decomposition of $G'$ with width at most $\frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$ in polynomial time from the tree decomposition of $G''$. Now to get the tree decomposition of the given graph instance G, add F (of size k which we removed) to all the bags of the tree decomposition of $G'$. This finally gives the required tree decomposition of G of width at most $k + \frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$. $\square$

We combine the treewidth bound that can be obtained from Lemma 3.34 with Iterative Compression, together with the $3^{\textbf{tw}}$ algorithm to obtain an ${\mathcal {O}}^\star (3^k1.78^\ell )$ algorithm for solving RIAFD.

We now describe the working of the routine RIAFD_IC3. The iterative compression routine proceeds as follows. We start with an empty graph, and add the vertices of G one by one, while always maintaining a riafd-set of size at most k in the current graph. Maintaining a riafd-set for the current graph helps us utilize Lemma 3.34 to obtain a small tree decomposition (of size $k + \frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$). Then we can add the next vertex in the ordering to all the bags in the tree decomposition to get a new riafd-set of size k in ${\mathcal {O}}^\star (3^{\textbf{tw}})$. If we are unable to find such a riafd-set in a particular iteration, we can terminate the algorithm early.

Algorithm 8

$\mathtt {RIAFD\_IC3}(G,R,k,\ell )$

Now we restate Theorem 1.2 (4) and prove it.

Theorem 3.37

(Restatement of Theorem 1.2 (4)) $\mathtt {RIAFD\_IC3}$ solves RIAFD problem in time ${\mathcal {O}}^\star (3^k1.78^\ell )$ and exponential space with high probability.

Proof

Suppose that there exists a riafd-set $F^\star$ of size at most k. Let $(v_1, v_2, \ldots ,$ $v_n)$ be the ordering from Line 1, and define $V_i:= \left\{ v_1, \ldots ,v_i\right\}$. We note that $F^\star \cap V_i$ is a riafd-set of $G\left[ V_i\right]$ so RIAFD problem on Line 6 will be feasible in each iteration (and will be computed correctly with high probability in every iteration). Therefore, with high probability, a riafd-set is returned successfully (by union bound).

We now bound the running time. On Line 4, the current set F is a riafd-set of $G\left[ V_i\right]$, so Lemma 3.34 guarantees a tree decomposition of width at most $k + \frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))$ and adding $v_i$ to each bag on Line 5 increases the width by at most one. By the Cut & Count algorithm from Sect. 3.1, Line 6 runs in time ${\mathcal {O}}^\star (3^{\left( k + \frac{3}{5.769}\ell + {\mathcal {O}}(\log (n))\right) }) = {\mathcal {O}}^\star (3^{\left( k + \frac{3}{5.769}\ell \right) })$. This gives the desired time of ${\mathcal {O}}^\star (3^k1.78^\ell )$ on simplification. The space bound follows directly from the description of RIAFD_IC3, Lemma 3.34 and the space bound of the Cut & Count algorithm. $\square$

4 Pseudoforest Deletion

In this section we present faster randomized algorithms for Pseudoforest Deletion. In Sect. 4.1 we present an ${\mathcal {O}}^{\star }(3^{\textbf{tw}})$ Cut & Count algorithm building on techniques from [11] for FVS. Using this we give an ${\mathcal {O}}^\star (3^k)$ time and polynomial space algorithm in Sect. 4.2. In Sect. 4.3, we use the method in [14] to get an ${\mathcal {O}}^\star (2.85^k)$ time and polynomial space algorithm. Henceforth, the abbreviation pds denotes a pseudoforest deletion set, i.e., a solution to an instance of Pseudoforest Deletion.

4.1 ${\mathcal {O}}^{\star }(3^{\textbf{tw}})$ Algorithm

Lemma 4.1

A graph $G=(V,E)$ with n vertices and m edges is a pseudoforest if and only if it has $n-m$ connected components which are trees.

Proof

We only consider cases where $n\ge m$. Note that any graph $G = (V,E)$ with n vertices and m edges has at least $n-m$ connected components which are trees. This is because of a simple additive argument and the fact that for a connected component other than a tree with $n'$ vertices and $m'$ edges, the term $n'-m'\le 0$.

Forward Direction: If G is a pseudoforest, then its connected components can be either a tree or a tree plus an edge. For the “tree plus edge component”, $n'-m'=0$. Hence we have $n-m$ trees.

Reverse Direction: We will prove the contrapositive, i.e., if G is not a pseudoforest, then it has strictly greater than $n-m$ connected components which are trees. To see this, consider the case when $n-m = \sum \limits _{i \in [cc(G)]} n_i-m_i$ where $n_i$ and $m_i$ are the number of vertices and the number of edges of the $i^{\text {th}}$ connected component, respectively. Since $n_i-m_i < 0$ for all connected components that are not pseudotrees, we have $n-m <$ number of connected components that are trees, as required. $\square$

We present a Cut & Count technique similar to the one for FVS in [11]. As the universe we take $U=V\times \{{\varvec{P}},{\varvec{M}}_1\}+E\times \{{\varvec{M}}_2\}$. The main difference between our algorithm from the one for FVS is we account for additional ${\varvec{M}}_2$ markers for the edges. For each edge, we a priori decide one of its endpoints to represent the edge, which we call the “representative vertex” of the edge. Also, given a set of marked edges $M_2$, $\psi (M_2)$ denotes the set of representative vertices of the edges in $M_2$. When an edge is marked, it is assumed to be deleted and it’s representative vertex is marked. This assumption will be crucial in our algorithm.

We assign weights uniformly at random to the elements of our universe with the weight function $\omega :U\rightarrow \{1,\ldots ,N\}$, where $N=2|U|=4|V|+2|E|$.

The Cut Part: For integers A, B, C, D, W we define:

• 1. ${{\mathcal {R}}^{A,B,C,D}_W}$ to be the family of solution candidates: ${{\mathcal {R}}^{A,B,C,D}_W}$ is the family of triples $(X,M_1,M_2)$ where $X \subseteq {V}$, $|X|=A$, $|E[X]| = B+D$ of which D edges are marked, i.e $M_2\subseteq E[X]$ and $|M_2|=D$, $M_1\subseteq X$, $|M_1|=C$ and $\omega ((V {\setminus } X)\times \{{\varvec{P}}\})+\omega (M_1\times \{{\varvec{M}}_1\})+ \omega (M_2\times \{{\varvec{M}}_2\})=W$.

• 2. ${S^{A,B,C,D}_W}$ to be the set of solutions: the family of triples $(X,M_1,M_2)$, where $(X,M_1,M_2)\in {{\mathcal {R}}^{A,B,C,D}_W}$ and every connected component of $G[X] - M_2$ is a tree containing at least one ${\varvec{M}}_1$ or ${\varvec{M}}_2$ marker.

• 3. ${{\mathcal {C}}^{A,B,C,D}_W}$ to be the family of pairs $((X,M_1,M_2),(X_L,X_R))$ where $(X,M_1,M_2)$ $\in {{\mathcal {R}}^{A,B,C,D}_W}$, $M_1\subseteq X_L$, $\psi (M_2)\subseteq X_L$ and $(X_L,X_R)$ is a consistent cut of G[X].

According to [11], a consistent cut $(X_L, X_R)$ is one where there is no edge between the cuts. But, as we stated that an edge marked with a marker $\varvec{M_2}$ is deleted, these edges are allowed to cross the cuts. However, the representative vertex must belong to $X_L$ only.

Lemma 4.2

The graph G admits a pseudoforest deletion set of size k iff there exist integers B, D, W such that ${S^{n-k,B,n-k-B-D,D}_W}$ is nonempty.

Proof

Forward direction: Let G have a pds P of size k. Then $G' = G[V\setminus P]=(V',E')$ is a pseudoforest with $n-k$ vertices. Let $G'$ have D connected components which are “a tree plus an edge” and by Lemma 4.1$G'$ has $n-k-B-D$ connected components which are trees, where $B = |E'| - D$. Then we can place one ${\varvec{M}}_1$ marker each for all the tree components. Let $M_1$ be the set of these marked vertices. In each of the D “tree plus an edge components”, only one cycle exists. Choose any edge belonging to that cycle as an ${\varvec{M}}_2$ marker. Thus, by definition, this edge is deleted making the component a tree. Also, as defined above, the representative vertex of the deleted edge is marked. Let $M_2$ be the set of all the marked edges. Also, let $W:= \omega ((V {\setminus } X)\times \{{\varvec{P}}\})+\omega (M_1\times \{{\varvec{M}}_1\})+\omega (M_2\times \{{\varvec{M}}_2\})$. We now see that $(X,M_1,M_2)\in S_W^{n-k,B,n-k-B-D,D}$.

Reverse direction: We have that ${S^{n-k,B,n-k-B-D,D}_W}$ is non-empty for some integers B, D and W. Let us consider some $(X,M_1,M_2)\in {S^{n-k,B,n-k-B-D,D}_W}$. Then, the graph G[X] has $n-k$ vertices, $B+D$ edges and every connected component of $G[X] - M_2$ is a tree with at least one ${\varvec{M}}_1$ or ${\varvec{M}}_2$ marker, by definition. Since, $G[X] - M_2$ is a forest with $n-k$ vertices and B edges, it has exactly $n-k-B$ components which each need to have at least one of the $n-k-B$ markers. Therefore, every connected component of $G[X] - M_2$ is a tree with exactly one of ${\varvec{M}}_1$ or ${\varvec{M}}_2$ marker. Notice that if a tree component in G[X] is marked by an ${\varvec{M}}_2$ marker, then the number of unmarked tree components remains the same, as on marking an edge, the edge is deleted (by definition) marking it’s representative vertex. Thus, on deletion we get two trees among which one is marked while the other is still unmarked. These unmarked tree components necessarily have to be taken care of by ${\varvec{M}}_1$ markers. Therefore, the number of tree components has to be equal to the number of ${\varvec{M}}_1$ markers, i.e. the number of tree components is exactly $n-k-B-D$. Therefore, by Lemma 4.1G[X] is a pseudoforest. $\square$

Lemma 4.3

$|{\mathcal {C}}^{A,B,C,D}_W|\equiv |S^{A,B,C,D}_W| \, (\text {mod} \, 2)$.

Proof

Consider a triple $(X,M_1,M_2)$ in ${\mathcal {R}}^{A,B,C,D}_W$. If $G[X] - M_2$ has c connected components without any marker(${\varvec{M}}_1$ or ${\varvec{M}}_2$), then it contributes $2^c$ to $|{\mathcal {C}}^{A,B,C,D}_W|$. Hence, if $c \ge 1$, the triple $(X,M_1,M_2)$ contributes $2^c \equiv 0\ (\text {mod}\ 2)$ to $|{\mathcal {C}}^{A,B,C,D}_W|$ $(\text {mod}\ 2)$. A triple $(X,M_1,M_2) \in S^{A,B,C,D}_W$ iff $G[X] - M_2$ has no unmarked connected components. Thus, it contributes $1\, (\text {mod} \, 2)$ to both $S^{A,B,C,D}_W$ and ${\mathcal {C}}^{A,B,C,D}_W$. Hence, $|{\mathcal {C}}^{A,B,C,D}_W|\equiv |S^{A,B,C,D}_W| \, (\text {mod}\, 2)$. $\square$

The Count Part: Now we describe a dynamic programming procedure CountC($\omega ,A,B,C,D,W,{\mathbb {T}}$), that given a nice tree decomposition ${\mathbb {T}}$, weight function $\omega$ and integers A, B, C, D, W, computes $|{\mathcal {C}}^{A,B,C,D}_W|$ mod 2. For every bag $x\in {\mathbb {T}}$, $a\le |V|$, $b\le |V|$, $c\le |V|$, $d\le |V|$, $w\le 3N|V|$ and $s\in \{{\varvec{F}},{\varvec{L}},{\varvec{R}}\}^{B_x}$ (called the colouring), define

$$\begin{aligned} {\mathcal {R}}_x(a,b,c,d,w)= & {} \Big \{(X,M_1,M_2)\;\big |\; X\subseteq V_x\wedge \,|X|=a\wedge \; |E_x\cap E[X]|=b+\\ {}{} & {} d\wedge M_1\subseteq X \wedge \; M_2\subseteq E_x\cap E[X] \wedge \; |M_1|=c\wedge \; |M_2|= \\{} & {} d\wedge \omega ((V\setminus X)\times \varvec{\{P\} })+\omega (M_1\times \{{\varvec{M}}_1\})+\omega (M_2\times \{{\varvec{M}}_2\})\\{} & {} =w\Big \} \\ {\mathcal {C}}_x(a,b,c,d,w)= & {} \Big \{((X,M_1,M_2),(X_L,X_R))\;\big |\;(X,M_1,M_2)\in {\mathcal {R}}_x(a,b,c,d,w)\\ {}{} & {} \wedge M_1\subseteq X_L\wedge \psi (M_2)\subseteq X_L\wedge (X,(X_L,X_R)) \text { is a consistently}\\{} & {} \text {cut subgraph of } G_x\Big \} \\ A_x(a,b,c,d,w,s)= & {} \Big |\Big \{((X,M_1,M_2),(X_L,X_R))\in C_x(a,b,c,d,w)\;\big | (s(v)={\varvec{L}}\\{} & {} \implies v\in X_L)\wedge (s(v)={\varvec{R}}\implies v\in X_R)\wedge (s(v)={\varvec{F}}\implies \\{} & {} v\notin X)\Big \}\Big | \end{aligned}$$

Note that we may assume $b\le |V|$ and $d\le |V|$ because the number of edges in a pseudoforest cannot exceed the number of vertices. The accumulators a, b, c, d, w keep track of the number of vertices, edges of X, $M_1$ markers, $M_2$ markers and the target weight respectively. Hence $A_x(a,b,c,d,w,s)$ is the number of pairs in ${\mathcal {C}}_x(a,b,c,d,w)$ having a fixed interface with vertices in $B_x$. Note that we choose a vertex to be an $M_1$ marker in its respective forget bag. For the $M_2$ marker for an edge we make the choice in the introduce edge bag, where we decide to not include it in G[X] if it is chosen as a $M_2$ marker. Also note that the endpoints in this case for this edge can be on opposite sides of the cut.

The algorithm computes $A_x(a,b,c,d,w,s)$ for each bag $x\in {\mathbb {T}}$ and for all reasonable values of a, b, c, d, w and s. We now give the recurrence for $A_x(a,b,c,d,w,s)$ used by the dynamic programming algorithm. In order to simplify notation let v be the vertex introduced and contained in an introduce bag, (u, v) the edge introduced in an introduce edge bag with u being the representative of the edge (i.e. $\psi (\{(u,v)\}) = \{u\}$), and let y, z denote the left and right child of x respectively in ${\mathbb {T}}$ if present.

• Leaf bag:

  $$\begin{aligned} A_x(0,0,0,0,0,\varnothing )&=1 \end{aligned}$$

• Introduce vertex bag:

  $$\begin{aligned} A_x(a,b,c,d,w,s\cup \{(v,{\varvec{F}})\})&=A_y(a,b,c,d,w-\omega ((v,{\varvec{P}})),s)\\ A_x(a,b,c,d,w,s\cup \{(v,{\varvec{L}})\})&= A_y(a-1,b,c,d,w,s)\\ A_x(a,b,c,d,w,s\cup \{(v,{\varvec{R}})\})&= A_y(a-1,b,c,d,w,s) \end{aligned}$$

• Introduce edge bag:

  • If $s(u)={\varvec{L}}\wedge s(v)={\varvec{R}}$

    $$\begin{aligned} A_x(a,b,c,d,w,s) = A_y(a,b,c,d-1,w-\omega ((u,v),{\varvec{M}}_2)) \end{aligned}$$

  • If $s(u)={\varvec{F}}\vee s(v)={\varvec{F}}\vee s(u)=s(v)={\varvec{R}}$

    $$\begin{aligned} A_x(a,b,c,d,w,s)&= A_y(a,b-[s(u)=s(v)\ne {\varvec{F}}],c,d,w,s) \end{aligned}$$

  • If $s(u)=s(v)={\varvec{L}}$

    $$\begin{aligned} A_x(a,b,c,d,w,s)&= A_y(a,b-1,c,d,w,s)\\&\ \ \ +A_y(a,b,c,d-1,w-\omega ((u,v),{\varvec{M}}_2),s) \end{aligned}$$

  Here we remove table entries not consistent with the edge (u, v), and update the accumulator b storing the number of edges in the induced subgraph and we mark the edge (u, v) keeping u in $X_L$ updating the accumulator d (even in the case when u and v are in $X_L$ and $X_R$ respectively) of edges in the induced subgraph.

• Forget vertex bag:

  $$\begin{aligned} A_x(a,b,c,d,w,s)&= A_y(a,b,c-1,d,w-\omega ((v,{\varvec{M}}_1)),s[v\rightarrow {\varvec{L}}])\\&\;\;\;\;+ \sum \limits _{\alpha \in \{{\varvec{F}},{\varvec{L}},{\varvec{R}}\}}A_y(a,b,c,d,w,s[v\rightarrow \alpha ]) \end{aligned}$$

  If the vertex v was in $X_L$ then we can mark it and update the accumulator c. If we do not mark the vertex v then it can have any of the three states with no additional requirements imposed.

• Join bag:

  $$\begin{aligned} A_x(a,b,c,d,w,s)&= \sum \limits _{{\begin{array}{c} a_1+a_2=a+|s^{-1}(\{L,R\})|\\ b_1+b_2=b \\ c_1+c_2=c \\ d_1+d_2=d \\ w_1+w_2=w+\omega (s^{-1}({\varvec{F}})\times \{{\varvec{P}}\}) \end{array}}} A_y(a_1,b_1,c_1,d_1,w_1,s) \cdot \\&A_z(a_2,b_2,c_2,d_2,w_2,s) \end{aligned}$$

  The only valid combinations to achieve the colouring s is the same colouring in both the children bags. Since the vertices coloured ${\varvec{F}}$ according to s are present in both y and z, their contribution to the weight w and the number of the vertices a needs to be accounted for.

Since $|{\mathcal {C}}^{A,B,C,D}_W|\equiv A_r(A,B,C,D,W,\varnothing ) \ (\text {mod} \ 2)$, we compute $A_r(A,B,C,D,W,$ $\varnothing )$ for all reasonable values of the parameters as mentioned before using the dynamic programming procedure, which takes ${\mathcal {O}}^\star (3^{\textbf{tw}}|V|^{{\mathcal {O}}(1)})$ time. This concludes the description of the Cut & Count algorithm for pds.

We state the following equivalent of Lemma 3.3. The proof is omitted as it is very similar to the equivalent proof given for RIAFD.

Lemma 4.4

Let $G = (V,E)$ be a graph and d be an integer. Set the universe $U=V\times \{{\varvec{P}},{\varvec{M}}_1\}\cup E\times \{{\varvec{M}}_2\}$. Pick $\omega '(u) \in \{1, \ldots , 2 |U|\}$ uniformly and independent at random for every $u \in U$. Define $\omega : U \rightarrow {\mathbb {N}}$ such that $\omega ((v,{\varvec{P}})):= |V|^2\omega '((v,{\varvec{P}})) + deg(v)$ for all $v \in V$ and $\omega (u) = |V|^2\omega '(u)$ for all other $u \in U$. The following statements hold:

• 1. If for some integers $m'$, D, $W = i|V|^2 + d$ we have that $|{\mathcal {C}}_W^{n-k,m',n-k-m'-D,D}|$ $\not \equiv 0\ (\text {mod} \ 2)$, then G has a Pseudoforest Deletion set P of size k satisfying $deg(F) = d$.

• 2. If G has a Pseudoforest Deletion set P of size k satisfying $deg(P) = d$, then with probability at least 1/2 for some $m'$, D, $W = i|V|^2 + d$ we have that $|{\mathcal {C}}_W^{n-k,m',n-k-m'-D,D}| \not \equiv 0\ (\text {mod} \ 2)$.

4.2 ${\mathcal {O}}^\star (3^k)$ Algorithm in Polynomial Space

In this section, we present an ${\mathcal {O}}^\star (3^k)$ algorithm using polynomial space for solving Pseudoforest Deletion. First, we state the equivalent of Claim 3.5 and Theorem 3.6 for Pseudoforest Deletion problem. Their proofs are omitted since they work by replacing the Cut & Count algorithm for RIAFD with Cut & Count for PDS described above, replacing RIAFD-FCCount with PF-FCCount, taking modulo with 2 instead of $2^t$ and following a similar line of reasoning.

Claim 4.5

Given a tree decomposition ${\mathbb {T}}$ with a set $S\subseteq V$ which is present in all its bags and a vertex assignment function $f: S \rightarrow \{{\varvec{F}},{\varvec{L}},{\varvec{R}}\}$, there is a routine PF-FCCount$({\mathbb {T}},R,A,B,C,D,W,f)$ which can compute $|{\mathcal {C}}_{W}^{A,B,C,D}| \;(\text {mod} \; 2)$ in time ${\mathcal {O}}^\star \left( 3^{\textbf{tw}- |S|}\right)$.

Theorem 4.6

Given a tree decomposition ${\mathbb {T}}$, a set $S\subseteq V$ present in all bags of ${\mathbb {T}}$, parameter k, $\texttt{CutandCountPF}$ solves the pseudoforest deletion problem in ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}}\right)$ time and ${\mathcal {O}}^{\star }\left( 3^{\textbf{tw}- |S|}\right)$ space with high probability.

Lemma 4.7

Given a graph $G = (V,E)$ and a pds P of size k, you can construct a tree decomposition ${\mathbb {T}}$ which contains the set P in all bags and has width at most $k+2$ in polynomial time.

Proof

$G[V \setminus P]$ is a pseudoforest. Let $G[V \setminus P]$ have c connected components. Let us consider the $i^{\text {th}}$ component $C_i$ and denote their individual tree decomposition as ${\mathbb {T}}_i$. Note that $C_i$ is either a tree or a pseudoforest. If $C_i$ is a tree there is a trivial tree decomposition ${\mathbb {T}}_i$ of width 1. If not, then $C_i$ is a pseudotree. Remove any edge (u, v) from the only cycle in $C_i$ and construct the tree decomposition of the remaining tree. Add the vertex u in all bags of that tree decomposition to get ${\mathbb {T}}_i$ of width 2 for the pseudotree $C_i$. Now, make an empty bag as the root and connect the root of all ${\mathbb {T}}_i$ to it and call the resulting tree decomposition (of width 2) ${\mathbb {T}}'_i$. Now, adding P to all bags of ${\mathbb {T}}'_i$ gives the desired tree decomposition ${\mathbb {T}}_i$ of width $k+2$. The time bound is trivial from the description of the procedure. $\square$

Now, we state the following lemma and prove it.

Lemma 4.8

There exists an algorithm $\texttt{PF3k}$ that solves Pseudoforest Deletion in ${\mathcal {O}}^\star (3^k)$ time and polynomial space with high probability.

Proof

In algorithm RIAFD3k3l from Sect. 3.2, replace RIAFDCutandCount with CutandCountPF. Also replace the equivalent lemmas, theorems and claims. Denote this algorithm as PF3k. The proof of correctness and success-probability is similar to Theorem 1.2 (1) in Sect. 3.2. The running time and space bound follow by similar arguments in the proof of Theorem 1.2 (1), Theorem 4.6 and Lemma 4.7. $\square$

4.3 ${\mathcal {O}}^{\star }(2.85^k)$ Algorithm in Polynomial space

In this section, we present a ${\mathcal {O}}^{\star }(2.85^k)$ algorithm using polynomial space. We use the method from [14], dividing the problem into sparse and dense cases. Following are a few basic reduction rules for Pseudoforest Deletion [27].

Definition 4.9

Reduction 1: Apply the following reduction rules exhaustively until there is no edge of multiplicity larger than 3, no vertex with at most one loop, and degree of all vertices is at least 3.

• 1. If there is more than one self-loop at a vertex v, delete v and decrease k by 1; add v to the output pds.

• 2. If there is an edge of multiplicity larger than 3, reduce its multiplicity to 3.

• 3. If there is a a vertex v of degree at most 1, delete v.

• 4. If there is a vertex v of degree 2, delete v and join its neighbours with an edge.

• 5. If $k<0$, then we have a no instance. If $k>0$ and G is a pseudoforest, then we have a yes instance. If $k=0$, we have a yes instance iff G is a pseudoforest.

4.3.1 Dense Case

In this case, we apply a probabilistic reduction that capitalises on the fact that a large number of edges are incident to the pds. We will use the same ideas as of Reduction 2 for RIAFD in Sect. 3.3. Thus, even here we aim to obtain a reduction that succeeds with probability strictly greater than 1/3 so as to achieve a randomized algorithm running in ${\mathcal {O}}^{\star }(3-\epsilon )^k$ time that succeeds with high probability.

Definition 4.10

Reduction 2 (P): Assume that Reduction 1 does not apply and G has a vertex of degree at least 3. Sample a vertex $v \in V$ proportional to $\omega (v):= (deg(v)-2)$. That is, select each vertex with probability $\frac{\omega (v)}{\omega (V)}$. Delete v and decrease k by 1.

Claim 4.11

Let G be a graph, P a pds of G. Denote ${\overline{P}}:= V {\setminus } P$. We have that,

$$\begin{aligned} deg({\overline{P}}) \le deg(P) + 2(|{\overline{P}}|). \end{aligned}$$

Lemma 4.12

Given a graph G, if there exists a pds P of size k such that $deg(P) \ge \frac{4-2\epsilon }{1-\epsilon }k$, then success of Reduction 2 which is essentially picking a vertex v from the pds P occurs with probability at least $\frac{1}{3-\epsilon }$.

The proofs of the above claim and lemma follow a similar line of reasoning as the proofs of Claim 3.11 and Lemma 3.12, hence they are omitted.

4.3.2 Sparse Case

In this case, since $deg(P)/|P| \le {\overline{d}}$ and ${\overline{d}} = {\mathcal {O}}(1)$, it is possible to get a tree decomposition of size $(1-\Omega (1))k$.

We state this without proof through the following lemmas since they use the same ideas from [14], Lemma 3.14 and Lemma 3.18.

Lemma 4.13

Given (G, k) and a pds P of G of size exactly k, define ${\overline{d}}:= \frac{deg(P)}{k}$, and suppose that ${\overline{d}} = {\mathcal {O}}(1)$. There is a randomized algorithm running in expected polynomial time that computes a separation (A, B, S) of G such that:

• 1. $|A\cap P|,|B\cap P|\ge (2^{-{\overline{d}}}-o(1))k$

• 2. $|S|\le (1+o(1))k-|A\cap P|-|B\cap P|$

Proof

The proof is similar to that in [14]. The only difference is in the first step i.e construction of a $\beta$-separator $S_{\epsilon }$. For this we can use Lemma 2.7 which gives a $\beta$-separator of size at most $3\beta$ ($\textbf{tw}$ of any pseudoforest is at most 2), and as $\beta = \epsilon k = o(k)$, $|S_{\epsilon }| = o(k)$. All other steps and bounds remain exactly the same. $\square$

Lemma 4.14

Let G be a graph and P be a pds of G of size k, and define ${\overline{d}}:= \frac{deg(P)}{k}$. There is an algorithm that, given G and P, computes a tree decomposition of G of width at most $(1-2^{-{\overline{d}}}+o(1))k$, and runs in polynomial time in expectation.

As we are in the sparse case, which means that there exists a pds P of size k with bounded degree, i.e., $deg(P) \le {\overline{d}}k$. We call this bounded version of the problem, BPDS. As we saw, the small separator helps in constructing a tree decomposition of small width, but requires that we are given a pds of size k and bounded degree. To attain this, we use an Iterative Compression based procedure which at every iteration considers a pds of size at most k with bounded degree and uses it to construct the small separator. Using this small separator we construct a tree decomposition of small width and employ a Cut & Count based procedure to solve BPDS for the current induced subgraph, i.e, get a bpds of size at most k with bounded degree. This bpds is used for the next iteration, and so on.

Note 4.15

Using the tree decomposition obtained in Lemma 4.14, we can run the Cut & Count algorithm from Sect. 4.1. But this will utilize exponential space. To get polynomial space, we use the following idea.

Given an (A, B, S) separation of a graph G according to Lemma 4.13 along with a pds P of size at most k of bounded average degree ${\overline{d}}$, we construct a tree decomposition ${\mathbb {T}}'$ of G as follows: Since $(A\cap P)\cup S$ is a pds for $A\cup S$, we construct a nice tree decomposition ${\mathbb {T}}_1$ of $A\cup S$ which forgets all vertices in S at the last(going from a leaf bag to the root bag). Hence there is a bag $B_y$ which contains all the vertices $v\in S$ and nothing else. Upto this bag, no edge $e\in E[S,S]$ is introduced. Consider this part of the tree decomposition of ${\mathbb {T}}_1$(denote as ${\mathbb {T}}_1'$) up to node y. Similarly we construct a tree decomposition ${\mathbb {T}}_2$ for partition B as we did for A. There is a bag $B_z$ in ${\mathbb {T}}_2$ which contains all vertices $v\in S$ and nothing more. Denote the tree decomposition up to node z for ${\mathbb {T}}_2$ as ${\mathbb {T}}_2'$. The final tree decomposition ${\mathbb {T}}$ for G is constructed by joining ${\mathbb {T}}_1'$ and ${\mathbb {T}}_2'$ via a join node and then going toward the root we have the introduce edge bags and forget vertex bags for $v\in S$. We use this tree decomposition ${\mathbb {T}}'$ for proving the polynomial space bound in Algorithm BPDS.

Now, we give the claimed BPDS algorithm, which is a Cut & Count based algorithm that solves bounded degree PDS given a small separator.

Algorithm 9

$\texttt{BPDS}(G,P,k,A,B,S)$

Lemma 4.16

There is an Algorithm $\texttt{BPDS}$ that, given G, a pds P of G of size at most $k+1$, parameter ${\overline{d}}$, and a separation (A, B, S) as given by Lemma 4.13, outputs a pds of size at most k satisfying $deg(P)/|P| \le d$, or $\texttt{Infeasible}$ if none exists. The algorithm uses ${\mathcal {O}}^{\star }(3^{(1-2^{-{\overline{d}}}+o(1))k})$ time and polynomial space.

Proof

Note that we reorder the computation of algorithm CutandCountPF in a slightly different way on tree decomposition ${\mathbb {T}}'$ to achieve polynomial space. Follow the notations according to Note 4.15. The way we reorder the computation of CutandCountPF on tree decomposition ${\mathbb {T}}'$ is as follows: For a fixed colouring s of S, we compute $A_y(a,b,c,d,w,s)$ and $A_z(a,b,c,d,w,s)$ in polynomial space according to Claim 4.5. Now the remaining tree decomposition has bags only consisting of vertices in S. Using $A_y(a,b,c,d,w,s)$ and $A_z(a,b,c,d,w,s)$ for some colouring s of S we can compute $C_W^{A,B,C,D}$ for ${\mathbb {T}}'$ in polynomial space by Theorem 4.6.

The algorithm is clearly correct since it uses CutandCountPF as a subroutine with reordered computation. By Lemma 4.4, the pds P of size at most k is found using CutandCountPF with bounded average degree ${\overline{d}}$ with success probability at least 1/2. The success probability can be easily boosted by $n^{{\mathcal {O}}(1)}$ runs of the algorithm. The width of the tree decomposition from the input according to Lemma 4.14 is ${(1-2^{-{\overline{d}}}+o(1))k}$. Thus the time bound follows the time bound of the $\texttt{CutandCountPF}$ algorithm. $\square$

Now, we give the Iterative Compression routine which solves BPDS, as explained above.

Lemma 4.17

There exists an algorithm $\texttt{PFIC1}$ that solves BPDS in running time $O^{\star }(3^{(1-2^{-{\overline{d}}}+o(1))k})$ and polynomial space with high probability.

Proof

PFIC1 can be constructed by replacing every occurrence of BRIAFD1 with BPDS and constructing the separator using Lemma 4.13. The proofs of correctness, space bound and success-probability are similar to Lemma 3.21. $\square$

4.3.3 Combining the Sparse and Dense Cases

Having described the Dense and the Sparse Cases, we now combine them to give the final randomized algorithm.

Lemma 4.18

Fix the parameter $\epsilon \in (0,1)$ and let $c_\epsilon :=max\left\{ 3-\epsilon ,3^{1-2^{-\frac{4-2\epsilon }{1-\epsilon }}}\right\}$. If $c_\epsilon \ge 2$, there exists an algorithm $\texttt{PDS1}$ that succeeds with probability at least $c_\epsilon ^{-k}$. Moreover Algorithm $\texttt{PDS1}$ has expected polynomial running time and requires polynomial space.

Proof

In algorithm RIAFD1, replace every occurrence of RIAFDIC1 with PFIC1. Also, replace the Reduction rules with the ones given for Pseudoforest Deletion. This modified algorithm is PDS1. The running time, space bound and success probability analysis are similar to the analysis in proof of Lemma 3.32. $\square$

Note that the outer loop on k is not required here. If there exists a pds of size at most k, we can add arbitrary vertices to get a pds of size exactly k.

To optimize for $c_\epsilon$, we set $\epsilon \approx 0.155433$, giving $c_\epsilon \approx 2.8446$. Using Lemma 2.4 we can boost the success probability to be sufficiently high. Theorem 1.4 thus follows from Lemma 4.18 and Lemma 2.4.

5 Conclusion

In this paper, we applied the technique of Li and Nederlof [14] to other problems around the Feedback Vertex Set problem. The technique of Li and Nederlof is inherently randomized, and it uses the Cut & Count technique, which is also randomized. Designing matching deterministic algorithms for these problems, as well as for Feedback Vertex Set, is a long standing open problem. However, there is a deterministic algorithm for Pseudoforest Deletion running in time ${{{\mathcal {O}}}}^{\star }(3^k)$ [26]. So obtaining a deterministic algorithm for Pseudoforest Deletion running in time ${\mathcal {O}}^{\star }(c^k)$ for a constant $c<3$ is an interesting open question. Further, can we design an algorithm for Pseudoforest Deletion running in time ${\mathcal {O}}^{\star }(2.7^k)$, by designing a different Cut & Count based algorithm for this problem? Finally, could we get a ${{{\mathcal {O}}}}^{\star }(c^k 2^{o(\ell )})$ algorithm for Almost Forest Deletion, for a constant c possibly less than 3?