1 Preliminary
The Feedback Vertex Set problem (FVS for short), which asks to delete minimum number of vertices from a given graph to make it acyclic, is one of the 21 NPhard problems proved by Karp [10]
. It has important applications in biocomputing, operating system and artificial intelligence and so on. The problem has attracted a lot of attention from the parameterized complexity community due to its importance. Both its undirected and directed version have been well studied
[3, 4, 5, 7].Feedback vertex set problem has been proved to be fixed parameter tractable when parameterized with the solution size, that is, the number of vertices allowed to be deleted. For undirected feedback vertex set problem, the state of the art algorithm runs in time in deterministic setting [9] and in the randomized setting [11], here the notation hides polynomial factors in .
Several classes of graphs that are nearly acyclic have been defined in the litarature. A graph is called an pseudoforest if we can delete at most edges from each component in to get a forest. A pseudoforest is a 1pseudoforest. A graph is called an almost forest if we can delete edges from to get a forest.
As a generalization of feedback vertex set problem, Philip et al. [13] introduced the problem of deleting vertices to get a graph that is nearly a forest. Several results have been obtained in this line of research. In [13], the authors gave a algorithm for pseudoforest deletion, which asks to delete at most vertices to get an pseudoforest. The here depends on doubly exponentially. They also gave a time algorithm for the problem of pseudoforest deletion.
Rai and Saraub [14] gave a algorithm for the Almost Forest Deletion problem, which asks to delete minimum vertices to get an almost forest. Lin et al. [12] gave an improved algorithm for this problem that runs in time . Bodlaender et al. [1] gave an improved algorithm for pseudoforest deletion running in time .
A quasiforest is a graph in which each connected component admits a feedback vertex set of size at most . This notion was raised by Hols and Kratsch in [8] in which they show that the Vertex Cover problem admits a polynomial kernel when parameterized with distance to quasiforest. They did not show how to obtain such a modulator to quasiforest.
In this paper, we first give an algorithm for pseudoforest deletion that runs in time , improving the algorithm in [13]. We also give an FPT algorithm to obtain a minimum modulator to quasiforest. To the author’s acknowledgement, this is the first nontrivial FPT result for quasiforest deletion.
2 Notations and Terminology
Here we give a brief list of the graph theory concepts used in this paper, for other notations and terminology, we refer readers to [2].
For a graph , and are called its vertex set and edge set respectively. A nonempty graph is connected if there is a path between any pair of vertices, otherwise, we call it disconnected.
The multiplicity of an edge is the number of copies it appears in the multigraph. An edge is called a loop if . The degree of a vertex is the number of edges incident with it. A forest is a graph in which there is no cycle. A tree is a connected forest. A graph is a subgraph of a graph , if and . A subgraph of is called an induced subgraph of if for any , edge if and only if . We also denote by to indicate that is induced by the vertex set .
A pseudoforest is a graph in which each connected component can be made into a forest by deleting at most one edge. For a positive integer , an rpseudoforest is a graph in which each connected component can be made into a forest by deleting at most edges. A quasiforest is a graph in which each component admits a feedback vertex set of size at most .
3 Branching algorithm for pseudoforest deletion
Definition 1.
Given a graph , a subset is called an pseudoforest deletion set of if is an pseudoforest.
Here is an iterative version of the parameterized pseudoforest deletion problem.
pseudoforest Deletion
Instance: Graph with an pseudoforest deletion set , , integers and .
Parameter: and .
Output: Decide if there exists an pseudoforest deletion set of with ?
For a connected component in a graph , we call the quantity the excess of and denote it by . Note that for any connected component. Let be the set of components in . We define the excess of , denoted by , as i.e. the maximum excess among all components in . By definition, is an pseudoforest if and only if . For vertex subset , let be the number of components in .
We give the following observations about pseudoforest.
Observation 1: If is a subgraph of an pseudoforest, then is also an pseudoforest.
Observation 2: If is an pseudoforest, then each component in has at most edges.
By Observation 2, checking whether a given graph is an pseudoforest can be done in polynomial time.
Now we show how to solve the pseudoforest deletion via the approach of iterative compression. As a standard step, we introduce the following disjoint version of pseudoforest deletion.
Disjoint pseudoforest Deletion
Input: Graph with an pseudoforest deletion set , , integers and .
Parameter: and .
Output: Decide if there exists an pseudoforest deletion set of with and ?
To solve Disjoint pseudoforest Deletion, we apply the following reduction rules.
Reduction Rule 1: Let be an instance of Disjoint pseudoforest Deletion, if there exists a vertex such that , then return .
The correctness of Reduction Rule 1 is easy to prove.
Proof.
We show and are equivalent instances of Disjoint pseudoforest Deletion by proving that they have same solutions.
On the one hand, if is an pseudoforest deletion set of disjoint from , then is also an pseudoforest deletion set of . Indeed, if , then , otherwise, is a subgraph of , which is an pseudoforest graph. In both cases, is an pseudoforest graph.
On the other hand, let be an pseudoforest deletion set of disjoint from . Let be the component in containing . By definition of , is an pseudoforest in . Since , it follows that is also an pseudoforest in . Furthermore, and only differ at component . Thus, is an pseudoforest deletion set of disjoint from .
∎
Reduction Rule 2: If there exists such that is not an pseudoforest, then return .
It is obvious that any pseudoforest deletion set disjoint from must contain .
Reduction Rule 3: If there exists a vertex of degree two, such that at least one neighbor of is in , then delete and put a new edge between its two neighbors (even if they were already adjacent). If both incident edges of are to the same vertex, delete and put a new loop on the adjacent vertex (even if it has loop(s) already).
Now we prove the correctness of Rule 3.
Lemma 1.
Reduction Rule 3 is correct.
Proof.
Note that the operation decreases both the edge number and vertex number by 1.
On the one hand, let be a yesinstance of Disjoint pseudoforest Deletion, and let be an minimal pseudoforest deletion set of size at most , which is disjoint from . Let be the vertex of degree 2 being deleted from and be the resulting graph. Let be the two neighbors of in .
If , then by the minimality of , the neighbor of not in is not in . Without loss of generality, we may assume that and , then is an pseudoforest deletion set of . Thus if is a yes instance, then is also a yes instance.
If , then is an isolated vertex or in the component containing or in . can be obtained from by deleting or bypassing it, either way, is an pseudoforest.
On the other hand, let be a yes instance of Disjoint pseudoforest Deletion, and let be an minimal pseudoforest deletion set of size at most , which is disjoint from . If both are not in , then can be obtained from by subdividing edge and name the new vertex . If at least one of and is in , then has degree 0 or 1 in . In both cases, is also an pseudoforest. It follows that is also a solution for . ∎
Reduction Rule 4: If , then return no.
It is easy to see that Rules 14 can be applied in polynomial time. Given an instance of Disjoint pseudoforest Deletion, we first apply Rules 14 whenever possible.
Now we show how to handle the case when none of Rules 14 can be applied.
Define measure Note that initially as .
In order to get a depth bounded search tree, we prove that decreases after each application of the following branching rules.
BR1. Branching on a vertex with .
In one branch, we put into the solution and call the algorithm on . Note that in this branch, , (for each ) remain the same while decreases by 1. Hence drops by 1.
In the other branch, we put into and call the algorithm on . Let . There are the following two possible cases regarding the distribution of .
Case 1: belongs to more than one component in , thus . Let be the set of components in that are adjacent to .
To compute the difference between excess sums in and , denote
It follows that . In this case, drops by at least .
Case 2: All the neighbors of belong to one component, denoted by . Then , and as . Hence decrease by at least 1.
Therefore, in BR1, the measure drops by in one case, and at least or
in the other, while remaining nonnegative. In the worst case, it gives us branching vector
.Observe that after exhaustive applications of Rule 3 and BR1, every vertex in has degree at least 3. Moreover, if there exists a vertex such that , then . And so if holds for each , then , that is . Thus each must be in a cycle.
If is not an pseudoforest, there must be edges between and , as we know both and are pseudoforest. In the following, we branch on vertices in adjacent to .
BR2. Branching on a vertex adjacent to .
First let us consider the case when there is a component in such that there is only one edge between and , where and . Note that if the solution should intersect , then it suffices to contain . Thus we may branch on whether is in the solution or not. If is in the solution, then decreases and thus decreases by one. If is not in the solution, then we put into , which greatly decreases the value of , thus also decreases by at least one.
Now assume each component in has at least two edges to . Look at one shortest path in , such that both endvertices of are adjacent to some vertex in (we allow to be an isolated vertex). Note that such a shortest path can be found in polynomial time. We prove that . As any component in is an pseudoforest, . Note that each vertex in has degree at least 3 after exhaustive applications of Rule 3. And observe that no internal vertex of has an edge to , otherwise we find a path shorter than , a contradiction. Let be the component in containing , we know , and . As , so .
We branch on whether to delete any vertex on the path . Suppose . We consider branches. In branch where , we delete vertex on path , and call the algorithm on . In branch , we don’t delete any vertex on . Note that for branch , where , , (for any ) remain the same while decrease by at least 1. Thus drops by at least 1.
If is not an pseudoforest, then we ignore branch . Otherwise, for branch , we get a new instance , where . If edges between and are to the same component in , then , thus in this branch, decrease by 1. Otherwise, the edges between and are to different components in . In this case, decreases by 1 and , so drops by at least 1. This gives us the tuple branching vector in which .
According to the branching vectors in BR1 and BR2, the algorithm runs in time .
The following lemma states that a fast parameterized algorithm for the disjoint version problem gives a fast algorithm for the original problem.
Lemma 2.
[6] If there is an algorithm sloving Disjiont pseudoforest Deletion in time , then there is an algorithm solving pweudoforest Deletion in time .
So we get an algorithm for pseudoforest deletion with running time , which improves over the result in [13]. Our result answers the question raised in [1] on whether there is an algorithm for pseudoforest deletion runs in time .
Theorem 1.
There exists an algorithm for pseudoforest deletion with running time .
4 Kernelization of pseudoforest deletion
In this section, we give an improved kernel for the pseudoforest deletion problem. By exhaustively applying Reduction Rules 1 and 3, we will get an instance with minimum degree at least 3.
Lemma 3.
If a graph has minimum degree at least 3, maximum degree at most , and an pseudoforest deletion set of size at most , then it has at most vertices and at most edges.
Proof.
Let be an pseudoforest deletion set of of size at most . Let . It follows that each component in can be made into a forest by deleting at most edges. Suppose there are components in , we know that , since deleting any vertex of degree produces at most components. For each component with , we know there are at most edges. Thus, . By counting the number of edges incident with , we know that
It follows that . So . And .
∎
We need to make use of the following result.
Theorem 2 ([13]).
Given an instance of pseudoforest Deletion, in polynomial time, we can get an equivalent instance such that , and the maximum degree of is at most .
Theorem 3.
The pseudoforest deletion problem admits a kernel with vertices and edges.
Proof.
5 quasiforest deletion
Definition 2.
Given graph , a subset is called a quasiforest deletion set of if is a quasiforest.
Let us recall the definition of quasiforest deletion first.
quasiforest deletion
Instance: An undirected graph , an integer .
Parameter: .
Output: Decide if there exists a set with such that is a quasiforest.
Lemma 4.
A yes instance of quasiforest deletion has treewidth at most .
Proof.
Let be a yes instance of quasiforest deletion, then there is a set , such that each component in has feedback vertex set of size at most . Thus each component in has treewidth at most . By putting into each bag of the tree decomposition for each component in , we obtain a tree decomposition of , which has treewdith at most . It follows that has treewidth at most . ∎
We first point out that that the problem is FPT according to Courcelle’s theorem by expressing it with Monadic Second Logic. The basic idea of the expression is as follows: such that , . The definition of is as follows: , such that . The definition of is as follows: , such that and , , such that and and .
Theorem 4.
(Courcelle) Given a graph and a formula in Monadic Second Logic describing a property of interest, and parameterizing by the combination of and the size of the formula , it can be determined in time whether has the property of interest.
Theorem 5.
The quasiforest deletion problem is FPT parameterized with and .
Unfortunately, the algorithm implied by Courcelle’s Theorem may be several layers exponential. Aiming at fully exploiting the problem structure and design a faster algorithm, we solve the quasiforest deletion problem by the iterative compression approach. By Guessing the intersection of and , the problem is transformed into the following disjoint version.
Disjoint quasiforest deletion
Instance: An undirected graph , an integer and a vertex set with such that is a quasiforest.
Parameter: .
Output: Decide if there exists a set with such that is a quasiforest.
Denote , then is a quasiforest, that is, each connected component in admits feedback vertex set of size at most . Note that according to the algorithm in [9], we can check whether a given graph is a quasiforest in time .
Reduction Rule 1: If there is a vertex with degree at most one, then delete and return a new instance .
Reduction Rule 2: If there is a vertex with degree exactly two in , then delete and add an edge between the neighbors of .
After exhaustive applications of Reduction Rules 12, the resulting instance has minimum degree at least 3.
Reduction Rule 3: Observe that is a quasiforest, otherwise it is a noinstance. If there is any vertex such that is not a quasiforest, then delete and decrease by one.
Lemma 5.
Suppose is a yes instance of Disjoint quasiforest deletion, then for each vertex , there are at most components in that contains at least one cycle adjacent with .
Proof.
If there are more than components in , which are adjacent to , contains a cycle, then for any vertex set , such that , the component containing in is not a quasiforest. Thus is a no instance. It follows that for each vertex , the sum of the for the components in that are adjacent to is at most . ∎
By branching on minimum feedback vertex set of each such component in , i.e. either put the vertex into the solution or put it into , we may obtain a new instance in which every component in is a tree, moreover, the size of is upper bounded by .
The following lemma provides a bound on the number of trees in that has large neighborhood in .
Lemma 6.
Suppose is a yes instance of Disjoint quasiforest deletion, then there are at most components in that has at least neighbors in .
Proof.
Consider the measure , in which is the number of components in and is the maximum number of components in where is a minimum feedback vertex set of . Note that by putting a component that has at least neighbors in into , either decreases, or increases, or decreases. Indeed, if does not increase, then contains no vertex in , moreover, contains at most vertices, thus connects two components in , and so decreases. Since , of any yes instance contains at most trees that has at least neighbors in . ∎
Lemma 7.
Let be a yes instance of disjoint quasiforest deletion, then for each tree in that has at least neighbors in , we may partition it into less than subtrees, each has at most neighbors in , and keep the number of vertices in upper bounded.
Proof.
Let be a tree in that has more than neighbors in . Suppose on the contrary, we can only partition into at least maximal trees each has at most neighbors in , then there is a partition of into smaller trees each has at least neighbors in (just combining two adjacent subtrees), which is not possible, according to Lemma 6. By branching on the boundaries of the at most trees, We reduce the instance into bounded number of new instances, in which each tree has at most in . Moreover, has bounded size, as for each such tree, we put less than vertices into . ∎
Now we obtain an instance in which consists of only trees each has at most neighbors in , where . To obtain an FPT algorithm, we further reduce the number of trees in .
Definition 3.
Two trees in have same neighborhood type in if and for any vertex , has only one edge to if and only if has only one edge to .
Reduction Rule 4: For each neighborhood type , reduce the number of trees in that have neighborhood type in to .
Lemma 8.
Reduction Rule 4 is safe.
Proof.
Let be an instance of disjoint quasiforest deletion, such that there are trees with same neighborhood type in , which are . By deleting we get a new instance . Let be the common neighborhood of the trees in .
To prove the safety of Reduction Rule 4, we need to show that is a yes instance if and only if a yes instance.
On the one hand, it is easy to see that if is a yes instance then a yes instance as is a subgraph of .
On the other hand, suppose is a yes instance. Then there is a set such that and each component in admits a feedback vertex set of size at most . Note that at least of are disjoint from , and every two vertices in will be connected by each of these trees. It follows that contains at least vertex disjoint paths between every two vertices in . All vertices in are in the same connected component in , thus all except one vertex in will have to be in the feedback vertex set of .
Let be a feedback vertex set of with size at most . Note that are of same neighborhood type in , thus, for any vertex , if forms a cycle with , then it forms a cycle with , for any . Thus if is not empty, then does not form any cycle with the vertex in . And so is still a feedback vertex set of when we put back. It follows that is also a yes instance.
∎
For each , there are different neighborhood types with neighborhood , depending on whether the number of edges each vertex in has to the trees is just one.
According to Lemma 8, after exhaustive applications of Reduction Rule 4, there are at most trees of each neighborhood type.
When each tree in has at most neighbors in , there are at most different neighborhood types, and for each neighborhood type, Reduction Rule 4 can be applied in polynomial time.
Theorem 6.
(Gallai) Given a simple graph , a set , and an integer , one can in polynomial time either

find a family of pairwise vertexdisjoint paths, or

conclude that no such family exists and, moreover, find a set of at most vertices, such that in no connected component contains more than one vertex of .
Definition 4.
We called a vertex forced if for every solution , every feedback vertex set of size at most of the component containing in must contain .
Note that a vertex is a forced vertex if contains vertex disjoint paths between neighbors of . Thus we may set , and then for each vertex , let , check whether is a forced vertex via Gallai’s Theorem.
We already show that the number of trees in is upper bounded. We may now guess which trees are intersecting the solution, note that there are at most such trees. For each guess, we check whether it is compatible, i.e. does putting all the trees (that are guessed to be disjoint with the solution) into violate the requirement of quasiforest.
We guess how the components in are going to be connected in . For each compatible guess, we need to delete vertices from the trees, such that, the components are separated accordingly. That is, we need to delete vertices from the trees, such that, some components are not going to be connected.
There are bounded number of vertices in that are neighbors of . We can compute the size of minimum feedback vertex set for each component in . We may also guess for each vertex in the neighborhood of in , whether it is in the feedback vertex set or not.
We label each component with the size of its minimum feedback vertex set.
Lemma 9.
The problem reduces to bounded number of instances in which consists of at most trees, each has at most neighbors in , moreover, each tree contains at most vertices, where .
Proof.
Since contains at most trees, we know that contains at most vertices. For each vertex , we decide whether it is a forced vertex via Gallai’s Theorem. Thus we obtain a partition of , where contains all the forced vertices. According to Gallai’s Theorem, for each vertex , we can find a set with at most vertices, such that each component in contains at most one neighbor of . Thus, by branching on whether each vertex in is in the solution, we may partition each tree in into subtrees, which contains at most one neighbor of each vertex in .
We apply reduction rule 4 again to reduce the number of trees. And then we further reduce the instance by guessing how the trees are going to intersecting with the solution. Easy to know that, there are at most trees in the reduced instance, moreover, each tree in contains at most one neighbor of each vertex in .
Now we show how to bound the size of each tree. We guess how the component are going to be separated in where is a minimum quasiforest deletion set of . There are bounded number of such guesses. And then, we check whether the guessing can be realized. To simplify, we may regard all vertices in the same component from as one vertex. For two vertices that are guessed to be in different components, there are at most vertices in the trees that are adjacent to both and , since otherwise, deleting cannot separate and . Thus the total number of vertices that have neighbors in two guessed components must be upper bounded. Suppose we guessed there to be components, then at most pairs of vertices in the components. It follows that there are at most vertices in the trees that have neighbors in different guessed components.
And we also know that in each tree, the number of vertices that are adjacent to is upper bounded, since each tree contains at most one neighbor of each vertex in . Thus we only need to bound the number of vertices that are not adjacent to and only have neighbors in just one component. We bound this by arguing that there is no need to keep too many such vertices in the same tree, since such vertices only connecting vertices that are guessed to be in the same components, moreover, their neighbors in are forced to be in the feedback vertex sets, thus the number of such vertices does not affect the solution. In each tree, for each path connecting neighbors of and vertices with neighbors in more than one components, we just keep at one vertex that are adjacent to one component in (note that there are at most components).
Thus we obtain a bound on the size of each tree in , moreover, there are at most tree. Each tree in the reduced instance will have at most vertices. And so we can solve the reduced instance in fpt time by branching on the vertices in , which has bounded number of vertices.
∎
Theorem 7.
The quasiforest deletion problem can be solved in time
.
Proof.
We solve the Disjoint quasiforest deletion problem as a subroutine. It takes at most steps to make acyclic. And it takes at most steps to apply lemma 6. It take steps to exhaustively apply Reduction Rule 4. It takes at most guesses to get an instance in which there are at most trees in . For each instance, in which there are at most trees each has at most neighbors in , we can reduce it into bounded number of instances, where each tree has bounded size. And finally, we just need to solve instances in which contains at most trees, each has at most vertices. Thus it takes at most steps to solve each such instance via branching. According to the above analysis, the running time of our algorithm for Disjoint quasiforest deletion is at most . To solve quasiforest deletion, it suffices to solve copies of Disjoint quasiforest deletion, thus, we may solve quasiforest deletion in time . ∎
6 Conclusion
In this paper, we provide FPT results for two generalized versions of feedback vertex set problem. It would be interesting to know whether the problem of quasiforest deletion admits a polynomial kernel.
7 Acknowledgement
The research of Bin Sheng is supported by National Natural Science Foundation of China (No. 61802178).
References
 [1] Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A faster parameterized algorithm for pseudoforest deletion. Discrete Applied Mathematics, 236:42–56, 2018.
 [2] Béla Bollobás. Modern graph theory, volume 184. Springer Science & Business Media, 2013.
 [3] Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73(1):63–86, 2015.
 [4] Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188–1198, 2008.
 [5] Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed subset feedback vertex set is fixedparameter tractable. ACM Trans. Algorithms, 11(4):28:1–28:28, 2015.
 [6] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
 [7] Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Subset feedback vertex set is fixedparameter tractable. SIAM J. Discrete Math., 27(1):290–309, 2013.
 [8] EvaMaria C. Hols and Stefan Kratsch. Smaller parameters for vertex cover kernelization. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 68, 2017, Vienna, Austria, pages 20:1–20:12, 2017.
 [9] Yoichi Iwata and Yusuke Kobayashi. Improved analysis of highestdegree branching for feedback vertex set. In 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 1113, 2019, Munich, Germany, pages 22:1–22:11, 2019.
 [10] Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 2022, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pages 85–103, 1972.
 [11] Jason Li and Jesper Nederlof. Detecting feedback vertex sets of size in O time. CoRR, abs/1906.12298, 2019.
 [12] Mugang Lin, Qilong Feng, Jianxin Wang, Jianer Chen, Bin Fu, and Wenjun Li. An improved FPT algorithm for almost forest deletion problem. Inf. Process. Lett., 136:30–36, 2018.
 [13] Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Generalized pseudoforest deletion: Algorithms and uniform kernel. SIAM J. Discrete Math., 32(2):882–901, 2018.
 [14] Ashutosh Rai and Saket Saurabh. Bivariate complexity analysis of almost forest deletion. Theor. Comput. Sci., 708:18–33, 2018.
Comments
There are no comments yet.