A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs

Ghorbani, Ebrahim; Mnich, Matthias

doi:10.4230/LIPIcs.ICALP.2026.96

A $\nicefrac{{9}}{{4}}$ -Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs

Ebrahim Ghorbani

Hamburg University of Technology, Institute for Algorithms and Complexity, Germany Matthias Mnich

Hamburg University of Technology, Institute for Algorithms and Complexity, Germany

Abstract

We provide the first non-trivial approximation algorithm for the fundamental directed feedback vertex set (DFVS) problem in the class of quasi-transitive digraphs. This class of digraphs encompasses both dense and sparse classes of digraphs, for which specialized DFVS algorithms were proposed in the literature, like tournaments or transitive orientations of bounded treewidth graphs.

Our approximation algorithm can handle both dense graphs, as well as sparse graphs, by a single approach, which is based on carefully analysing the solutions to a linear programming relaxation of DFVS. It also handles the node-weighted DFVS problem, for which it computes a 9/4-approximation in polynomial time.

Along the way, we improve and simplify the best-known deterministic polynomial-time approximation algorithms for DFVS in tournaments (Cai et al., SICOMP 2001; Mnich et al., ESA 2016).

Keywords and phrases:

directed feedback vertex set, tournaments, quasi-transitive digraphs

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

DOI:

10.4230/LIPIcs.ICALP.2026.96

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Directed Feedback Vertex Set (DFVS) problem is one of the most intensely studied $\mathsf{NP}$ -hard problems: for a given directed graph (digraph) $D$ , it aims to find a minimum-sized subset $F$ of nodes whose removal from $D$ yields an acyclic digraph. It is one of the 21 $\mathsf{NP}$ -complete problems whose hardness was established by Karp in his seminal paper [16]. This intractability result motivates the design of polynomial-time approximation algorithms for it. To date, the best-known approximation algorithms yield $O(\log n\log\log n)$ -approximations, and are due to Seymour [23], and to Even et al. [11]. This leaves quite some gap to the best-known inapproximability result: assuming the Unique Games Conjecture, the DFVS problem does not admit a constant-factor approximation in polynomial time [15]. This contrasts with the Feedback Vertex Set problem on undirected graphs, for which a factor-2 approximation has long been known [2, 6].

Also in contrast to the Feedback Vertex Set problem on undirected graphs, only limited investigations into the complexity and approximability of the DFVS problem on classes of directed graphs have been done. A possible reason is that the DFVS problem on directed graphs appears to behave rather differently than on undirected graphs. For DFVS on sparse digraphs, we are only aware of an exact polynomial-time algorithm on digraphs whose underlying undirected graph has bounded treewidth [8], and a $\nicefrac{{12}}{{5}}$ -approximation on planar digraphs¹¹1Goemans and Williamson [12] claim an approximation factor of $\nicefrac{{9}}{{4}}$ , but Berman and Yaroslavtsev [7] point out an error in their analysis, and argue that it is only an $\nicefrac{{18}}{{7}}$ -approximation..

On dense digraphs, the DFVS problem is often studied in its more general, node-weighted version, where the input digraph $D$ is equipped with a node-weight function $w:V(D)\rightarrow\mathbb{Q}_{\geq 0}$ , and the goal is to compute a minimum-weight DFVS, where the weight of the DFVS equals the sum of the weights of the nodes which it contains. A well-known class of dense digraphs for which several approximation algorithms for node-weighted DFVS have been devised are tournaments, which are orientations of complete undirected graphs. For tournaments, obtaining a 3-approximation for DFVS is easy, as DFVS on tournaments is a particular case of the 3-Hitting Set problem. 3-Hitting Set admits a simple 3-approximation, whereas obtaining a $(3-\varepsilon)$ -approximation is hard under the Unique Games Conjecture [17], for any $\varepsilon>0$ . But for DFVS on tournaments, this factor 3 was improved to a $\nicefrac{{5}}{{2}}$ -approximation, by Cai et al. [9]. They greedily include all nodes from $\mathcal{T}_{5}$ -subtournaments, which are 5-node tournaments $T$ which every DFVS of $T$ must intersect in at least two nodes. Then they meticulously analysed the structure of $\mathcal{T}_{5}$ -free tournaments, for which they obtained an exact min-max relation between directed cycle covering and directed cycle packing; there, they solve the DFVS problem via linear programming (LP) covering-packing duality. It took more than 15 years before the $\nicefrac{{5}}{{2}}$ -approximation was improved to a $\nicefrac{{7}}{{3}}$ -approximation, by Mnich et al. [21]. They considered the family $\mathcal{T}_{7}$ of 7-node tournaments $T$ which every DFVS of $T$ must intersect in at least three nodes. Whereas $\mathcal{T}_{5}$ contains 5 tournaments, $\mathcal{T}_{7}$ contains 121 tournaments, so they handled $\mathcal{T}_{7}$ -free tournaments by a complex layering algorithm. Aprile et al. [1] later gave another, slightly faster $\nicefrac{{7}}{{3}}$ -approximation. Finally, Lokshtanov et al. [18] devised the first 2-approximation algorithm for DFVS on tournaments. It is a randomized branching algorithm; its derandomization however leads to a quasi-polynomial run-time. It was extended to a randomized $(2\alpha)$ -approximation algorithm for digraphs with independence number $\alpha$ [14]. Beyond DFVS on tournaments, there is only a limited understanding which (other) classes of 3-Hitting Set instances admit a $(3-\varepsilon)$ -approximation, for some $\varepsilon>0$ .

1.1 Our contributions

Our main focus is the node-weighted DFVS problem in a wide generalization of tournaments. A digraph is quasi-transitive if for every node there is complete adjacency between its in-neighbors and out-neighbors. Quasi-transitive digraphs are of particular interest due to their close connection with comparability graphs. In fact, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph [5]. Clearly, every tournament is a quasi-transitive digraph. Quasi-transitive digraphs are extensively studied; the standard textbook on digraphs by Bang-Jensen and Gutin contains an entire chapter on quasi-transitive digraphs [3, Ch. 8]. Quasi-transitive digraphs can have underlying undirected graphs which neither have bounded treewidth, nor have bounded independent set size; see Figure 1 for an example. In particular, they can be very dense (such as tournaments or semi-complete digraphs), or very sparse (certain orientations of paths). The parameterized complexity of DFVS on quasi-transitive digraphs was studied by Bang-Jensen et al. [4]; however, no non-trivial approximation algorithms seem to be known for it.

We argue that the DFVS problem on quasi-transitive digraphs can be cast as a special case of 3-Hitting Set; thus, we readily obtain a 3-approximation. Our main result is the first non-trivial approximation algorithm for the problem:

Theorem 1.

The node-weighted DFVS problem on quasi-transitive digraphs admits a deterministic $\nicefrac{{9}}{{4}}$ -approximation in polynomial time.

Figure 1: The underlying undirected graphs of quasi-transitive digraphs can have both unbounded tree-width and unbounded independence number: In this grid, replace each node by an arbitrary tournament and every arc by a complete set of arcs between the corresponding tournaments, all oriented in the same direction as the original arc.

Theorem 1 directly improves the approximation factor over the previously best deterministic $\nicefrac{{7}}{{3}}$ -approximation algorithm for node-weighted DFVS on the narrower class of tournaments.

Our focus is not only in generalization, and giving quantitative improvements: importantly, our approach also considerably simplifies previous arguments. For instance, we give a short direct proof of the min-max relation in $\mathcal{T}_{5}$ -free tournaments, drastically shortcutting the 10-page analysis by Cai et al. [9]. Also, whereas the $\nicefrac{{7}}{{3}}$ -approximation by Aprile et al. [1] simplifies the one by Mnich et al. [21], for $\mathcal{T}_{7}$ -free tournaments it requires a layering algorithm which is non-trivial to analyze; we instead do not need such algorithm at all. We detail our insights, which yield this simplification and generalization, in the next paragraph.

1.2 Our methodology

We define the set ${\cal T}_{9}$ as the family of $9$ -node tournaments with minimum DFVS size at least $4$ . The algorithm consists of two stages. In the first stage, we use iterative rounding to eliminate every tournament from $\mathcal{T}_{9}$ present in the input digraph $D$ . The total weight of nodes removed in this stage is at most $\nicefrac{{9}}{{4}}$ times the corresponding decrease in the optimum weight. In the second stage, we present a $\nicefrac{{9}}{{4}}$ -approximation for DFVS in the remaining ${\cal T}_{9}$ -free digraph. As the family $\mathcal{T}_{9}$ is even more complex than $\mathcal{T}_{7}$ , we develop a novel approach to handle it. Namely, we consider the so-called triangle graph $H(D)$ of $D$ , obtained by deleting all arcs not participating in any directed triangle. We prove that $H(D)$ is perfect, and hence its chromatic number is equal to its clique number $\bm{\omega}$ . Therefore, any family of $\bm{\omega}-2$ color classes forms a DFVS. This approach directly yields the known $\nicefrac{{7}}{{3}}$ -approximation, but simpler. To achieve the improved $\nicefrac{{9}}{{4}}$ -approximation, we perform a more refined analysis of the sizes of the color classes, via the Greene–Kleitman theorem on posets.

2 The triangle graph of quasi-transitive digraphs

In this section, we introduce the key notion of the triangle graph of a digraph and analyze its properties in relation to the DFVS problem. In particular, we show that the triangle graph of a quasi-transitive digraph is perfect, and that forbidding tournaments with relatively large DFVS size forces the triangle graph to have a small clique number.

For a digraph $D$ , let $V(D)$ be its node set and let $A(D)$ be its arc set, and write $u\to v$ to indicate that $(u,v)\in A(D)$ . For $S\subseteq V(D)$ , let $D[S]$ denote the subdigraph of $D$ induced by $S$ . Note that quasi-transitive digraphs $D$ can equivalently be defined by the property that the existence of arcs $u\to v$ and $v\to w$ in $D$ implies that either $u\to w$ or $w\to u$ . When the existence of arcs $u\to v$ and $v\to w$ in $D$ implies $u\to w$ , the digraph $D$ is said to be transitive. Throughout, cycle and triangle mean directed cycle and directed triangle, respectively.

Recall that the objective of the DFVS problem is to intersect all cycles. We first show that in quasi-transitive digraphs, it suffices to hit all triangles in order to hit all cycles. To this end, our next lemma generalizes a well-known fact from tournaments to all quasi-transitive digraphs.

Lemma 2.

In quasi-transitive digraphs, every cycle contains a triangle.

Proof.

Let $D$ be a quasi-transitive digraph, and assume that the nodes $v_{1},\ldots,v_{k}$ with $k\geq 4$ form a cycle $C$ in $D$ with arcs $v_{1}\to v_{2}\to\cdots\to v_{k}\to v_{1}$ . We prove the assertion by induction on $k$ .

For the base case $k=4$ , as $D$ is quasi-transitive, there is an arc between $v_{1}$ and $v_{3}$ (see Figure 2). But either orientation of this arc creates a triangle. Next, assume that $k\geq 5$ . If $C$ contains a shorter cycle, the claim follows by the induction hypothesis. Thus, assume that this is not the case. By quasi-transitivity of $D$ , we have $v_{1}\to v_{3}$ , and so $v_{1}\to v_{i}$ for all $i=3,\ldots,k-1$ . This, though, creates a triangle $v_{1}\to v_{k-1}\to v_{k}\to v_{1}$ , a contradiction. $\hfill\blacktriangleleft$

This lemma motivates introducing the following notion, which is key to our arguments. For a digraph $D$ , we define its triangle graph $H(D)$ as the subdigraph of $D$ induced by the arcs that belong to the triangles in $D$ . We remark that the property of Lemma 2 holds in particular for $H(D)$ .

Figure 2: Every cycle of length 4 contains a triangle.

Figure 3: When the arcs

v_{1}v_{2}

and

v_{2}v_{3}

are present in

\overline{H}(T)

, the arc

v_{1}v_{3}

cannot be included in any triangle, i.e.,

v_{1}v_{3}\in A(\overline{H}(T))

.

$\blacktriangleright$ Remark 3.

We record here a simple but useful observation: every DFVS of $H(D)$ is also a DFVS of $D$ . Therefore, to find a DFVS of $D$ , it suffices to focus on the subgraph $H(D)$ .

The proof of the next lemma relies on the following useful structural decomposition of quasi-transitive digraphs, which we describe after introducing some additional notions. Let $D_{0}$ be a digraph with node set $\{v_{1},\ldots,v_{s}\}$ , and let $G_{1},\ldots,G_{s}$ be pairwise node-disjoint digraphs. The composition $D_{0}[G_{1},\ldots,G_{s}]$ is the digraph obtained from the disjoint union of $G_{1},\ldots,G_{s}$ by adding the following arcs: for every arc $(v_{i},v_{j})\in A(D_{0})$ , all arcs from every node of $G_{i}$ to every node of $G_{j}$ are added. We also recall that a digraph is called strong if, for every pair $u, v$ of distinct nodes in $D$ , there exists a directed path from $u$ to $v$ as well as a directed path from $v$ to $u$ .

Proposition 4 (Bang-Jensen and Huang [5]).

Let $D$ be a quasi-transitive digraph.

(i)

If $D$ is not strong, then there exist a transitive digraph $D_{0}$ and strong quasi-transitive digraphs $G_{1},\ldots,G_{s}$ such that $D=D_{0}[G_{1},\ldots,G_{s}]$ .
(ii)

If $D$ is strong, then there exists a strong tournament $T_{0}$ and quasi-transitive digraphs $Q_{1},\ldots,Q_{s}$ so that each $Q_{i}$ is either a single node or is non-strong and $D=T_{0}[Q_{1},\ldots,Q_{s}]$ .

Lemma 5.

Every quasi-transitive digraph $D$ can be embedded in a tournament $T$ such that $H(D)=H(T)$ .

Proof.

Let $n$ be the order of $D$ . By induction on $n$ , we show that there is a tournament $T$ containing $D$ as a subdigraph and satisfying $H(D)=H(T)$ .

For $n\leq 3$ , the assertion holds by inspection. Henceforth, assume that $n\geq 4$ .

First assume that $D$ is strong. Then, by Proposition 4, $D=T_{0}[Q_{1},\ldots,Q_{s}]$ for some tournament $T_{0}$ of order $s\geq 3$ and quasi-transitive digraphs $Q_{1},\ldots,Q_{s}$ . By the induction hypothesis, every $Q_{i}$ can be embedded in a tournament $T_{i}$ such that $H(Q_{i})=H(T_{i})$ . We then define $T:=T_{0}[T_{1},\ldots,T_{s}]$ and observe that $T$ is a tournament. Since the arcs of $D$ between any two distinct $Q_{i}$ are entirely directed from one to the other, the triangles of $D$ are either inherited from $T_{0}$ , meaning that they involve nodes from three distinct $Q_{i}$ ’s, or they are entirely contained within a single $Q_{i}$ . Therefore, $H(D)=H(T_{0})[H(Q_{1}),\ldots,H(Q_{s})]$ . The same reasoning also implies that $H(T)=H(T_{0})[H(T_{1}),\ldots,H(T_{s})]$ . Since $H(Q_{i})=H(T_{i})$ for $i=1,\ldots,s$ , we obtain $H(D)=H(T)$ .

Next, assume that $D$ is not strong. Then, by Proposition 4, $D=D_{0}[G_{1},\ldots,G_{s}]$ , where $D_{0}$ is a transitive digraph of order $s\geq 2$ and $G_{1},\ldots,G_{s}$ are strong quasi-transitive digraphs. Note that no arc of $D_{0}$ belongs to a triangle, which implies that $H(D)=H(G_{1})\cup\cdots\cup H(G_{s})$ . We know that every transitive digraph can be embedded in a transitive tournament. Let $T_{0}$ be such a transitive tournament containing $D_{0}$ . Moreover, by induction, each $G_{i}$ can be embedded in a tournament $T_{i}$ of the same order such that $H(G_{i})=H(T_{i})$ . We then set $T:=T_{0}[T_{1},\ldots,T_{s}]$ , for which we have $H(T)=H(T_{1})\cup\cdots\cup H(T_{s})$ . Combining the above relations yields $H(D)=H(T)$ . $\hfill\blacktriangleleft$

2.1 Perfectness of the triangle graph

A digraph is called perfect if, in every induced subdigraph, the chromatic number equals the clique number²²2For a digraph, the clique number and chromatic number refer to those of its underlying undirected graph. (see [3, Section 11.7]).

In the next lemma, we prove the useful property that for a quasi-transitive digraph $D$ , the triangle digraph $H(D)$ is perfect. Indeed, the perfectness of $H(D)$ follows from the fact that its complement is transitive. Recall that the arc set of a transitive digraph induces a partial order on its node set. By Mirsky’s theorem [20], in any finite partially ordered set, the maximum size of a chain equals the minimum number of antichains required to cover all elements. This translates to the statement that the chromatic number of a transitive digraph equals its clique number. Since transitivity is inherited by induced subdigraphs, it follows that transitive digraphs are perfect.

Lemma 6.

For any quasi-transitive digraph $D$ , $H(D)$ is a perfect digraph.

Proof.

Let $T$ be a tournament such that $H(D)=H(T)$ , which exists by Lemma 5. We will show that $\overline{H}(T):=T\setminus A(H(T))$ is a transitive digraph which implies that $\overline{H}(T)$ is perfect. Hence, by the Perfect Graph Theorem (Lovász [19]), it follows that $H(D)$ is perfect.

Assume that $(v_{1},v_{2}),(v_{2},v_{3})\in A(\overline{H}(T))$ . The tournament $T$ contains an arc between $v_{1}$ and $v_{3}$ . This arc cannot be $(v_{3},v_{1})$ ; otherwise, $v_{1},v_{2},v_{3}$ would form a triangle in $T$ , and so all its three arcs would belong to $H(T)$ , a contradiction. Hence, $(v_{1},v_{3})\in A(T)$ .

We claim that $(v_{1},v_{3})$ is not included in a triangle in $T$ . Else, there would exist a node $u$ forming the subgraph depicted in Figure 3. Again, $T$ being a tournament, there is an arc between $u$ and $v_{2}$ . However, either direction of the edge between $u$ and $v_{2}$ implies that either $(v_{1},v_{2})$ or $(v_{2},v_{3})$ would be an arc of a triangle, which is a contradiction. It follows that $(v_{1},v_{3})\in A(\overline{H}(T))$ , thereby establishing the transitivity of $\overline{H}(T)$ . $\hfill\blacktriangleleft$

For a digraph $D$ , let $\mathsf{mfvs}(D)$ denote the minimum size of a DFVS of $D$ . And for a digraph $D$ whose nodes are weighted by some function $w:V(D)\rightarrow\mathbb{Q}_{\geq 0}$ , let $\mathsf{mfvs}(D,w)$ denote the minimum weight of a DFVS of $D$ . We write $w(D)$ for the sum of the weights of all nodes in $D$ .

We now use the perfectness of $H(D)$ to bound $\mathsf{mfvs}(D,w)$ for quasi-transitive digraphs $(D,w)$ .

Theorem 7.

Let $(D,w)$ be a non-acyclic node-weighted quasi-transitive digraph, and let $\bm{\omega}$ be the clique number of $H(D)$ . Then $\mathsf{mfvs}(D,w)\leq\frac{\bm{\omega}-2}{\bm{\omega}}\,w(D)$ .

Proof.

Since $H=H(D)$ is a perfect digraph by Lemma 6, its chromatic number equals $\bm{\omega}$ . Consequently, $V(H)$ can be partitioned into $\bm{\omega}$ color classes, each of which is an independent set. Considering the union $S$ of any $\bm{\omega}-2$ color classes, the graph $H\setminus S$ is bipartite, implying that $H\setminus S$ contains no triangles. Therefore, $S$ serves as a DFVS for $H$ . To minimize the weight of such a DFVS, we select the $\bm{\omega}-2$ color classes with the smallest total weight. By this choice, their total weight is at most $\frac{\bm{\omega}-2}{\bm{\omega}}w(H)$ . The result now follows since $w(H)\leq w(D)$ , and any DFVS of $H$ is also a DFVS for $D$ . $\hfill\blacktriangleleft$

2.2 Transitive tournaments in the triangle graph

Define ${\cal T}_{2k+1}$ as the set of tournaments $T$ on $2k+1$ nodes satisfying $\mathsf{mfvs}(T)\geq k$ . A digraph is said to be ${\cal T}_{2k+1}$ -free if it contains no $T\in{\cal T}_{2k+1}$ as a subdigraph. Recall that an acyclic tournament is transitive and has a unique structure: its nodes admit a total ordering. Denote by $\mathbb{T}_{n}$ the transitive tournament of order $n$ .

Next, we establish another ingredient of our argument: for a ${\cal T}_{2k+1}$ -free quasi-transitive digraph $D$ , the size of the largest transitive tournament in $H(D)$ is bounded by $2^{k-1}$ . To prove this, we require two additional lemmas.

Let $v$ be a vertex of a digraph $H$ , and let $H^{\prime}$ be a subdigraph of $H$ not containing $v$ . We denote by $A(v,H^{\prime})$ the set of arcs in $H^{\prime}$ that form a triangle with $v$ .

Lemma 8.

Let $H$ be a digraph and $v\in V(H)$ . Then $A(v,H-v)$ induces a bipartite subgraph of $H$ .

Proof.

If $A(v,H-v)$ does not induce a bipartite graph, then it contains an odd cycle. This implies that $A(v,H-v)$ includes two arcs of the form shown in Figure 4. However, a single node cannot form a triangle with both of these arcs. Therefore, $A(v,H-v)$ must induce a bipartite subgraph. $\hfill\blacktriangleleft$

Figure 4: A forbidden subgraph for the graph induced by

A(v,H-v)

.

Lemma 9.

Let $D$ be a quasi-transitive digraph that contains a transitive tournament $\mathbb{T}$ .

(i)

If $A(u,\mathbb{T})\neq\emptyset$ , then $u$ must be adjacent to all nodes of $\mathbb{T}$ .
(ii)

If $A(u_{1},\mathbb{T})\neq\emptyset$ , $A(u_{2},\mathbb{T})\neq\emptyset$ , and $A(u_{1},\mathbb{T})\neq A(u_{2},\mathbb{T})$ , then $u_{1}$ and $u_{2}$ are adjacent in $D$ .

Proof.

(i)

Let $v_{1},\ldots,v_{p}$ be the nodes of $\mathbb{T}$ , ordered according to the total order of $\mathbb{T}$ . If $u\to v_{i}$ , then by the quasi-transitivity of $D$ , $u$ is adjacent to all nodes $v_{i},\ldots,v_{p}$ . Similarly, if $v_{j}\to u$ , then $u$ is adjacent to all nodes $v_{1},\ldots,v_{j}$ . By assumption, there exist indices $i<j$ such that there is a triangle $u\to v_{i}\to v_{j}\to u$ . Hence, the assertion follows.
(ii)

By (i), $u_{1}$ and $u_{2}$ are adjacent to all nodes of $\mathbb{T}$ . Hence, as $A(u_{1},\mathbb{T})\neq A(u_{2},\mathbb{T})$ , there must exist a node $v$ in $\mathbb{T}$ such that either $u_{1}\to v\to u_{2}$ or $u_{2}\to v\to u_{1}$ , and then the quasi-transitivity of $D$ implies that $u_{1}$ and $u_{2}$ are adjacent.

$\hfill\blacktriangleleft$

Theorem 10.

Let $k\geq 2$ , and let $D$ be a quasi-transitive digraph such that $H(D)$ contains $\mathbb{T}_{2^{k-1}+1}$ . Then $D$ contains a tournament from ${\cal T}_{2k+1}$ .

Proof.

We prove, by induction on $k\geq 2$ , that $k+1$ nodes from $\mathbb{T}_{2^{k-1}+1}$ together with $k$ nodes from $U:=V(H(D))\setminus V(\mathbb{T})$ form a tournament from ${\cal T}_{2k+1}$ .

For the base case $k=2$ , the digraph $H(D)$ contains $\mathbb{T}_{3}$ . By definition of $H(D)$ , every arc of $\mathbb{T}_{3}$ must be contained in a triangle in $D$ (and thus also in $H(D)$ ). This must be realized through nodes of $U$ . Consider Figure 5, where $v_{1},v_{2},v_{3}$ are the nodes of $\mathbb{T}_{3}$ . Choose $u_{1}\in U$ such that it forms a triangle with $v_{1},v_{3}$ . Since $D$ is quasi-transitive, we have either $v_{2}\to u_{1}$ or $u_{1}\to v_{2}$ . Assume the former. Then $u_{1},v_{1},v_{2}$ also form a triangle. Next, choose $u_{2}\in U$ such that $u_{2},v_{2},v_{3}$ form a triangle. This yields the configuration depicted in Figure 5. This subdigraph has no DFVS of size $1$ . By Lemma 9, $u_{1},u_{2}$ together with $\mathbb{T}_{3}$ induce a tournament $T$ (the two missing arcs in Figure 5 are not relevant for our argument). Therefore, $T\in{\cal T}_{5}$ . In case that $u_{1}\to v_{2}$ , then $u_{1},v_{2},v_{3}$ form a triangle. Then we choose $u_{2}$ such that $u_{2},v_{1},v_{2}$ form a triangle, and the result follows similarly.

Figure 5: A subdigraph

\mathbb{T}_{3}

(on nodes

v_{1},v_{2},v_{3}

) in

H(D)

forces a subdigraph in

D

with DFVS of size at least

2

.

Now, assume that $k\geq 3$ and the assertion holds for $k-1$ . For simplicity, set $p:=2^{k-1}+1$ and let $\mathbb{T}:=\mathbb{T}_{p}$ . Let $v_{1},\ldots,v_{p}$ be the nodes of $\mathbb{T}$ , ordered according to the transitive order of $\mathbb{T}$ . Since $\mathbb{T}$ is a subgraph of $H(D)$ , every arc of $\mathbb{T}$ must be included in a triangle, and again this can only be achieved by incorporating nodes from $U$ . Let $u_{1}\in U$ be a node that forms a triangle with the arc $(v_{1},v_{p})$ .

Let $X$ be the set of nodes $v$ in $\mathbb{T}$ such that $u_{1}\to v$ , and let $Y$ be the set of nodes $v$ in $\mathbb{T}$ such that $v\to u_{1}$ . Every arc of $\mathbb{T}$ directed from $X$ toward $Y$ forms a triangle with $u_{1}$ . Since $X\cup Y$ is a partition of $V(\mathbb{T})$ , we have $|X|+|Y|=2^{k-1}+1$ , and hence either $|X|\geq 2^{k-2}+1$ or $|Y|\geq 2^{k-2}+1$ .

First, assume that, $|X|\geq 2^{k-2}+1$ . Then $\mathbb{T}[X]$ contains $\mathbb{T}_{2^{k-2}+1}$ , and by the induction hypothesis, $k$ nodes from $X$ and $k-1$ nodes from $U$ form a tournament $T\in{\cal T}_{2k-1}$ . Observe that for every arc $v_{i}v_{j}$ in $\mathbb{T}[X]$ , $u_{1}$ cannot form a triangle with $v_{i}v_{j}$ because $u_{1}\to v_{i}$ and $u_{1}\to v_{j}$ . Thus, $u_{1}\notin V(T)$ . Also, $v_{p}\not\in X$ and $v_{i}\to v_{p}$ for every $v_{i}\in X$ . Let $T^{\prime}:=D[V(T)\cup\{u_{1},v_{p}\}]$ ; see Figure 6. By Lemma 9, $T^{\prime}$ is a tournament. Note that for every $v_{i}\in V(T)\cap X$ , $u_{1}v_{i}v_{p}$ is a triangle. Hence any DFVS of $T^{\prime}$ must contain either one of $u_{1},v_{p}$ together with a DFVS of $T$ , or the entire $V(T)\cap X$ . So $\mathsf{mfvs}(T^{\prime})\geq k$ , that is, $T^{\prime}\in{\cal T}_{2k+1}$ .

If $|Y|\geq 2^{k-2}+1$ , then we are done by a similar argument, replacing $Y$ by $X$ and $v_{p}$ by $v_{1}$ (note that $v_{1}\notin Y$ and $v_{1}\to v_{i}$ for every $v_{i}\in Y$ ). $\hfill\blacktriangleleft$

Figure 6: The structure of the tournament

T^{\prime}\in{\cal T}_{2k+1}

arising in the proof of Theorem 10. Arcs between

u_{1},v_{p}

and

Y\cap V(T)

are not drawn.

Theorem 11.

For every ${\cal T}_{5}$ -free (resp. ${\cal T}_{7}$ -free) quasi-transitive digraph $D$ , the clique number of $H(D)$ is at most $3$ (resp. $6$ ).

Proof.

First, let $D$ be a ${\cal T}_{5}$ -free quasi-transitive digraph. For sake of contradiction, assume that $H=H(D)$ contains a clique $K$ of order $4$ . Note that every tournament on $4$ nodes has a DFVS of size at most $1$ . Thus, $\mathsf{mfvs}(H[K])\leq 1$ implying that $H[K]$ and hence $H$ contains $\mathbb{T}_{3}$ . From Theorem 10, it follows that $D$ contains a tournament from ${\cal T}_{5}$ , a contradiction.

Second, let $D$ be a ${\cal T}_{7}$ -free quasi-transitive digraph. Assume that $H$ contains a clique $K$ of order $7$ . Then $\mathsf{mfvs}(H[K])\leq 2$ as $H[K]$ is also ${\cal T}_{7}$ -free. It follows that $H[K]$ and hence $H$ contains $\mathbb{T}_{5}$ . Now Theorem 10 implies that $D$ contains a tournament from ${\cal T}_{7}$ , a contradiction. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 12.

For ${\cal T}_{7}$ -free tournaments $T$ , Mnich et al. [21] showed that $\mathsf{mfvs}(T)\leq\tfrac{7}{9}w(T)$ . Theorems 7 and 11 improve this bound to $\mathsf{mfvs}(D,w)\leq\tfrac{2}{3}w(D)$ for any node-weighted ${\cal T}_{7}$ -free quasi-transitive digraph $(D,w)$ .

2.3 Greene–Kleitman Theorem

For a partially ordered set (poset) ${\cal P}$ , the Greene–Kleitman theorem [13] asserts that the maximum size of a $k$ -chain – that is, the union of $k$ chains – in ${\cal P}$ is equal to the minimum $k$ -norm of a partition of ${\cal P}$ into antichains. Here, the $k$ -norm of a family ${\cal A}=(A_{1},\ldots,A_{t})$ of sets is defined as

\|{\cal A}\|_{k}:=\sum_{i=1}^{t}\min(|A_{i}|,k)\enspace.

Given a quasi-transitive digraph $D$ , by Lemma 5 there is a tournament $T$ such that $H(D)=H(T)$ . By the proof of Lemma 6, we know that $\overline{H}(T)$ is a transitive digraph and hence defines a poset $\mathcal{P}$ . Any chain in ${\cal P}$ is an independent set in $H(T)$ . Conversely, every independent set in $H(T)$ is a clique in the transitive digraph $\overline{H}(T)$ , and hence it must be a transitive tournament, which in turn corresponds to a chain in ${\cal P}$ . Consequently, $2$ -chains in ${\cal P}$ correspond to induced bipartite subdigraphs of $H(T)$ .

The Greene–Kleitman theorem can be extended to the case where the elements of ${\cal P}$ have non-negative integer weights, as shown by Cong [10, Theorem 2.2]. For this, we need to generalize the notion of a partition into antichains to the weighted setting. Given a non-negative integral weight function $z$ on the elements of ${\cal P}$ , a family ${\cal A}$ of antichains is called a $z$ -partition of antichains in ${\cal P}$ if every element $v$ of ${\cal P}$ appears in $z_{v}$ (the weight assigned to $v$ ) of the antichains in ${\cal A}$ . Clearly, when $z=1$ , this definition reduces to the antichain partition. The weighted Greene–Kleitman theorem by Cong [10] can be translated to triangle graphs as follows:

Lemma 13.

Let $(D,z)$ be a node-weighted quasi-transitive digraph with $z:V(D)\to\mathbb{Z}_{\geqslant 0}$ . Then the maximum weight of an induced bipartite subgraph in $H(D)$ equals the minimum $2$ -norm of $z$ -partition of cliques of $H(D)$ .

For transitive digraphs with non-negative rational weights, there is an efficient algorithm for finding maximum-weight $2$ -chains. Applied to $\overline{H}(D)$ , this result can be stated as follows.

Lemma 14 ([22]).

There is an algorithm that, given any node-weighted quasi-transitive digraph $(D,w)$ with weight function $w:V(D)\to\mathbb{Q}_{\geqslant 0}$ , computes an induced bipartite subgraph in $H(D)$ of maximum weight in $O(|V(D)|^{2})$ time.

3 Revisiting known results: Extensions and simplified proofs

In this section, we present intermediate results that simplify and improve known DFVS algorithms for tournaments and also extend them to quasi-transitive digraphs. First, we devise an exact polynomial-time algorithm for computing DFVS in $\mathcal{T}_{5}$ -free tournaments. Second, we provide a simple $\nicefrac{{7}}{{3}}$ -approximation algorithm for DFVS on all tournaments. Finally, we give a polynomial-time $2$ -approximation algorithm for DFVS in $\mathcal{T}_{7}$ -free quasi-transitive digraphs.

For a weight function $z$ on $V(D)$ , we continue to use $z_{v}$ to denote the weight assigned to $v\in V(D)$ , and for $S\subseteq V(D)$ we set $z(S):=\sum_{v\in S}z_{v}$ .

3.1 An exact algorithm for DFVS in ${\cal T}_{5}$ -free quasi-transitive digraphs

For a weighted digraph $(D,z)$ with non-negative integral weight $z$ , a $z$ -packing of directed triangles is a family $F$ of triangles such that, for each node $v$ of $D$ , the number of triangles in $F$ containing $v$ is at most $z_{v}$ . When $z=1$ , the triangles in $F$ must be disjoint; however, this need not hold for general weight functions. We remark that there is an LP-duality relationship between triangle packing and DFVS, and that tournaments in ${\cal T}_{5}$ do not satisfy strong duality, in the sense that they contain only one triangle while their minimum DFVS has size $2$ .

Our next theorem extends, with a simpler proof, the result of Cai et al. [9, Theorem 3.2] showing that, for ${\cal T}_{5}$ -free tournaments, the maximum size of triangle packing is equal to the minimum size of a DFVS. It also extends (and improves the run-time) of the exact algorithm for computing a minimum-size DFVS in ${\cal T}_{5}$ -free tournaments (the “Minimum $\Delta$ -Covering Algorithm” from Section 4 of the work by Cai et al. [9] with run-time $O(|V(D)|^{3})$ ) to the broader class of quasi-transitive digraphs.

Theorem 15.

Let $(D,z)$ be a quasi-transitive digraph with integral node weights.

(i)

For every weight function $z$ , the minimum weight of a DFVS of $(D,z)$ equals the size of a maximum $z$ -packing of triangles in $D$ if and only if $D$ is ${\cal T}_{5}$ -free.
(ii)

For ${\cal T}_{5}$ -free quasi-transitive digraph $(D,z)$ , there exists an exact algorithm for finding a minimum DFVS in $D$ that runs in time $O(|V(D)|^{2})$ .

Proof.

Assume, without loss of generality, that each node of $D$ lies on some triangle. Let $H=H(D)$ , and write $V$ for $V(H)=V(D)$ . Let $B\subseteq V$ be a node set that induces a bipartite subgraph of maximum weight in $H$ .

(i)

First, assume that $D$ is ${\cal T}_{5}$ -free. We know that $\overline{B}:=V\setminus B$ is a DFVS of $D$ . Note that, by LP duality, the size of every $z$ -packing of triangles is at most the weight of any DFVS. Therefore, to prove equality, it suffices to show that there exists a $z$ -packing of triangles in $H$ whose size is equal to $z(\overline{B})$ .

Let ${\cal K}$ be a $z$ -partition of cliques of $H$ with minimum $2$ -norm. By Theorem 11, every $K\in{\cal K}$ has size at most $3$ . Let $t_{i}$ denote the number of $i$ -cliques in ${\cal K}$ for $i=1,2,3$ . So, $\|{\cal K}\|_{2}=2t_{3}+2t_{2}+t_{1}.$ By Lemma 13, $z(B)=\|{\cal K}\|_{2}$ , and thus $z(\overline{B})=z(V)-\|{\cal K}\|_{2}=t_{3}.$ Note that the $3$ -cliques in $H$ correspond to (directed) triangles. Otherwise, $H$ would contain $\mathbb{T}_{3}$ which by Theorem 10, implies that $H$ contains a tournament from ${\cal T}_{5}$ , a contradiction. It follows that the $3$ -cliques of ${\cal K}$ form a $z$ -packing of triangles in $H$ with size $t_{3}=z(\overline{B})$ , giving the result.

We now verify the necessity of $D$ being ${\cal T}_{5}$ -free. Suppose that $D$ contains a subtournament $T\in{\cal T}_{5}$ . Define a weight function $w$ by assigning weight $1$ to each node of $T$ and weight $0$ to all other nodes of $D$ . Then $\mathsf{mfvs}(D,w)=2$ , whereas every $w$ -packing of directed triangles in $D$ has size at most $1$ .

(ii)

As proved in (i), a minimum DFVS of $(D,z)$ is the complement of an induced bipartite subgraph of maximum weight. By Lemma 14, there is an algorithm to find such a subgraph that runs in time $O(|V(D)|^{2})$ .

$\hfill\blacktriangleleft$

3.2 A $\nicefrac{{7}}{{3}}$ -approximation for DFVS in quasi-transitive digraphs

For ${\cal T}_{7}$ -free quasi-transitive digraph $(D,w)$ , by Remark 12, $\mathsf{mfvs}(D,w)\leq\tfrac{2}{3}w(D)$ . This immediately yields a $\nicefrac{{7}}{{3}}$ -approximation algorithm for the DFVS problem in node-weighted quasi-transitive digraphs $(D,w)$ , as follows. Consider the linear program which seeks $x\geq 0$ minimizing $\sum_{v\in V(D)}w_{v}x_{v}$ subject to (1) $x(K)\geq 1$ for all triangles $K$ , and (2) $x(K)\geq 3$ for all 7-node subdigraphs $K\in\mathcal{T}_{7}$ . Let $\mathsf{opt}(D)$ be the optimal value of this LP. We iteratively solve this LP, obtaining a solution $x$ , then remove all nodes $v$ with $x_{v}\geq\tfrac{3}{7}$ , placing them in a set $\tilde{F}$ and subsequently remove all nodes that do not belong to a triangle. As a result, we obtain a subdigraph $\tilde{D}$ that admits a feasible solution $\tilde{x}<\tfrac{3}{7}$ to the above LP. The constraint (2) implies that $\tilde{D}$ should be ${\cal T}_{7}$ -free. Since all nodes of $\tilde{D}$ lie in some triangle and $\tilde{x}<\tfrac{3}{7}$ , it follows that $\tilde{x}>0$ over $\tilde{D}$ . Thus, by applying primal-dual slackness (see [21, Lemma 6]), we obtain $\mathsf{opt}(\tilde{D})\geq\tfrac{1}{3}w(\tilde{D})$ . Consequently,

\tfrac{7}{3}\mathsf{mfvs}(D)\geq\tfrac{7}{3}\mathsf{opt}(D)\geq w(\tilde{F})+% \tfrac{7}{3}\mathsf{opt}(\tilde{D})\geq w(\tilde{F})+\tfrac{7}{9}w(\tilde{D})% \geq w(\tilde{F})+\mathsf{mfvs}(\tilde{D})\enspace.

(1)

Note that the second inequality follows from the fact that the restriction of an optimal solution for $D$ to $\tilde{D}$ gives a feasible solution for $\tilde{D}$ . Since a DFVS of $\tilde{D}$ together with $\tilde{F}$ forms a DFVS of $D$ , the above inequality implies that we have obtained a DFVS of $D$ with weight at most $\tfrac{7}{3}\mathsf{mfvs}(D)$ .

3.3 A deterministic polynomial-time 2-approximation for DFVS in $\mathcal{T}_{7}$ -free quasi-transitive digraphs

Recall that, in tournaments, the only known 2-approximations for DFVS are either randomized, or they require quasi-polynomial time [18]. Consequently, the same is true for the broader class of quasi-transitive digraphs. We overcome these challenges for the class of $\mathcal{T}_{7}$ -free quasi-transitive digraphs by a slight modification of the $\nicefrac{{7}}{{3}}$ -approximation algorithm described above. We only replace the threshold $\tfrac{3}{7}$ by $\tfrac{1}{2}$ in the algorithm to obtain the set $\tilde{F}$ and the subdigraph $\tilde{D}$ . As $D$ is ${\cal T}_{7}$ -free, $\tilde{D}$ is also ${\cal T}_{7}$ -free, and thus by Theorems 7 and 11, $\mathsf{mfvs}(\tilde{D},w)\leq\tfrac{2}{3}w(\tilde{D})$ . We still retain the property that $\tilde{x}>0$ over $\tilde{D}$ . Thus, by applying primal–dual slackness, we obtain $\mathsf{opt}(\tilde{D})\geq\tfrac{1}{3}w(\tilde{D})$ . As a result, we obtain

2\mathsf{mfvs}(D)\geq 2\mathsf{opt}(D)\geq w(\tilde{F})+2\mathsf{opt}(\tilde{D% })\geq w(\tilde{F})+\tfrac{2}{3}w(\tilde{D})\geq w(\tilde{F})+\mathsf{mfvs}(% \tilde{D})\enspace.

The inequalities here, particularly the second one, are justified analogously to (1).

4 A $\nicefrac{{9}}{{4}}$ -approximation for DFVS in quasi-transitive digraphs

In this section we prove our main result. Let $(D,w)$ be a digraph with node weights $w:V(D)\to\mathbb{Q}_{\geq 0}$ . For a function $x:V(D)\to\mathbb{Q}$ , and $S\subset V(D)$ recall that $x(S)=\sum_{v\in S}x_{v}$ .

We use iterative rounding for the following LP relaxation of the DFVS problem in $(D,w)$ :

minimize	$\displaystyle\nobreak\ \sum_{v\in V(D)}w_{v}x_{v},$	(LP)
subject to	$\displaystyle\quad x(K)\geq\mathsf{mfvs}(D[K]),\nobreak\ \hbox{for cliques $K$% of $D$ with $\|K\|\leq 15$},$
	$\displaystyle\quad x\geq 0\enspace.$

We denote by $\mathsf{opt}(D)=\mathsf{opt}(D,w)$ the optimal value of (LP).

4.1 Algorithm description

The algorithm consists of two phases. In the first phase, we find a subdigraph $\tilde{D}$ of $D$ such that there is a solution $\tilde{x}<\frac{4}{9}$ to (LP) for $\tilde{D}$ . In particular, $\tilde{D}$ is ${\cal T}_{9}$ -free (otherwise, $\tilde{x}$ cannot be feasible to (LP) for $\tilde{D}$ ). To obtain $\tilde{D}$ , we iteratively solve (LP). During an iteration, a complementary set $\tilde{F}$ is produced, consisting of all nodes $v$ with $x_{v}\geq\frac{4}{9}$ for the optimal solution $x$ of the corresponding iteration of (LP). By the end of the first phase, if $\tilde{D}=\emptyset$ , return $\tilde{F}$ as a DFVS.

Otherwise, the algorithm enters the second phase, where we start by partitioning $V(\tilde{D})$ into subsets according to the values of $\tilde{x}$ . The subgraphs induced by these subsets turn out to have small clique numbers. We then compute a DFVS of “small” weight for each of them using Theorem 7, and denote them by $X_{1},\ldots,X_{4}$ . The algorithm outputs the set $\tilde{F}$ together with the $X_{i}$ of minimum weight among the four. In Theorem 1, we will prove that the output is indeed a DFVS of $(D,w)$ with weight at most $\frac{9}{4}\mathsf{mfvs}(D,w)$ .

For the algorithm description and analysis, we introduce the notation

V_{[a,b)}:=\left\{v\in V(\tilde{D}):a\leq\tilde{x}_{v}<b\right\},

and $\tilde{D}_{I}:=\tilde{D}[V_{I}]$ for any interval $I$ .

Algorithm 1 DFVS for Quasi-Transitive Digraphs.

4.2 Algorithm analysis

We first argue that Algorithm 1 runs in polynomial time. The first phase involves iterations of (LP) which have size $\mathcal{O}(n^{15})$ where $n=|V(D)|$ . The number of iterations is at most $n$ as in each iteration at least one new node is included in the set $\tilde{F}$ and removed from $D$ . The second phase involves finding a maximum-weight induced bipartite subgraph of $H(\tilde{D}_{I})$ for three different $I$ , which can be done in $\mathcal{O}(n^{2})$ by Lemma 14.

In what follows, we establish the correctness of Algorithm 1 and prove the claimed approximation factor.

Lemma 16.

For a quasi-transitive digraph $D$ , consider the output $\tilde{D}$ of the first phase in Algorithm 1. Then the clique number of $H(\tilde{D})$ is at most $14$ .

Proof.

By definition, there exists an optimal solution $\tilde{x}$ to (LP) for $\tilde{D}$ , such that $\tilde{x}_{v}<\frac{4}{9}$ for all $v\in V(\tilde{D})$ . This also implies that $\tilde{D}$ is $\mathcal{T}_{9}$ -free; otherwise, the constraints of (LP) would be violated for some clique $K$ of order 9.

For sake of contradiction, assume that $H(\tilde{D})$ contains a clique $K$ of order $15$ . If $\mathsf{mfvs}(\tilde{D}[K])\leq 6$ , then there is a set $F\subset K$ with $|F|\leq 6$ such that $K\setminus F$ is a transitive tournament. This means $H(\tilde{D})$ contains $\mathbb{T}_{9}$ . Hence, from Theorem 10, it follows that $\tilde{D}$ contains a tournament from ${\cal T}_{9}$ , which is impossible. Thus, $\mathsf{mfvs}(\tilde{D}[K])\geq 7$ , that is $K\in{\cal T}_{15}$ and the feasibility of $\tilde{x}$ implies that $\tilde{x}(K)\geq 7$ . This, in turn implies that for some $v\in K$ , we have $\tilde{x}_{v}\geq\frac{\tilde{x}(K)}{|K|}\geq\frac{7}{15}>\frac{4}{9}$ – a contradiction. $\hfill\blacktriangleleft$

We are now ready to prove our main result:

Theorem 1 (restated).

The output of Algorithm 1 for a node-weighted quasi-transitive digraph $(D,w)$ is a DFVS with weight at most $\tfrac{9}{4}\mathsf{mfvs}(D,w)$ .

Proof.

First, we show that the output of Algorithm 1, namely $\tilde{F}\cup X$ , is a DFVS of $D$ . Note that $\tilde{x}_{v}>\tfrac{1}{9}$ for any $v\in V(\tilde{D})$ . Otherwise, since every node of $\tilde{D}$ lies on a triangle, $v$ forms a triangle with, say, nodes $v^{\prime}$ and $v^{\prime\prime}$ , but $\tilde{x}_{v}+\tilde{x}_{v^{\prime}}+\tilde{x}_{v^{\prime\prime}}<\tfrac{1}{9}% +\tfrac{4}{9}+\tfrac{4}{9}=1$ – a contradiction (the feasibility of $\tilde{x}$ implies that $\tilde{x}(K)\geq 1$ for every triangle $K$ ). This also implies that every triangle in $D$ not contained in $\tilde{D}$ must necessarily intersect $\tilde{F}$ . Consequently, the union of any DFVS of $\tilde{D}$ and the set $\tilde{F}$ constitutes a DFVS of $D$ . It therefore suffices to demonstrate that $X$ is a DFVS of $\tilde{D}$ . To this end, we establish that each set defined in (2) is indeed a DFVS of $\tilde{D}$ :

(i)

$B_{[\frac{1}{9},\frac{4}{9})}$ induces a bipartite subgraph of $\tilde{D}$ , so its complement $X_{1}$ is a DFVS of $\tilde{D}$ .
(ii)

A triangle in $\tilde{D}$ that intersects $V_{[\frac{1}{9},\frac{1}{7})}$ must also intersect $V_{[\frac{3}{7},\frac{4}{9})}$ , a fact that is implied by the feasibility of $\tilde{x}$ for (LP) on $\tilde{D}$ . Other triangles of $\tilde{D}$ are included in $\tilde{D}_{[\frac{1}{7},\frac{3}{7})}$ , and we know that $\overline{B}_{[\frac{1}{7},\frac{3}{7})}$ is a DFVS of $\tilde{D}_{[\frac{1}{7},\frac{3}{7})}$ . Therefore, $X_{2}=V_{[\frac{3}{7},\frac{4}{9})}\cup\overline{B}_{[\frac{1}{7},\frac{3}{7})}$ is a DFVS of $\tilde{D}$ .
(iii)

Similarly, every triangle in $\tilde{D}$ that intersects $V_{[\frac{1}{9},\frac{1}{5})}$ must also intersect $V_{[\frac{2}{5},\frac{4}{9})}$ . Since $\overline{B}_{[\frac{1}{5},\frac{2}{5})}$ is a DFVS of $\tilde{D}_{[\frac{1}{5},\frac{2}{5})}$ , their union, i.e. $X_{3}$ , is a DFVS of $\tilde{D}$ .
(iv)

Every triangle in $\tilde{D}$ must contain a node $v$ with $\tilde{x}_{v}\geq\frac{1}{3}$ . Hence, $X_{4}$ is a DFVS of $\tilde{D}$ .

To complete the proof, we need to show that

w(\tilde{F})+w(X)\leq\tfrac{9}{4}\mathsf{mfvs}(D,w)\enspace.

(3)

For this purpose, it suffices to establish that

w(X)\leq\tfrac{9}{4}\mathsf{opt}(\tilde{D})\enspace.

(4)

To see why this is sufficient, observe that $\mathsf{opt}(D)\geq\mathsf{opt}(\tilde{D})+\frac{4}{9}w(\tilde{F})$ . This follows by induction and the fact that in every iteration of the phase 1, the restriction of an optimal solution to (LP) for $D$ onto $V(\tilde{D})$ remains a feasible solution to (LP) for $\tilde{D}$ . It then follows that $\tfrac{9}{4}\mathsf{opt}(D)\geq w(X)+w(\tilde{F})$ . This completes the proof of (3), since $\mathsf{mfvs}(D,w)\geq\mathsf{opt}(D)$ .

The remainder of the proof is dedicated to establishing (4), which we address by considering the following two cases. Throughout these cases, we leverage the property that $\tilde{D}$ is ${\cal T}_{9}$ -free.

Case 1.

$w(X_{1})\geq\frac{27}{32}w(V_{[\frac{1}{9},\frac{4}{9})})$

For simplicity, let $\tilde{B}:=B_{[\frac{1}{9},\frac{4}{9})}$ and $\tilde{V}:=V(\tilde{D})=V_{[\frac{1}{9},\frac{4}{9})}$ . We proceed by applying Lemma 13, requiring us to work with integral weights. So for some sufficiently large positive integer $M$ , we can assume that $z:=Mw$ is an integral weight function on $\tilde{V}$ . Let ${\cal K}$ be a $z$ -partition of cliques of $H=H(\tilde{D})$ with minimum $2$ -norm, and let $t_{i}$ be the number of $i$ -cliques in ${\cal K}$ . By Lemma 16, we have $|K|\leq 14$ for every $K\in{\cal K}$ . Then we have

z(\tilde{V})=\sum_{K\in{\cal K}}\|K\|=\sum_{i=1}^{14}it_{i}\enspace.

By Lemma 13, we have

z(\tilde{B})=\sum_{i=1}^{14}\min(i,2)t_{i}=t_{1}+\sum_{i=2}^{14}2t_{i}\enspace.

It follows that $z(X_{1})=z(\tilde{V})-z(\tilde{B})=\sum_{i=3}^{14}(i-2)t_{i}$ . By assumption, we have $32z(X_{1})-27z(\tilde{V})\geq 0$ , that is

-27t_{1}-54t_{2}+\sum_{i=3}^{14}(5i-64)t_{i}\geq 0\enspace.

(5)

We observe that for every clique $K$ in $H$ with $|K|\geq 9$ , we have $\mathsf{mfvs}(H[K])\geq|K|-8$ . Otherwise, $H[K]$ would possess a DFVS $F$ with $|F|\leq|K|-9$ , implying that $K\setminus F$ is a transitive tournament of order at least $9$ . This would mean $H$ contains $\mathbb{T}_{9}$ , which by Theorem 10 implies that $H$ contains a tournament from $\mathcal{T}_{9}$ , a contradiction. From the feasibility of $\tilde{x}$ for (LP), it then follows that $\sum_{v\in K}\tilde{x}_{v}\geq|K|-8$ . Summing up for all $i$ -cliques with $9\leq i\leq 14$ , we deduce that

M\cdot\mathsf{opt}(\tilde{D})=\sum_{v\in\tilde{V}}z_{v}\tilde{x}_{v}=\sum_{K% \in{\cal K}}\sum_{v\in K}\tilde{x}_{v}\geq\sum_{i=9}^{14}(i-8)t_{i}\enspace.

We see that

9M\cdot\mathsf{opt}(\tilde{D})-4z(X_{1})\geq\sum_{i=9}^{14}(9i-72)t_{i}-\sum_{% i=3}^{8}(4i-8)t_{i}\geq\sum_{i=3}^{14}(5i-64)t_{i}\geq 0,

where the last inequality follows from (5). Hence, $\mathsf{opt}(\tilde{D})-\tfrac{4}{9}w(X_{1})\geq 0,$ which completes the proof for Case 1.

Case 2.

$w(X_{1})\leq\frac{27}{32}w(V_{[\frac{1}{9},\frac{4}{9})})$

For the remainder of the proof, we partition $V(\tilde{D})=V_{[\frac{1}{9},\frac{4}{9})}$ into subsets $V_{I}$ , corresponding to the intervals $I$ listed in Table 1. For convenience, we also adopt the notation shown in the table to denote the weights of these node sets $V_{I}$ :

Table 1: Intervals

I

partitioning

[\frac{1}{9},\frac{4}{9})

and the notation used for the weights of

V_{I}

.

$I$		$[\frac{1}{9},\frac{1}{7})$	$[\frac{1}{7},\frac{1}{5})$	$[\frac{1}{5},\frac{1}{3})$	$[\frac{1}{3},\frac{2}{5})$	$[\frac{2}{5},\frac{3}{7})$	$[\frac{3}{7},\frac{4}{9})$
$w(V_{I})$		$w_{1}$	$w_{2}$	$w_{3}$	$w_{4}$	$w_{5}$	$w_{6}$

With the notation of Table 1 it is evident that

\mathsf{opt}(\tilde{D})\geq g:=\tfrac{3}{7}w_{6}+\tfrac{2}{5}w_{5}+\tfrac{1}{3% }w_{4}+\tfrac{1}{5}w_{3}+\tfrac{1}{7}w_{2}+\tfrac{1}{9}w_{1}\enspace.

Next, we derive upper bounds for each of $w(X_{1}),\ldots,w(X_{4})$ in terms of $w_{1},\ldots,w_{6}$ . A suitable convex combination of these bounds will be used later to bound $w(X)$ .

(i)

By assumption, $w(X_{1})\leq\frac{27}{32}w(V_{[\frac{1}{9},\frac{4}{9})})$ , so

$w(X_{1})\leq f_{1}:=\tfrac{27}{32}(w_{1}+\cdots+w_{6})\enspace.$
(ii)

Since $\tilde{D}_{[\frac{1}{7},\frac{3}{7})}$ is ${\cal T}_{7}$ -free (otherwise the constraint of (LP) would be violated for some clique $K$ of order 7 in $\tilde{D}$ ), applying Theorems 7 and 11 yields $w(\overline{B}_{[\frac{1}{7},\frac{3}{7})})\leq\frac{2}{3}w(\tilde{D}_{[\frac{% 1}{7},\frac{3}{7})})$ . Therefore,

$w(X_{2})\leq f_{2}:=w_{6}+\tfrac{2}{3}(w_{2}+\cdots+w_{5})\enspace.$
(iii)

Similarly $\tilde{D}_{[\frac{1}{5},\frac{2}{5})}$ is ${\cal T}_{5}$ -free, and thus applying Theorems 7 and 11 yields $w(\overline{B}_{[\frac{1}{5},\frac{2}{5})})\leq\tfrac{1}{3}w(\tilde{D}_{[\frac% {1}{5},\frac{2}{5})})$ . Therefore,

$w(X_{3})\leq f_{3}:=w_{5}+w_{6}+\tfrac{1}{3}(w_{3}+w_{4})\enspace.$
(iv)

Finally, we have

$w(X_{4})=f_{4}:=w_{4}+w_{5}+w_{6}\enspace.$

Note that for any non-negative reals $\lambda_{1},\ldots,\lambda_{4}$ with $\lambda_{1}+\cdots+\lambda_{4}=1$ , we have

w(X)=\min\bigl\{w(X_{1}),\ldots,w(X_{4})\bigr\}\leq\lambda_{1}w(X_{1})+\cdots+% \lambda_{4}w(X_{4})\leq\lambda_{1}f_{1}+\cdots+\lambda_{4}f_{4}\enspace.

We now seek suitable $\lambda_{1},\ldots,\lambda_{4}$ such that

\tfrac{9}{4}g\geq\lambda_{1}f_{1}+\cdots+\lambda_{4}f_{4}\enspace.

This can be formulated as a linear program whose solution yields

\lambda_{1}=\tfrac{8}{35},\,\lambda_{2}=\tfrac{27}{140},\,\lambda_{3}=\tfrac{2% 7}{70},\,\lambda_{4}=\tfrac{27}{140}\enspace.

Hence, we come up with the following inequality which can be verified directly:

\tfrac{9}{4}\mathsf{opt}(\tilde{D})-w(X)\geq\tfrac{9}{4}g-\bigl(\tfrac{8}{35}f% _{1}+\tfrac{27}{140}f_{2}+\tfrac{27}{70}f_{3}+\tfrac{27}{140}f_{4}\bigr)=% \tfrac{2}{35}w_{1}+\tfrac{3}{28}w_{4}\geq 0\enspace.

This finishes the proof of (4), and thereby completes the proof of the theorem. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 2.

We now discuss the prospects for improving our method and the limitations that must be overcome to further refine the approximation ratio. Algorithm 1 can be adjusted to work with $\mathcal{T}_{2k+1}$ -free digraphs. Concretely, line 3 of Algorithm 1 can be adapted to remove nodes with $x_{v}\geq\frac{k}{2k+1}$ (for a given $k\geq 5$ ) and identify a $\mathcal{T}_{2k+1}$ -free subdigraph $\tilde{D}$ of $D$ . Improving the approximation ratio essentially requires establishing “small” upper bounds analogous to (4) which relies on Lemma 16. On the other hand, generalization of Lemma 16 to arbitrary $k$ yields an exponential bound on the clique number of $H(\tilde{D})$ . This bound is tight; indeed, recall that the proof of Theorem 10 constructs a tournament by appending a set $U^{\prime}$ of $k$ nodes to $\mathbb{T}_{2^{k-1}+1}$ . If the digraph $D$ consists only of $\mathbb{T}_{2^{k-1}+1}$ and $U^{\prime}$ , then $D$ remains $\mathcal{T}_{2k+1}$ -free, yet the clique number of $H(\tilde{D})$ is at least $2^{k-1}+1$ . Consequently, for $k\geq 5$ , a straightforward generalization of Lemma 16 will not suffice to establish a sufficiently strong bound analogous to (4), and thus will not improve the approximation ratio.

5 Discussion

We devised the first non-trivial approximation algorithm for the node-weighted DFVS problem on quasi-transitive digraphs, with approximation factor $\nicefrac{{9}}{{4}}$ . It directly improves the previously best deterministic polynomial-time approximation factor $\nicefrac{{7}}{{3}}$ for DFVS on tournaments [1, 21]. More importantly, our algorithm is much simpler than the $\nicefrac{{7}}{{3}}$ -approximation. A natural quest is to obtain deterministic 2-approximation algorithms for DFVS on quasi-transitive digraphs. This would completely settle the approximability of DFVS on this class of digraphs, as the Unique Games Conjecture rules out $(2-\varepsilon)$ -approximations for any $\varepsilon>0$ .

References

[1] Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh. A $7/3$ -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams. Discrete Appl. Math., 337:149–160, 2023. doi:10.1016/J.DAM.2023.04.016.
[2] Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289–297, 1999. doi:10.1137/S0895480196305124.
[3] Jørgen Bang-Jensen and Gregory Gutin. Classes of directed graphs, volume 11. Springer, 2018.
[4] Jørgen Bang-Jensen, Alessandro Maddaloni, and Saket Saurabh. Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica, 76(2):320–343, 2016. doi:10.1007/S00453-015-0038-2.
[5] Jørgen Bang-Jensen and Jing Huang. Quasi-transitive digraphs. J. Graph Theory, 20(2):141–161, 1995. doi:10.1002/JGT.3190200205.
[6] Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167–188, 1996.
[7] Piotr Berman and Grigory Yaroslavtsev. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Proc. APPROX 2012, volume 7408 of Lecture Notes Comput. Sci., pages 50–60, 2012. doi:10.1007/978-3-642-32512-0_5.
[8] Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, and Marcin Wrochna. On directed feedback vertex set parameterized by treewidth. In Proc. WG 2018, volume 11159 of Lecture Notes Comput. Sci., pages 65–78, 2018. doi:10.1007/978-3-030-00256-5_6.
[9] Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993–2007, 2001. doi:10.1137/S0097539798338163.
[10] Jason Cong. Computing maximum weighted $k$ -families and $k$ -cofamilies in partially ordered sets. Technical Report CSD-930014, University of California, 1993. URL: https://ftp.cs.ucla.edu/tech-report/1993-reports/930014.pdf.
[11] Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. doi:10.1007/PL00009191.
[12] Michel X Goemans and David P Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 18(1):37–59, 1998. doi:10.1007/PL00009810.
[13] Curtis Greene and Daniel J. Kleitman. The structure of Sperner $k$ -families. J. Combinatorial Theory Ser. A, 20(1):41–68, 1976. doi:10.1016/0097-3165(76)90077-7.
[14] Sushmita Gupta, Sounak Modak, Saket Saurabh, and Sanjay Seetharaman. Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments. In Proc. LATIN 2024, volume 14578 of Lecture Notes Comput. Sci., pages 225–240, 2024. doi:10.1007/978-3-031-55598-5_15.
[15] Venkatesan Guruswami and Euiwoong Lee. Simple proof of hardness of feedback vertex set. Theory Comput., 12(6):1–11, 2016. doi:10.4086/TOC.2016.V012A006.
[16] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer, 1972. doi:10.1007/978-1-4684-2001-2_9.
[17] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within $2-\varepsilon$ . J. Comput. Syst. Sci., 74(3):335–349, 2008.
[18] Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2-approximating feedback vertex set in tournaments. In Proc. SODA 2020, pages 1010–1018, 2020. doi:10.1137/1.9781611975994.61.
[19] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Math., 2(3):253–267, 1972. doi:10.1016/0012-365X(72)90006-4.
[20] L. Mirsky. A dual of Dilworth’s decomposition theorem. Amer. Math. Monthly, 78:876–877, 1971.
[21] Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A $7/3$ -approximation for feedback vertex sets in tournaments. In Proc. ESA 2016, volume 57 of Leibniz Int. Proc. Informatics, pages 67:1–67:14, 2016. doi:10.4230/LIPIcs.ESA.2016.67.
[22] M. Sarrafzadeh and R.-D. Lou. Maximum $k$ -covering of weighted transitive graphs with applications. Algorithmica, 9(1):84–100, 1993. doi:10.1007/BF01185340.
[23] Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. doi:10.1007/BF01200760.

[bib.bib1] [1] Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh. A $7/3$ -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams. Discrete Appl. Math., 337:149–160, 2023. doi:10.1016/J.DAM.2023.04.016.

[bib.bib2] [2] Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289–297, 1999. doi:10.1137/S0895480196305124.

[bib.bib3] [3] Jørgen Bang-Jensen and Gregory Gutin. Classes of directed graphs, volume 11. Springer, 2018.

[bib.bib4] [4] Jørgen Bang-Jensen, Alessandro Maddaloni, and Saket Saurabh. Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica, 76(2):320–343, 2016. doi:10.1007/S00453-015-0038-2.

[bib.bib5] [5] Jørgen Bang-Jensen and Jing Huang. Quasi-transitive digraphs. J. Graph Theory, 20(2):141–161, 1995. doi:10.1002/JGT.3190200205.

[bib.bib6] [6] Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167–188, 1996.

[bib.bib7] [7] Piotr Berman and Grigory Yaroslavtsev. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Proc. APPROX 2012, volume 7408 of Lecture Notes Comput. Sci., pages 50–60, 2012. doi:10.1007/978-3-642-32512-0_5.

[bib.bib8] [8] Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, and Marcin Wrochna. On directed feedback vertex set parameterized by treewidth. In Proc. WG 2018, volume 11159 of Lecture Notes Comput. Sci., pages 65–78, 2018. doi:10.1007/978-3-030-00256-5_6.

[bib.bib9] [9] Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993–2007, 2001. doi:10.1137/S0097539798338163.

[bib.bib10] [10] Jason Cong. Computing maximum weighted $k$ -families and $k$ -cofamilies in partially ordered sets. Technical Report CSD-930014, University of California, 1993. URL: https://ftp.cs.ucla.edu/tech-report/1993-reports/930014.pdf.

[bib.bib11] [11] Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. doi:10.1007/PL00009191.

[bib.bib12] [12] Michel X Goemans and David P Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 18(1):37–59, 1998. doi:10.1007/PL00009810.

[bib.bib13] [13] Curtis Greene and Daniel J. Kleitman. The structure of Sperner $k$ -families. J. Combinatorial Theory Ser. A, 20(1):41–68, 1976. doi:10.1016/0097-3165(76)90077-7.

[bib.bib14] [14] Sushmita Gupta, Sounak Modak, Saket Saurabh, and Sanjay Seetharaman. Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments. In Proc. LATIN 2024, volume 14578 of Lecture Notes Comput. Sci., pages 225–240, 2024. doi:10.1007/978-3-031-55598-5_15.

[bib.bib15] [15] Venkatesan Guruswami and Euiwoong Lee. Simple proof of hardness of feedback vertex set. Theory Comput., 12(6):1–11, 2016. doi:10.4086/TOC.2016.V012A006.

[bib.bib16] [16] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer, 1972. doi:10.1007/978-1-4684-2001-2_9.

[bib.bib17] [17] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within $2-\varepsilon$ . J. Comput. Syst. Sci., 74(3):335–349, 2008.

[bib.bib18] [18] Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2-approximating feedback vertex set in tournaments. In Proc. SODA 2020, pages 1010–1018, 2020. doi:10.1137/1.9781611975994.61.

[bib.bib19] [19] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Math., 2(3):253–267, 1972. doi:10.1016/0012-365X(72)90006-4.

[bib.bib20] [20] L. Mirsky. A dual of Dilworth’s decomposition theorem. Amer. Math. Monthly, 78:876–877, 1971.

[bib.bib21] [21] Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A $7/3$ -approximation for feedback vertex sets in tournaments. In Proc. ESA 2016, volume 57 of Leibniz Int. Proc. Informatics, pages 67:1–67:14, 2016. doi:10.4230/LIPIcs.ESA.2016.67.

[bib.bib22] [22] M. Sarrafzadeh and R.-D. Lou. Maximum $k$ -covering of weighted transitive graphs with applications. Algorithmica, 9(1):84–100, 1993. doi:10.1007/BF01185340.

[bib.bib23] [23] Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. doi:10.1007/BF01200760.

A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our contributions

Theorem 1.

1.2 Our methodology

2 The triangle graph of quasi-transitive digraphs

Lemma 2.

Proof.

▶ Remark 3.

Proposition 4 (Bang-Jensen and Huang [5]).

Lemma 5.

Proof.

2.1 Perfectness of the triangle graph

Lemma 6.

Proof.

Theorem 7.

Proof.

2.2 Transitive tournaments in the triangle graph

Lemma 8.

Proof.

Lemma 9.

Proof.

Theorem 10.

Proof.

Theorem 11.

Proof.

▶ Remark 12.

2.3 Greene–Kleitman Theorem

Lemma 13.

Lemma 14 ([22]).

3 Revisiting known results: Extensions and simplified proofs

3.1 An exact algorithm for DFVS in 𝓣𝟓-free quasi-transitive digraphs

Theorem 15.

Proof.

3.2 A 𝟕/𝟑-approximation for DFVS in quasi-transitive digraphs

3.3 A deterministic polynomial-time 2-approximation for DFVS in 𝓣𝟕-free quasi-transitive digraphs

4 A 𝟗/𝟒-approximation for DFVS in quasi-transitive digraphs

4.1 Algorithm description

4.2 Algorithm analysis

Lemma 16.

Proof.

Theorem 1 (restated).

Proof.

Case 1.

Case 2.

▶ Remark 2.

5 Discussion

References

A $\nicefrac{{9}}{{4}}$ -Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs

$\blacktriangleright$ Remark 3.

$\blacktriangleright$ Remark 12.

3.1 An exact algorithm for DFVS in ${\cal T}_{5}$ -free quasi-transitive digraphs

3.2 A $\nicefrac{{7}}{{3}}$ -approximation for DFVS in quasi-transitive digraphs

3.3 A deterministic polynomial-time 2-approximation for DFVS in $\mathcal{T}_{7}$ -free quasi-transitive digraphs

4 A $\nicefrac{{9}}{{4}}$ -approximation for DFVS in quasi-transitive digraphs

$\blacktriangleright$ Remark 2.