Computing a Minimum Feedback Vertex Set

Now everything is ready to give the description of the algorithm. Instead of comput-ing a minimum feedback vertex set directly, the algorithm finds the maximum size

of an induced forest in a graph. In fact, it solves a more general problem: for any acyclic setF it finds the maximum size of an induced forest containingF. Let us remark, that the algorithm can easily be turned into an algorithm computing such a set (instead of its cardinality only).

During an execution of the algorithm one vertext∈Fis called theactive vertex.

The algorithm branches on a chosen neighbor of the active vertext. Letv∈N(t).

Denote byKthe set of all vertices ofF other thant that are adjacent tov. LetG⁰ be the graph obtained after the compressioncompress(K∪ {v} →u). We say that a vertexw∈V\ {t}is ageneralized neighborofvinGifwis a neighbor ofuinG⁰. Denote by gd(v)the generalized degreeofvwhich is the number of its generalized neighbors.

For example, in Fig. 6.3, say we haveK={t⁰}. After the compressioncompress(K∪ {v} →u)in the new graph the neighbors ofu(exceptt) arey,z, andw. Thus the gen-eralized degree ofvis 3.

v x

t z w

y

t⁰ x v

t z w

y

Fig. 6.3 Example of compression and generalised degree

The description of the algorithm consists of a sequence of cases and subcases. To avoid a confusing nesting of if-then-else statements let us use the following conven-tion: the first case which applies is used in the algorithm. Thus, inside a given case, the hypotheses of all previous cases are assumed to be false.

Algorithmmif(G,F)computes for a given graphG= (V,E)and an acyclic set F⊆V the maximum size of an induced forest containingF. It is described by the following preprocessing and main procedures. Let us note thatmif(G,/0)computes the maximum size of an induced forest inG.

Preprocessing

1. IfGconsists ofk≥2 connected componentsG₁,G₂, . . . ,G_k, then the algorithm is called on each of the components and

mif(G,F) =

k i=1

∑

mif(G_i,Fi), whereF_i:=V(G_i)∩Ffor alli∈ {1,2, . . . ,k}.

2. IfFis not independent, then apply operationcompress(T→v_T)on an arbitrary non-trivial componentT ofF. IfT contains the active vertex thenv_T becomes active. LetG⁰be the resulting graph and letF⁰be the set of vertices ofG⁰obtained fromF. Then

6.2 Feedback Vertex Set 111 mif(G,F) =mif(G⁰,F⁰) +|T| −1.

Main procedures

1. IfF=V, thenMG(F) ={V}. Thus,

mif(G,F) =|V|. 2. IfF=/0 and∆(G)≤1, thenM^G(F) ={V}and mif(G,F) =|V|.

3. IfF=/0 and∆(G)≥2, then the algorithm chooses a vertextinGof degree at least 2. The algorithm branches on two subproblems—eithertis contained in a maximum induced forest, or not—and returns the maximum:

mif(G,F) =max{mif(G,F∪ {t}), mif(G\ {t},F)}.

4. IfFcontains no active vertex, then choose an arbitrary vertext∈Fas an active vertex. Denote the active vertex bytfrom now on.

5. If there is a vertexv∈N(t)with gd(v)≤1, then addvtoF:

mif(G,F) =mif(G,F∪ {v}).

6. If there is a vertexv∈N(t)with gd(v)≥3, then branch into two subproblems by either selectingvinF or discardingvfromFand removingvfromG:

mif(G,F) =max{mif(G,F∪ {v}), mif(G\ {v},F)}.

7. If there is a vertexv∈N(t)with gd(v) =2 then denote its generalized neighbors byw₁andw₂. Branch by either selectingvinF, or by discardingvfromF and removing it fromGand also selectw₁andw₂inF. If selectingw₁andw₂toF creates a cycle, just ignore the second subproblem.

mif(G,F) =max{mif(G,F∪ {v}),

mif(G\ {v},F∪ {w₁,w₂})}.

Thus the algorithm has three branching rules (casesMain 3, 6and7). The cor-rectness and the running time of the algorithm are analyzed in the following.

Theorem 6.6.The problemFEEDBACKVERTEXSETis solvable in timeO(1.8899ⁿ).

Proof. LetGbe a graph onnvertices. We consider the algorithmmif(G,F) de-scribed above. In what follows, we prove that a maximum induced forest ofGcan be computed in timeO(1.8899ⁿ)by algorithmmif(G,/0). The correctness of Pre-processing 1andMain 1,2,3,4,6is clear. The correctness ofPreprocessing 2follows

from Lemma 6.4. The correctness of casesMain 5,7follows from Lemma 6.5 (in-deed, applying Lemma 6.5 to the vertex u of the graph G⁰ shows that for some X∈ MG(F)eitherv, or at least two of its generalized neighbors are inX).

In order to evaluate the time complexity of the algorithm we use the following measure of an instance(G,F)of a subproblem:

µ(G,F) =|V\F|+c|V\(F∪N(t))|

where the value of the constant cis to be determined later. In other words, each vertex inF has weight 0, each vertex inN(t)has weight 1, each other vertex has weight 1+c, and the size of the instance is equal to the sum of the vertex weights.

Let us note that

µ(G,F)≤(1+c)n.

Thus if we prove that the running time of the algorithm isO^∗(β^µ)for some constant β, then we can estimate the running time byO^∗(β^(1+c)n).

Each of the following (non-branching) reduction steps reduces the size of the problem in polynomial time, and has no influence on the base of the running time of the algorithm:Preprocessing 1,2andMain 1,2,4,5as discussed in Chap. 1.

In all the remaining cases the algorithm branches into smaller subproblems. We consider these cases separately.

In the caseMain 3every vertex has weight 1+c. Therefore, removingvleads to a problem of sizeµ−1−c. Otherwise,vbecomes active after the next Main 4 step. Then all its neighbors become of weight 1, and we obtain a problem of size at mostµ−1−3cbecausevhas degree at least 2. This corresponds to the following recurrence

T(µ)≤T(µ−1−c) +T(µ−1−3c).

In the caseMain 6removing the vertexvdecreases the size of the problem by 1. If vis added toF then we obtain a non-trivial component inF, which is contracted into a new active vertext⁰at the next Preprocessing 2 step. Those of the generalized neighbors ofvthat are of weight 1 will be connected tot⁰by multiedges and thus removed during the next Preprocessing 2 step. If a generalized neighbor ofvis of weight 1+c, then it will become a neighbor oft⁰, i.e. of weight 1. Thus, in any case the size of the problem is decreased by at least 1+3c. So, we have that in this case

T(µ)≤T(µ−1) +T(µ−1−3c).

In the caseMain 7 we distinguish three subcases depending on the weights of the generalized neighbors ofv. Let ibe the number of generalized neighbors ofv of weight 1+c. AddingvtoFreduces the weight of a generalized neighbor either from 1 to 0 or from 1+cto 1. Removingvfrom the graph reduces the weight of both generalized neighbors ofvto 0 (since we add them toF). According to this, we obtain three recurrences, for eachi∈ {0,1,2},

T(µ)≤T(µ−(3−i)−ic) +T(µ−3−ic).

6.3 Dominating Set 113