1 Introduction
The Directed Feedback Vertex Set (DFVS) problem is that of finding a smallest vertex set in a given digraph such that is a directed acyclic graph. This problem is among the most classical problems in algorithmic graph theory. It is one of the 21 complete problems on Karp’s famous list [13].
Consequently, the DFVS problem has long attracted researchers in approximation algorithms. The current best known approximation factor that can be achieved in polynomial time for vertex digraphs with optimal fractional solution value is due to Seymour [18], Even et al. [7] and Even et al. [8]. On the negative side, Karp’s hardness reduction shows the problem to be hard, which rules out the existence of a polynomialtime approximation scheme (PTAS) assuming . Assuming the Unique Games Conjecture, the DFVS problem does not admit a polynomialtime approximation [12, 11, 19].
The DFVS problem has also received a significant amount of attention from the perspective of parameterized complexity. The main parameter of interest there is the optimal solution size . The problem can easily be solved in time by enumerating all sized vertex subsets and then seeking a topological order of . The interesting question is thus whether the DFVS problem is fixedparameter tractable with respect to , which is to devise an algorithm with run time for some computable function depending only on . It was a longstanding open problem whether DFVS admits such an algorithm. The question was finally resolved by Chen et al. who gave a time algorithm for graphs with vertices and arcs. Recently, an algorithm for DFVS with run time was given by Lokshtanov et al. [15]. It is wellknown that the arc deletion variant is parameterequivalent to the vertex deletion variant and hence Directed Feedback Arc Set (DFAS) can also be solved in time .
Once the breakthrough result for DFVS was obtained, the natural question arose how much further one can push the boundary of (fixedparameter) tractability. On the one hand, Chitnis et al. [5] showed that the generalization of DFVS where one only wishes to hit cycles going through a specified subset of nodes of a given digraph is still fixedparameter tractable when parameterized by solution size. On the other hand, Lokshtanov et al. [16] showed that finding a smallest set of vertices of hitting only the odd directed cycles of a given digraph is hard, and hence not fixedparameter tractable unless .
Our contributions. For another generalization the parameterized complexity is still open: In the Eulerian Strong Component Arc (Vertex) Deletion problem, one is given a directed multigraph , and asks for a set of at most vertices such that every strong component of is Eulerian, that is, every vertex has the same indegree and outdegree within its strong component. The arc version of this problem was suggested by Cechlárová and Schlotter [2] in the context of housing markets. Marx [17] explicitly posed determining the parameterized complexity of Eulerian Strong Component Vertex Deletion as an open problem. Notice that these problems generalize the DFAS/DFVS problems, where each strong component of has size one and thus is Eulerian.
Theorem 1.
Eulerian Strong Component Vertex Deletion is hard and hard parameterized by solution size , even for strong digraphs.
Alas, we are unable to determine the parameterized complexity of Eulerian Strong Component Arc Deletion, which appears to be more challenging. Hence, we consider two natural generalizations of DFAS which may help to gain better insight into the parameterized complexity of that problem.
First, we consider the problem of deleting a set of arcs or vertices from a given digraph such that every strong component has size at most . Thus, the DFAS/DFVS problems corresponds to the special case when . Formally, the problem Bounded Size Strong Component Arc (Vertex) Deletion takes as input a multidigraph and integers , and seeks a set of at most arcs or vertices such that every strong component of has size at most .
The undirected case of Bounded Size Strong Component Vertex (Arc) Deletion was studied recently. There, one wishes to delete at most vertices of an undirected vertex graph such that each connected component of the remaining graph has size at most . For being constant, Kumar and Lokshtanov [14] obtained a kernel of size that can be computed in time; note that the degree of the run time in the input size depends on and is thus not a fixedparameter algorithm. For general , there is a sized kernel computable in time by Xiao [20]. The directed case—which we consider here—generalizes the undirected case by replacing each edge by arcs in both directions.
Our main result here is to solve the directed case of the problem by a fixedparameter algorithm:
Theorem 2.
There is an algorithm that solves Bounded Size Strong Component Arc (Vertex) Deletion in time for vertex multidigraphs and integers .
In particular, our algorithm exhibits the same asymptotic dependence on as does the algorithm by Chen et al. [3] for the DFVS/DFAS problem, which corresponds to the special case .
Another motivation for this problem comes from the linkage problem, which asks for pairs of terminal vertices in a digraph if they can be connected by mutually arcdisjoint paths. The linkage problem is complete already for [9]. Recently, BangJensen and Larsen [1] solved the linkage problem in digraphs where strong components have size at most . Thus, finding induced subgraphs with strong components of size at most can be of interest in computing linkages.
Our second problem is that of deleting a set of arcs or vertices from a given digraph such that each remaining strong component is outregular, meaning that every vertex has outdegree exactly in its strong component , for . So in particular, every strong component is Eulerian, as in the Eulerian Strong Component Arc Deletion problem. Observe that in the DFAS/DFVS problem we delete arcs or vertices from a given directed graph such that each remaining strong component is 0outregular (trivial). Formally, we consider the 1OutRegular Arc (Vertex) Deletion problem in which for a given multidigraph and integer , we seek a set of at most arcs (vertices) such that every component of is outregular with . Note that this problem is equivalent to deleting a set of at most arcs (vertices) such that every nontrivial (consisting of more than one vertex) strong component of is an induced directed cycle. In contrast to Eulerian Strong Component Vertex Deletion, the 1OutRegular Arc (Vertex) Deletion problem is monotone, in that every superset of a solution is again a solution: if we delete an additional arc or vertex that breaks a strong component that is an induced cycle into several strong components, then each of these newly created strong components is trivial.
Our result for this problem reads as follows:
Theorem 3.
There is an algorithm solving 1OutRegular Arc (Vertex) Deletion in time for vertex digraphs and parameter .
Notice that for Bounded Size Strong Component Arc (Vertex) Deletion and 1OutRegular Arc (Vertex) Deletion, there are infinitely many instances for which solutions are arbitrarily smaller than those for DFAS (DFVS), and for any instance they are never larger. Therefore, our algorithms strictly generalize the one by Chen et al. [3] for DFAS (DFVS). As a possible next step towards resolving the parameterized complexity of Eulerian Strong Component Arc Deletion, one may generalize our algorithm for 1OutRegular Arc Deletion to OutRegular Arc Deletion for arbitrary .
We give algorithms for vertex deletion variants only, and then reduce the arc deletion variants to them.
2 Notions and Notations
We consider finite directed graphs (or digraphs) with vertex set and arc set . We allow multiple arcs and arcs in both directions between the same pairs of vertices. For each vertex , its outdegree in is the number of arcs of the form for some , and its indegree in is the number of arcs of the form for some . A vertex is balanced if . A digraph is balanced if every vertex is balanced.
For each subset , the subgraph induced by is the graph with vertex set and arc set . For any set of arcs or vertices of , let denote the subgraph of obtained by deleting the elements of from . For subgraphs of and vertex sets let denote the set of vertices that are reachable from in , i.e. vertices to which there is a path from some vertex in . For an walk and a walk we denote by the concatenation of these paths, i.e. the walk resulting from first traversing and then .
Let be a digraph. Then is outregular if every vertex has outdegree exactly . Further, is called strong if either consists of a single vertex (then is called trivial), or for any distinct there is a directed path from to . A strong component of is an inclusionmaximal strong induced subgraph of . Also, is strong for some if for any with , is strong. We say that is weakly connected if its underlying undirected graph is connected. Finally, is Eulerian if there is a closed walk in using each arc exactly once.
Definition 1.
For disjoint nonempty vertex sets of a digraph , an arc or vertex set is an separator if is disjoint from and there is no path from to in .
An separator is minimal if no proper subset of is an separator. An separator is important if there is no separator with and .
Proposition 1 ([4]).
Let be a digraph and let be disjoint nonempty vertex sets. For every there are at most important separators of size at most , all of which can be enumerated in time .
3 Tools for Generalized DFVS/DFAS Problems
Iterative Compression. We use the standard technique of iterative compression. For this, we label the vertices of the input digraph arbitrarily by , and set . We start with and the solution . As long as , we can set and continue. As soon as , the set is a solution for of size . The compression variant of our problem then takes as input a digraph and a solution of size , and seeks a solution of size at most for or decides that none exists.
We call an algorithm for the compression variant on to obtain a solution or find out that does not have a solution of size , but then neither has . By at most calls to this algorithm we can deduce a solution for the original instance .
Disjoint solution. Given an input to the compression variant, the next step is to ask for a solution for of size at most that is disjoint from the given solution of size . This assumption can be made by guessing the intersection , and deleting those vertices from . Since has elements, this step creates candidates . The disjoint compression variant of our problem then takes as input a graph , a solution of size , and seeks a solution of size at most disjoint from .
Covering the shadow of a solution. The “shadow” of a solution is the set of those vertices that are disconnected from (in either direction) after the removal of . A common idea of several fixedparameter algorithms on digraphs is to first ensure that there is a solution whose shadow is empty, as finding such a shadowless solution can be a significantly easier task. A generic framework by Chitnis et al. [5] shows that for special types of problems as defined below, one can invoke the random sampling of important separators technique and obtain a set which is disjoint from a minimum solution and covers its shadow, i.e. the shadow is contained in . What one does with this set, however, is problemspecific. Typically, given such a set, one can use (some problemspecific variant of) the “torso operation” to find an equivalent instance that has a shadowless solution. Therefore, one can focus on the simpler task of finding a shadowless solution or more precisely, finding any solution under the guarantee that a shadowless solution exists.
Definition 2 (shadow).
Let be a digraph and let . A vertex is in the forward shadow of (with respect to ) if is a separator in , and is in the reverse shadow of (with respect to ) if is a separator in .
A vertex is in the shadow of if it is in the forward or reverse shadow of .
Note that itself is not in the shadow of by definition of separators.
Definition 3 (connected and transversal).
Let be a digraph, let and let be a set of subgraphs of . We say that is connected if for every , each vertex of can reach some and is reachable by some (maybe different) vertex of by a walk completely contained in . For a set of subgraphs of , an transversal is a set of vertices that intersects the vertex set of every subgraph in .
Chitnis et al. [5] show how to deterministically cover the shadow of transversals:
Proposition 2 (deterministic covering of the shadow, [5]).
Let . In time one can construct sets such that for any set of subgraphs which is connected, if there exists an transversal of size at most then there is an transversal of size at most that is disjoint from and such that covers the shadow of , for some .
4 Hardness of Vertex Deletion
In this section we prove Theorem 1, by showing hardness and hardness of the Eulerian Strong Components Vertex Deletion problem. Before the hardness proof we recall an equivalent characterization of Eulerian digraphs:
Lemma 1 (folklore).
Let be a weakly connected digraph. Then is Eulerian if and only if is balanced.
We can now state the hardness reduction, which relies on the hardness of the following problem introduced by Cygan et al. [6]. In Directed Balanced Vertex Deletion, one is given a directed multigraph and an integer , and seeks a set of at most vertices such that is balanced.
Proposition 3 ([6]).
Directed Balanced Vertex Deletion is hard and hard with parameter .
We will prove the hardness of Eulerian Strong Component Vertex Deletion for strong digraphs by adding vertices ensuring this connectivity.
See 1
Proof.
We give a polynomial reduction from Directed Balanced Vertex Deletion. Let an instance of Directed Balanced Vertex Deletion. Let arise from by adding vertices and arcs for all and all . This construction obviously can be made to run in polynomial time. Moreover, is strong as one needs to delete at least all to disconnect two vertices. All we have to show is that has a solution as instance of Directed Balanced Vertex Deletion if and only if has a solution as instance of Eulerian Strong Component Vertex Deletion.
Let be a solution to as instance of Eulerian Strong Components Vertex Deletion. As is strong, is strong. Moreover is a solution, so is Eulerian (because it is the only strong component). Therefore, by Lemma 1 every vertex of is balanced. Deleting the remaining vertices of does not harm the balance of the remaining vertices, as for each and we delete one outgoing and one incoming arc of . Thus is balanced. Hence, is a solution to as instance of Directed Balanced Vertex Deletion.
Let be a solution to as instance of Directed Balanced Vertex Deletion. Then is balanced and by construction as well. Furthermore, is strong, and thus by Lemma 1 also Eulerian. Hence, the only strong component of is Eulerian and therefore is a solution to as instance of Eulerian Strong Component Vertex Deletion. ∎
5 Bounded Size Strong Component Arc (Vertex) Deletion
In this section we show a fixedparameter algorithm for the vertex deletion variant of Bounded Size Strong Component Vertex Deletion.
We give an algorithm that, given an vertex digraph and integers , decides in time if has a set of at most vertices such that every strong component of has size at most . Such a set will be called a solution of the instance .
The algorithm first executes the general steps “Iterative Compression” and “Disjoint Solution”; it continues with a reduction to a skew separator problem.
Reduction to Skew Separator Problem Now the goal is, given a digraph , integers , and a solution of , to decide if has a solution that is disjoint from . We solve this problem—which we call Disjoint Bounded Size Strong Component Vertex Deletion Reduction—by reducing it to finding a small “skew separator” in one of a bounded number of reduced instances.
Definition 4.
Let be a digraph, and let be two ordered collections of vertex subsets of . A skew separator for is a vertex subset of such that for any index pair with , there is no path from to in the graph .
This definition gives rise to the Skew Separator problem, which for a digraph , ordered collections of vertex subsets of , and an integer , asks for a skew separator for of size at most . Chen et al. [3] showed:
Proposition 4 ([3, Thm. 3.5]).
There is an algorithm solving Skew Separator in time for vertex digraphs .
The reduction from Disjoint Bounded Size Strong Component Vertex Deletion Reduction to Skew Separator is as follows. As is a solution of , we can assume that every strong component of has size at most . Similarly, we can assume that every strong component of has size at most , as otherwise there is no solution of that is disjoint from . Let be a labeling of the vertices in .
Lemma 2.
There is an algorithm that, given an vertex digraph , integers , and a solution of , in time computes a collection of at most vectors of length , where for , such that for some solution of disjoint from , there is a vector such that the strong component of containing is exactly for .
Proof.
Fix a hypothetical solution of that is disjoint from . The algorithm computes, for each vertex , a set of at most vertices such that induces a strong component of . (These sets must exist as is required to be disjoint from .) Notice that the definition of must only depend on but not on . Vertices in (other than ) may or may not belong to and in particular it can be that for some . Thus, for distinct , sets and possibly overlap.
Intuitively, to compute define a “candidate vertex for ” as a vertex that can potentially belong to the same strong component of as , for a hypothetical solution of size at most that is disjoint from . We want to bound the number of candidate vertices for each , or, more precisely, the number of “candidate sets” for which can be exactly the vertex set of the strong component that contains , after deleting a set of at most vertices from .
Formally, the algorithm constructs sets iteratively by a simple branching algorithm along the following lines. It starts with an initial set and a guessed set . For , suppose that it has already constructed a set that must be a subset of , and we want to either extend to a proper superset or decide that . If there is a path in of length at least two and length at most whose both end vertices are in and whose internal vertices are all outside , then it branches into two cases:

either some vertex of belongs to the deletion set (meaning that we add to ),

or the entire path belongs to the candidate set (meaning that we add the set of all internal vertices of to ).
Thus, in each branching step, either the size of strictly increases, or the size of strictly increases. Note that the size of is bounded by , and the size of is bounded by . Hence, in the first branch, adding to implies that the budget strictly decreases to , whereas in the second branch, adding to strictly decreases the budget to . We repeat this branching until the size of reaches the limit of or the size of reaches the limit of , or if there are no paths left of length at most with both end vertices inside and all internal vertices outside . At this point, the set will not be further extended, and is a candidate set for . This completes the algorithm description.
We analyze the run time of the algorithm. To construct all possible vectors, the search tree that arises from the branching has a number of leaves that is bounded by a function of and only, where is the sum of the remaining capacities of the ’s. By the above branching, this function satisfies the recursion , as in the first branch there are at most choices for vertex each of which reduces the budget of by 1, and one branch which reduces the budget of by the number of internal vertices of which is at least .
To obtain an upper bound on the growth of , we first notice that for all and for all . We then claim that , since by induction for it holds
where in the last inequality we used that and . Hence, the search tree has at most leaves, each leaf corresponding to some vector . The initial capacity satisfies , and thus . Since each branching step can be executed in polynomial time, the search tree (and hence the set ) can be constructed in time . Thus, the overall run time is . ∎
Observe that for each vertex each set contains at most vertices, and together with the run time of the algorithm in Lemma 2 directly implies that contains at most vectors.
Armed with Lemma 2, we can hence restrict our search for a solution of disjoint from to those that additionally are “compatible” with a vector in . Formally, a solution of is compatible with a vector if the strong component of containing is exactly for . For a given vector , to determine whether a solution of disjoint from and compatible with exists, we create several instances of the Skew Separator problem. To this end, note that if two sets for distinct overlap, then actually (and ). So for each set we choose exactly one (arbitrary) representative vertex among all vertices in with consistent choice over overlapping (and thus equal) ’s. Let be the set of these representative vertices. Now we generate precisely one instance of Skew Separator for each permutation of . The graph is the same in all these instances, and is obtained from by replacing each unique set by two vertices (where is the representative of ), and connecting all vertices incoming to in by an inarc to and all vertices outgoing from in by an arc outgoing from . This way also arcs of the type are added but none of type , or . Notice that this operation is welldefined and yields a simple digraph , even if for some distinct . The sets and of “sources” and “sinks” depend on the permutation with elements : let and let .
Thus, per triple we generate at most instances , the number of permutations of .
We now establish the correctness of this reduction, in the next two lemmas:
Lemma 3.
If an instance admits a solution disjoint from , compatible with and for which is a topological order of the connected components of , then forms a skew separator of size for .
Proof.
Suppose, for the sake of contradiction, that the claim is false. Then one of the two following cases must hold:

For two vertices with , there would be a path from to in . This corresponds to a path in . Either there is also a path in meaning that in contradiction to our choice of or the topological order of strong components was incorrect (as must be before )

The invertex of the strong component containing would be reachable from the outvertex of this strong component in the graph , because then the component would contain all the vertices on this path from to , and by the way we constructed , the size of in would be at least , contradicting that the strong component of containing has at most vertices. ∎
Lemma 4.
Conversely, if is a skew separator of with size at most , then is a solution of disjoint from and compatible with .
Proof.
Suppose, for the sake of contradiction, that is not a solution for . Then there is some strong component in of size more than . By abuse of notation let . Since neither (by choice of ) nor (as subdigraph of ) contain strong components of size more than , this component must contain vertices from both and . Let be a closed walk of that intersects both and . Such a closed walk must exist by being strong.
We consider two cases:

The closed walk intersects a single unique component . Then all other vertices of are in . Let be the representative of . As intersects , leaves and enters at least once. This means that there is a walk in that starts with the vertex and ends with the vertex , and all internal vertices of (of which there is at least one) are outside . But this contradicts the assumption that is a skew separator for the tuple that should cut all walks from to .

The closed walk intersects several different components . Let be the order of components that we encounter when traversing along the walk , starting from an arbitrary component , where . Let be the corresponding representative vertices. Then there must be an index such that occurs after in . Hence in is no path from to . Now consider the subpath of that starts from the component and ends at component and has its interior disjoint from both. Since all internal vertices on (by definition of ) are not in any , all such internal vertices of must be from , and the path corresponds to a path in the graph that starts from vertex and ends at vertex . Again, this contradicts the assumption that is a skew separator for .
Thus, the skew separator for is a solution for . ∎
In summary, we have reduced a single instance to the compression problem Disjoint Bounded Size Strong Component Vertex Deletion Reduction to at most instances of the Skew Separator problem, where each such instance corresponds to a permutation of . The reduction just described implies that:
Lemma 5.
An input to the Disjoint Bounded Size Strong Component Vertex Deletion problem is a “yes”instance if and only if at least one of the instances is a “yes”instance for the Skew Separator problem.
So we invoke the algorithm of Proposition 4 for each of the instances. If at least one of them is a “yes”instance then is a “yes”instance, otherwise is a “no”instance. Hence, we conclude that Disjoint Bounded Size Strong Component Vertex Deletion Reduction is fixedparameter tractable with respect to the joint parameter , and so is Bounded Size Strong Component Vertex Deletion. The overall run time of the algorithm is thus bounded by . This completes the proof of Theorem 2.
6 1OutRegular Arc (Vertex) Deletion
In this section we give a fixedparameter algorithm for the vertex deletion variant of Theorem 3. Let be a digraph and let . A solution for is a set of at most vertices of such that every nontrivial strong component of is 1outregular.
We first apply the steps “Iterative Compression” and “Disjoint Solution” from Sect. 3. This yields the Disjoint 1OutRegular Vertex Deletion Reduction problem, where we seek a solution of that is disjoint from and smaller than a solution of .
Then we continue with the technique of covering of shadows, as described in Sect. 3. In our setting, let be the collection of vertex sets of that induce a strong graph different from a simple directed cycle. Then clearly is connected and any solution must intersect every such induced subgraph.
So we can use Proposition 2 on to construct sets with such that one of these sets covers the shadow of our hypothetical solution with respect to . For each we construct an instance, where we assume that covers the shadow. Note that a vertex of is never in the shadow. As we assume that is disjoint from a solution, we reject an instance if contains a member of as a subgraph.
Observation 1.
has no subgraph in .
Normally, one would give a “torso” operation which transforms with the use of into an instance of the same problem which has a shadowless solution if and only if the original instance has any solution. Instead, our torso operation reduces to a similar problem while maintaining solution equivalence.
Reducing the Instance by the Torso Operation. Our torso operation works directly on the graph. It reduces the original instance to one of a new problem called Disjoint Shadowless Good 1OutRegular Vertex Deletion Reduction; afterwards we show the solution equivalence.
Definition 5.
Let be an instance of Disjoint 1OutRegular Vertex Deletion Reduction and let . Then defines the digraph with vertex set and good and bad arcs. An arc for is introduced whenever there is an path in (of length at least 1) whose internal vertices are all in . We mark as good if this path is unique and there is no cycle in with . Otherwise, we mark it as a bad arc.
Note that every arc between vertices not in also forms a path as above. Therefore is a subdigraph of . Also, may contain selfloops at vertices from cycles with only the vertex outside of . In , we call a cycle good if it consists of only good arcs. (A nongood cycle in can contain both good arcs and bad arcs.)
Now we want to compute a vertex set of size whose deletion from yields a digraph whose every nontrivial strong component is a cycle of good arcs. We call this problem Disjoint Shadowless Good 1OutRegular Vertex Deletion Reduction. To simplify notation we construct a set which contains all strong subdigraphs of that are not trivial or good cycles. Then is a solution to if and only if contains no subdigraph in . In the next lemma we verify that our new problem is indeed equivalent to the original problem, assuming that there is a solution disjoint from .
Lemma 6 (torso preserves obstructions).
Let be a digraph, as above and . For any it holds that contains a subdigraph in if and only if contains a subdigraph in .
Proof.
In the forward direction, if contains a subgraph , we can replace the arcs of as follows: All good arcs are replaced by their unique path in the torso operation. For a bad arc we insert all paths whose internal vertices completely belong to . If there is only a single such path then by definition there is a cycle in that intersects . We also insert all cycles of this type. Call the resulting graph .
This digraph is a subdigraph of and is strong, as was strong and all added vertices have a path from and to . Now, either was not a cycle, then is also not a cycle or it contained a bad arc and we have inserted at least two parallel paths or a cycle. In any case, we have .
In the backward direction, let have a subdigraph . Assume for contradiction that has no subdigraph in . We will show that . Note that the torso operation preserves subdigraph relations and connection. By Observation 1 we know that there is a . Furthermore, we know that there is also a as is a solution to . From by definition we know that and hence in . As is strong, there is a closed walk through and in .
Claim 1.
is a cycle.
Proof of Claim 1.
Suppose, for sake of contradiction, that is not a cycle. Let a vertex that is visited at least twice when traversing . Let be the first traversal and be the second one. Without loss of generality, we can assume that by replacing them by the next vertex outside of . If then the arcs all exist in the strong subdigraph . Therefore, in contradiction to the fact that is a subdigraph of . Else, arcs would exist, giving the same contradiction. This completes the proof of the claim. ∎
Now is strong and not a cycle, and therefore has to contain a (possibly closed) path with the following properties:

,

contains no arc from ,

all internal vertices of are disjoint of .
Then there are paths and in such that their endpoints are not in but all their interior vertices and furthermore respectively . If (resp. ), set (resp. .
If contains some interior vertex , the path is in and shrinks to a path in . As we get that has at least two outarcs in and therefore , a contradiction. Thus, the interior of lies in . Furthermore, if then , is a path in . Note that as is a cycle and . Therefore the path is shrunk by the torso operation to the arc . But then has two outgoing arcs in and as is still strong, . Therefore, we have and also as otherwise the arc would be bad (because there are two different paths). If lies before on the path is a path in . As the interior of and is in this would give a second path, making
Comments
There are no comments yet.