A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion

Split Vertex Deletion

Daniel Lokshtanov

University of California, Santa Barbara, CA, USA [email protected]

Pranabendu Misra

Max Planck Institut für Informatik, Saarland Informatics Campus, Saarbrücken, Germany [email protected]

Fahad Panolan

IIT Hyderabad, India [email protected]

Geevarghese Philip

Chennai Mathematical Institute, UMI ReLaX, Chennai, India [email protected]

Saket Saurabh

Institute of Mathematical Sciences, Chennai, India University of Bergen, Norway

[email protected]

Abstract

In theSplit Vertex Deletion (SVD)problem, the input is ann-vertex undirected graphGand a weight functionw:V(G)→N, and the objective is to find a minimum weight subsetS of vertices such thatG−S is a split graph (i.e., there is bipartition ofV(G−S) =C]I such thatC is a clique andI is an independent set inG−S). This problem is a special case of 5-Hitting Setand consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2−δ)-approximation algorithm, for any fixedδ >0, unless the Unique Games Conjecture fails.

We start by giving a simple quasipolynomial time (n^O(logn)) factor 2-approximation algorithm forSVDusing the notion ofclique-independent set separating collection. Thus, on the one handSVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: CanSVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for anyε >0, there is an^O(log1ε)-time 2(1 +ε)-approximation algorithm.

2012 ACM Subject Classification Theory of computation →Design and analysis of algorithms;

Theory of computation→Approximation algorithms analysis

Keywords and phrases Approximation Algorithms, Graph Algorithms, Split Vertex Deletion

Digital Object Identifier 10.4230/LIPIcs.ICALP.2020.80

Category Track A: Algorithms, Complexity and Games

Funding This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (via grant no. 819416 and no.

715744), the Norwegian Research Council(via grants MULTIVAL and CLASSIS), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

EATCS

© Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh;

licensed under Creative Commons License CC-BY

1 Introduction

TheHitting Setproblem encompasses a large number of well studied problems in Computer Science. Here, the input is a familyF of sets over ann-element universeU and a weight functionw: U →N, and the objective is to compute a hitting set of minimum weight. A hitting set is a subsetS ⊆U such that for anyF ∈ F, F∩S 6=∅ and the weight ofS is w(S) =P

u∈Sw(u). This problem generalizes a number of other well studied problems in computer science, and consequently it is very hard to approximate: it can not be approximated within a factor 2^{log1−δc(n)n} in polynomial time, for any constant c <1/2, unlessSAT can be decided in slightly subexponential time, whereδ_c(n) = 1/(log logn)^c [11]. A restricted version of this problem, is thed-Hitting Set problem, whered∈Nand the cardinality of every set in F is at most d. This problem also generalizes a number of well studied problems, and it admits a simple factord-approximation algorithm: Solve the natural LP relaxation and select all elements whose corresponding variable in the LP is set to at least 1/d. Unfortunately, this simple algorithm is likely to be the best possible. That is, assuming Unique Game Conjecture (UGC), there is noc-factor approximation algorithm ford-Hitting Set, for anyc < din the general case [7].

A number of vertex deletion problems on graphs can be considered as special cases of d-Hitting Set, and it is of great interest to devise factor-αapproximation algorithm for them where α < d, or rule out any such algorithm. For example, in the Vertex Cover problem, the input is a graph G and a weight function w:V(G) → N, and the objective is to find a subset of vertices of minimum weight that hits all edges inG. This is same as 2-Hitting Set, and assuming the Unique Games Conjecture we cannot do better than a factor-2 approximation in polynomial time. However, there are other examples of vertex deletion problems on graphs, that are special cases of d-Hitting Set, for which we can indeed do better than a factor-dapproximation. Consider theCluster Vertex Deletion problem, where the input is a graphG and a weight functionw:V(G)→ N, and the objective is to find a minimum weight subsetS of vertices such thatS is a cluster graph. Equivalently,S hits all induced paths of length 3 inG. Hence, it is a special case of 3-Hitting Setand admits a simple 3-approximation algorithm. You et al. [13] showed that the unweighted version of Cluster Vertex Deletionadmits a 5/2 approximation algorithm. Recently, this was improved to factor 9/4 by Fiorini et al. [5]. The problem also admits an approximation-preserving reduction fromVertex Coverand hence there is a lower bound of 2 on the approximation-factor assuming UGC [5]. Fiorini et al. [5]

have conjectured thatCluster Vertex Deletionadmits a 2-approximation algorithm.

Another example is theTournament Feedback Vertex Set (TFVS) problem, which is equivalent to hitting all directed triangles in a digraph. It is very well studied in the realm of approximation algorithms [3, 1, 10, 9], and very recently a 2-approximation algorithm was designed by Lokshtanov et al. [9], matching the lower-bound under UGC [12]. Similarly, a number of such “implicit”d-Hitting Setproblems are studied in Computer Science, and it is of great interest to settle their approximation complexity.

In this work we study another implicitd-Hitting Setproblem calledSplit Vertex Deletion(SVD)(defined below). A subset S of vertices in a graph G is a split vertex deletion set ifG−S is a split graph (i.e., there is bipartition ofV(G−S) =C]Isuch that Cis a clique and Iis an independent set in G−S).

Split Vertex Deletion(SVD)

Input: An undirected graphGand a weight function w:V(G)→N.

Output: A split vertex deletion setS⊆V(G) ofGof the smallest weight (an optimum split vertex deletion set ofG).

A graphGis a split graph if and only if it does not containC4, C5and 2K2as induced subgraphs in G [6]. This implies thatSVD is special case of 5-Hitting Set and hence it admits a simple 5-approximation algorithm. Furthermore, it is interesting to note that we can obtain a 2-approximation algorithm forSVD in timen^O(logn) using the notion of clique-independent set separating collection [4]. For a graph G, a clique-independent set separating collection is a familyC of vertex subsets ofV(G) such that for a cliqueC and an independent set IinGsuch that C∩I=∅, there is subset X in the collectionC such thatC⊆X andI⊆V(G)\X. Thus, if there is a “small” clique-independent set separating collection, then we can enumerate such a collectionC and solveVertex Cover ofG[X]

and G−X for eachX ∈ C. Notice that for any X ∈ C, the union of the two solutions of the two Vertex Cover instances on G[X] and G−X, respectively, is a solution to SVD. Moreover, the bestc-approximation solutions over all choices ofX, is ac-approximate solution of SVD. It is known that for anyn-vertex graph, there is clique-independent set separating collection of sizen^O(logn)and this can be enumerated in time linear in the size of the collection [4]. This along with a 2-approximation algorithm of Vertex Coverleads to ann^O(logn)-time 2-approximation algorithm for SVD. There is also a simple approximation preserving reduction fromVertex Coverto SVD, which shows that we cannot improve upon factor 2-approximation algorithm, unless UGC fails. The reduction is as follows: Given an instance (G, w) of Vertex Cover, we add a large complete graphH of size 2|V(G)|

intoGwith weight of each vertex inH to be max{w(u) : u∈V(G)}. One can easily verify that this is an approximation preserving reduction.

Thus, on the one hand SVD admits a 2-approximation in quasipolynomial (n^O(logn)) time, and on the other hand this approximation factor cannot be improved assuming UGC.

It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? This is precisely the question we address in this paper, and obtain the following result.

ITheorem 1. LetGbe a graph onn vertices,wa weight function onV(G)and letε >0 be a constant. Then there exists a randomized algorithm that runs in time O(n^g(ε)) and outputs S ⊆ V(G) such that G−S is a split graph and w(S) ≤ 2(1 +ε)w(OP T) with probability at least1/2. Here OP T is a minimum weight split vertex deletion set of G, and g(ε) = 6 + 8 log(80(1 +¹²_ε))·log(³⁰_ε)/log(4/3).

Overview of Theorem 1. At a very high level the algorithm described in Theorem 1 is inspired from the algorithm developed for factor 2-approximation algorithm for TFVS [9].

In TFVS knowing just one vertex is sufficient to completely split the instance into two independent sub-instances and thus leading to a natural divide and conquer scheme. However, in our case (SVD) the instances don’t become truly independent before every vertex is classified as either potential clique orpotential independent set vertex. Classifying all the vertices requires several new ideas and insights in the problem. This classification could be vaguely viewed as a polynomial time algorithm that quickly navigates through sets in clique-independent set separating collectionC, and almost reaches a correct partition.

Our algorithm in fact finds a (2 +ε)-factor approximate solution for a more general annotatedvariant of the problem, where the solution must obey certain additional constraints.

Annotated Split Vertex Deletion(A-SVD)

Input: An undirected graphG, a weight functionw: V(G)→N, and a partition of V(G) into three partsV(G) =C]I]U, where at most two of these parts may be empty.

Output: A setS^?⊆V(G) of Gof the smallest weight such thatG−S^?is a split graph with a split partition (C^?, I^?) whereC^?⊆(C∪U) andI^?⊆(I∪U) hold.

Afeasible solution to an instance (G, w,(C, I, U)) of Annotated Split Vertex Dele- tionis a split vertex deletion setS ofGsuch that the split graphG−S has a split partition (C⁰, I⁰) where no vertex in the specified setI goes to the split partC⁰ and no vertex in the specified setC goes to the independent part I⁰. Thus, each vertex in the setI is either deleted as part ofS or ends up in the independent setI⁰ in graphG−S, and each vertex in Cis either deleted or ends up in the clique C⁰ inG−S. There are no restrictions on where the vertices in the “unconstrained” setU may go. We call a feasible solution of A-SVDan annotated split vertex deletion set of the instance (G, w,(C, I, U)); theA-SVDproblem asks

for anoptimum annotated split vertex deletion set of the input instance.

First we show that we can, in polynomial time, find 2-factor approximate solutions toA- SVDinstances which are of the form (G, w,(C, I, U =∅)) ( Lemma 12). Let (G, w,(C, I, U)) be an instance of A-SVD, letOP T be an (unknown) optimum solution to (G, w,(C, I, U)), let (C^? ⊆(C∪U), I^? ⊆(I∪U)) be a split partition ofG−OP T, and let C_U^? = (C^?∩ U), I_U^? = (I^?∩U). We show that ifw(C_U^? \ {c^?})≤ ^{ε·w(OP T)}₂ holds for some c^? ∈C_U^? or w(I_U^?\{i^?})≤^{ε·w(OP T)}₂ holds for somei^?∈I_U^? then we can, in polynomial time, find a (2+ε)- factor approximate solution to (G, w,(C, I, U)) (Lemma 16, Lemma 18). These constitute the base cases of our algorithm. It is not difficult to see that moving a vertexx∈C_U^? to the setC and moving a vertexy∈I_U^? to the setIare approximation-preserving transformations.

At a high level, our algorithm starts with an arbitrary instance (G, w,(C, I, U)) of A-SVD, correctly identifies – with a constant probability of success – a good fraction of vertices which belong to the setsC_U^? orI_U^?, and moves these vertices to the setsC orI, respectively. It then recurses on the resulting instance, till it reaches one of the base cases described above.

We now briefly and informally outline how our algorithm identifies vertices as belonging toC_U^? or I_U^?. Consider the bipartite subgraph H ofGinduced by the pair (C_U^?, I_U^?). Define the weight of an edge to be the product of the weights of its two end-points, and suppose the total weight of edges inH is at least half the maximum possible weight. Then each of a constant fraction (by weight) of the vertices inI_U^? has a constant fraction (by weight) ofC_U^? in its neighborhood (Lemma 4). If we can identify one of these special vertices ofI_U^? then we can safely move all its neighbors inU to the setC while reducing the weight of C_U^? by a constant fraction. The catch, of course, is that we have no idea what the setI_U^? is.

To get around this, we find an approximate solutionX of theSplit Vertex Deletion instance defined by the induced subgraphG[U]. Let (CX, IX) be a split partition ofG−X. We show that we can, in polynomial time and with constant probability, sample a vertex from the setX∪(I_X\C_U^?) (Lemma 26). We further show that the weight ofX∪(I_X\C_U^?) is at most aconstant multipleof the weight of I_U^? (Lemma 22). So if I_U^? ⊆(X∪(IX\C_U^?)) holds then we can, with good probability, sample a vertex from the setI_U^?. The hard part is when this condition does not hold. We show using a series of lemmas (summarized in Lemma 25) that we can, even in this case, sample a vertex from one of the two setsC_U^?, I_U^? with constant probability. A symmetric analysis applies when the total weight ofnon-edges across (C_U^?, I_U^?) is at least half the maximum possible weight.

2 Preliminaries

We use]to denote the disjoint union of sets. Moreover, when we writeX]Y we implicitly assert that the setsX andY are disjoint. We useV(G) (respectively,E(G)) to denote the vertex set (respectively, the edge set) of graphG. For a subsetS ⊆V(G) of vertices ofGwe useG[S] to denote the subgraph ofGinducedbyS andG−S to denote the subgraph of Gobtained by deleting all vertices in S (and their incident edges) fromG. Anon-edge in

a graphGis any 2-subset {x, y} ⊆V(G) of vertices such that xyis not an edge inG. For the sake of brevity we use the notationxy to denote a non-edge{x, y}. For a finite setU, weight functionw:U →N, and subset X ⊆U we usew_X to denote the weight functionw restricted to the subset X, and w(X) to denote the sum P

x∈Xw(x) of weights of all the elements in X. For the sake of brevity we drop the subscriptX from the expressionw_X when there is no risk of ambiguity.

The operation of sampling (or picking) proportionately at random fromU according to the weight function w chooses one element fromU, where each element x∈U is chosen with probabilityw(x)/w(U). We useGto denote thecomplement of a graphG, defined as follows: The vertex set ofGisV(G). For every two vertices{u, v} ⊆V(G) there is an edge uvinGif and only ifuvisnotan edge in graphG. Avertex cover of graph Gis any subset S⊆V(G) of its vertex set such that the graphG−S has no edges. Aclique in graphGis any non-empty subsetS⊆V(G) of its vertex set such that (i)|S|= 1, or (ii) if|S| ≥2 then for every two verticesu, v inS, the edgeuvis present in graphG.

IObservation 2. For an undirected graphGand anyS⊆V(G), the vertex set V(G)\S is a clique in Gif and only ifS is a vertex cover of the complement graphG.

For a graphGand two disjoint vertex subsets X, Y ⊆V(G) ; X∩Y =∅ the bipartite subgraph ofGinduced by the pair(X, Y) has vertex setX∪Y and edge set{xy|x∈X, y∈ Y, xy ∈E(G)}. Note that the bipartite subgraph ofGinduced by the pair (X, Y) is not necessarily identical to the subgraphG[X∪Y] induced by the subset X∪Y, and is defined even if the induced subgraphG[X∪Y] is not bipartite. For a bipartite graphH with vertex bipartition V(H) = V1]V2 we define E(H\) = {v1v2 |v1 ∈ V1, v2 ∈ V2, v1v2 ∈/ E} to be the set of allnon-edgesof H with one end inV1 and the other end in V2. Further, for a weight functionw:V(H)→Ndefined on the vertex set of a bipartite graphH we define the weight of its edge set to bew(E(H)) =P

v₁v₂∈E(H)(w(v1)·w(v2)) and the weight of its set of non-edges to bew(E(H)) =\ P

v1v2∈\E(H)(w(v1)·w(v2)).

IDefinition 3. Let Gbe an undirected graph and w: V(G) →Na weight function. Let X, Y be two disjoint vertex subsets ofGand letH be the bipartite subgraph of Ginduced by the pair (X, Y). Let w(E(H)) andw(E(H\))be defined as above. We say that (X, Y) is a heavy pairifw(E(H))≥ ^w(X)·w(Y₂ ⁾ holds, and is a light pairifw(E(H))\ ≥ ^w(X)·w(Y₂ ⁾ holds.

ILemma 4(♣). ¹ Let H = (V, E)be a bipartite graph, let V =V₁]V₂ be a bipartition of H, and let w:V(H)→N be a weight function. Then(V1, V2)is either a heavy pair or a light pair. Moreover,

1. Suppose(V₁, V₂)is a heavy pair, and letX ={x∈V₁|w(N(x))≥^w(V₄²⁾} be the set of all vertices xin the setV1 such that the total weight of the neighborhood of xin the set V₂ is at least one-fourth the total weight of the set V₂. Then w(X)> ^w(V₄¹⁾.

2. Suppose(V1, V2)is a light pair, and letY ={y∈V1|w(V2\N(y))≥^w(V₄²⁾} be the set of all vertices y in the set V₁ such that the total weight of thenon-neighbors ofy in the setV2 is at least one-fourth the total weight of the set V2. Thenw(Y)> ^w(V₄¹⁾.

For a graphGgiven together with a weight functionw:V(G)→N, anoptimum vertex cover ofGis any vertex cover ofGwith the least total weight.

1 Proofs of statements labeled with a♣will appear in the full version of the paper.

Weighted Vertex Cover(wVC)

Input: An undirected graphGand a weight function w:V(G)→N. Output: An optimum vertex coverS⊆V(G) ofG

ITheorem 5([2]). There is an algorithm which, given an instance(G, w)of Weighted Vertex Coveras input, runs inO(|E(G)|)time and outputs a vertex cover S ofGwhose weight is at most twice the weight of an optimum vertex cover ofG.

3 The Algorithm

Let (G, w) be an instance of Split Vertex Deletion. Since deleting vertices conserves the property of being a split graph one can safely add zero-weight vertices to any split vertex deletion set. So we assume without loss of generality thatw(v)≥1 holds for everyv∈V(G).

Split Vertex DeletionisNP-complete by the meta-result of Lewis and Yannakakis [8], and has a simple 5-factor approximation algorithm based on the Local Ratio Technique.

ITheorem 6 (♣). There is a deterministic algorithm which, given an instance(G, w)of SVD, runs in O(|V(G)|⁶) time and outputs a split vertex deletion setS⊆V(G)of Gsuch that w(S)≤5·w(OP T)whereOP T is an optimum split vertex deletion set of G.

We describe a randomized polynomial-time algorithm which outputs a (2 +ε)-factor approximate solution for this problem for any fixedε >0.

Note that in an instance (G, w,(C, I, U)) of Annotated Split Vertex Deletionthe setC is not necessarily a clique, nor isI necessarily an independent set inG. But we have the following.

IObservation 7. Let S be a feasible solution of anA-SVD instance(G, w,(C, I, U)) and let(C⁰, I⁰)be a split partition of G−S whereC⁰ ⊆(C∪U) and I⁰ ⊆(I∪U) hold. Then C\S⊆C⁰ and I\S⊆I⁰ hold. Hence C\S is a clique in GandI\S is an independent set inG.

From Observations 2 and 7 we get

ICorollary 8. LetS be a feasible solution of anA-SVDinstance(G, w,(C, I, U)). LetV CC

be an optimum solution of the wVC instance(G[C], w)and letV CI be an optimum solution of the wVCinstance (G[I], w). Thenw(V CC)≤w(S∩C)andw(V CI)≤w(S∩I)hold.

A-SVDis clearly a generalization of SVD: Given an instance (G, w) of SVD, construct the instance (G, w,(C =∅, I =∅, U =V(G))) of A-SVD. Every split vertex deletion set of graphGis a feasible solution of theA-SVDinstance, and every annotated split vertex deletion set of (G, w,(∅,∅, V(G))) is a split vertex deletion set of graph G. It follows that for any constant c, a c-factor approximate solution to the A-SVDinstance is a c-factor approximate solution to theSVDinstance as well.

We can find feasible solutions to an A-SVD instance (G, w,(C, I, U)) by computing vertex covers for certain pairs of subgraphs derived fromG.

IObservation 9 (♣). Let (G, w,(C, I, U))be an instance of A-SVD.

1. LetV1 be a vertex cover of the graphG[I]U] and letV2 be a vertex cover of the graph G[C]. ThenV₁]V₂ is a feasible solution to (G, w,(C, I, U)).

2. Let V₃ be a vertex cover of the graph G[I] and let V₄ be a vertex cover of the graph G[C]U]. Then V3]V4 is a feasible solution to(G, w,(C, I, U)).

I

C

U

U

I

C

I

C

I

C

C

I

U

X

C

∩ C I

∩ I

Figure 1Illustration of Definition 13.

IObservation 10 (♣). Let (G, w,(C, I, U))be an instance of A-SVD and letu∈U.

1. Let V1 be a vertex cover of the graphG[I](U \ {u})]and let V2 be a vertex cover of the graph G[C∪ {u}]. Then V₁]V₂ is a feasible solution to (G, w,(C, I, U)).

2. Let V3 be a vertex cover of the graphG[I∪ {u}]and letV4 be a vertex cover of the graph G[C](U\ {u})]. ThenV₃]V₄ is a feasible solution to (G, w,(C, I, U)).

Observation 9 has some interesting consequences. For instance, it implies that when the

“unconstrained” setU in anA-SVDinstance isempty, an optimum solution to theA-SVD instance corresponds to optimum solutions of twoWeighted Vertex Cover instances derived from theA-SVD instance in a natural fashion.

ILemma 11(♣). LetS^?be an optimum solution to anA-SVDinstance(G, w,(C, I, U =∅)).

Then the set(S^?∩I) is an optimum solution to thewVC instance (G[I], w), and the set (S^?∩C) is an optimum solution to thewVCinstance (G[C], w).

This in turn implies that given anA-SVD instance in which the unconstrained setU is empty, we can find a 2-factor approximate solution to the instance in polynomial time.

I Lemma 12 (♣). There is a deterministic algorithm that finds a 2-factor approximate solution to an A-SVDinstance that is of the form(G, w,(C, I, U =∅)), inO(|E(G)|)time.

This idea generalizes as follows. LetOP T be an optimum solution to anA-SVDinstance (G, w,(C, I, U)). Suppose the split graphG−OP T has a split partition (C^?, I^?) such that vertices from the unconstrained setU contribute a small weightto either the cliqueC^? or the independent setI^?. Then a variant of the algorithm in the proof of Lemma 12 yields a small-factor approximate solution to the instance, in polynomial time. We state this formally in Lemma 16 below, for which we need some notation (see Figure 1).

IDefinition 13. Let(G, w,(C, I, U))be an instance ofA-SVD, and letε≥0 be a constant.

Let OP T ⊆ V(G) be an optimum solution of (G, w,(C, I, U)) and let (C^?, I^?) be a split partition of the split graph G^? = (G−OP T) such that C^? ⊆ (C∪U) and I^? ⊆ (I∪U) hold. Let C_U^? = (C^?∩U)be the set of vertices from the unconstrained set U which become part of the clique C^? and let I_U^? = (I^?∩U) be the set of vertices from U which become part of the independent set I^? in G^?. Let UOP T = (U ∩OP T), COP T = (C∩OP T) and IOP T = (I∩OP T).

Further, let X be a 5-factor approximate solution of the Split Vertex Deletion instance (G[U], wU) defined by the induced subgraph G[U], and let (CX, IX) be a split partition of the split graphG[U]−X.

I Remark 14. Given an instance (G, w,(C, I, U)) of A-SVD we can, using Theorem 6, compute such a setX and partition (C_X, I_X) in polynomial time.

IObservation 15(♣). Let(G, w,(C, I, U)), X, IX, CX, I_U^?, C_U^? be as in Definition 13. Then both |I_U^? \(X∪(I_X\C_U^?))| ≤1 and|C_U^? \(X∪(C_X\I_U^?))| ≤1 hold.

ILemma 16 (♣). Let (G, w,(C, I, U)), ε, OP T, C_U^?, I_U^? be as in Definition 13. Let S1 be a 2-factor approximate solution for the wVC instance (G[I∪U], w) and S₂ a 2-factor approximate solution for the wVC instance (G[C], w). Let S12 = (S1∪S2). Let S3 be a 2-factor approximate solution for the wVC instance (G[C∪U], w) and S₄ a 2-factor approximate solution for the wVCinstance (G[I], w). LetS34= (S3∪S4). Then the sets

S₁₂ andS₃₄ can be computed inO(|E(G)|) time. Further,

1. If w(C_U^?)≤ ^{ε·w(OP T)}₂ holds then the setS12 is a(2 +ε)-factor approximate solution for the Annotated Split Vertex Deletioninstance(G, w,(C, I, U)).

2. If w(I_U^?)≤ ^{ε·w(OP T)}₂ holds then the setS₃₄ is a(2 +ε)-factor approximate solution for the Annotated Split Vertex Deletioninstance(G, w,(C, I, U)).

IRemark 17. Note that these two cases are neither exclusive nor exhaustive.

By repeatedly applying the procedure in the proof of Lemma 16 and taking the minimum, we can find a (2 +ε)-factor approximate solution in polynomial time even in the more general case where there is at most one “heavy” vertex inC_U^? or I_U^? that

ILemma 18 (♣). Let (G, w,(C, I, U)), ε, OP T, C_U^?, I_U^? be as in Definition 13. For each vertex u ∈ U let S₁^u be a 2-factor approximate solution for the wVC instance (G[I ∪ (U\ {u})], w),S₂^u a 2-factor approximate solution for the wVC instance (G[C∪ {u}], w), and let S^u₁₂ =S₁^u∪S₂^u. Let S₃^u be a 2-factor approximate solution for the wVC instance (G[C∪(U\ {u})], w), S₄^u a 2-factor approximate solution for the wVC instance (G[I∪ {u}], w), and let S₃₄^u =S₃^u∪S₄^u. Finally, let S^† be a set of the formS₁₂^u of the minimum weight and letS^‡ be a set of the form S₃₄^u of the minimum weight, both minima taken over all vertices u∈U.

The setsS^† andS^‡ can be computed inO(|V(G)| · |E(G)|)time. Further,

1. Ifw(C_U^?\{c^?})≤ ^{ε·w(OP T)}₂ holds for some vertexc^?∈C_U^? then the setS^†is a(2+ε)-factor approximate solution for theA-SVD instance(G, w,(C, I, U)).

2. Ifw(I_U^?\ {i^?})≤^{ε·w(OP T)}₂ holds for some vertexi^?∈I_U^? then the setS^‡ is a(2 +ε)-factor approximate solution for theA-SVD instance(G, w,(C, I, U)).

IRemark 19. Note that these two cases are neither exclusive nor exhaustive.

IDefinition 20. Let(G, w,(C, I, U)), ε, OP T, C^?, I^?, C_U^?, I_U^? be as in Definition 13. We say that(G, w,(C, I, U))is an easy instance ifU =∅ holds, or if at least oneof the following holds: (i)w(C_U^?)≤ ^{ε·w(OP T)}₂ , (ii) w(I_U^?)≤ ^{ε·w(OP T}₂ ⁾, (iii) w(C_U^? \ {c^?})≤ ^{ε·w(OP T)}₂ holds for some vertexc^?∈C_U^?, (iv) w(I_U^? \ {i^?})≤ ^{ε·w(OP T)}₂ holds for some vertex i^? ∈I_U^?. We say that(G, w,(C, I, U))is a hardinstance otherwise.

From Lemma 12, Lemma 16 and Lemma 18 we get

ICorollary 21. There is an algorithm which, given an easy instance (G, w,(C, I, U)) of A-SVDand a constant ε >0as input, computes a (2 +ε)-factor approximate solution for (G, w,(C, I, U))in deterministic polynomial time.

ILemma 22(♣). Let (G, w,(C, I, U))be a hardinstance ofA-SVDand letε, C_U^?, I_U^?, X, IX, CX be as in Definition 13. Then the following hold:

1. w(X∪(IX\C_U^?))<(1 +¹²_ε)·w(I_U^?) 2. w(X∪(CX\I_U^?))<(1 +¹²_ε)·w(C_U^?)

Recall the notion of heavy and light pairs from Definition 3.

ILemma 23(♣). Let(G, w,(C, I, U))be ahardinstance ofA-SVDand letε, OP T, C^?, I^?, C_U^?, I_U^? be as in Definition 13. Suppose (I_U^?, C_U^?) is a heavy pair. Let I = {v ∈ I_U^? ; w(N(v)∩C_U^?) ≥ ^w(C₄^U?)} be the set of vertices in I_U^? which have a “heavy” neigh- borhood in C_U^?, and let i be a heaviest vertex in I, i.e. a vertex of maximum weight.

Let C = {v ∈ C_U^? ; w((I_U^? \ {i})\(N(v)∩I_U^?)) ≥ ^w(IU?\{i₄ ^})} be the set of vertices in C_U^? which have a “heavy” non-neighborhood in the subset I_U^? \ {i}, and let c be a heaviest vertex inC. LetI={v∈(I_U^? \ {i}) ; w(N(v)∩(C_U^? \ {c}))≥ ^w(CU?\{c₄ ^})} be the set of vertices inI_U^? \ {i} which have a “heavy” neighborhood inC_U^? \ {c}, and let C={v∈(C_U^? \ {c}) ; w((I_U^? \ {i})\(N(v)∩I_U^?))≥^w(IU?\{i₄ ^})} be the set of vertices in(C_U^? \ {c})which have a “heavy” non-neighborhoodinI_U^? \ {i}.

Then at least one of the following statements holds:

(1a) Picking a vertex proportionately at random from the set X∪(IX\C_U^?) yields a vertex v∈I with probability at least 1/(20(1 +¹²_ε)).

(1b) Picking a vertex proportionately at random from the setX∪(IX\C_U^?)yields a vertex v∈I with probability at least1/(4(1 +¹²_ε)).

(2a) Picking a vertex proportionately at random from the set X∪(CX\I_U^?) yields a vertex v∈C with probability at least 1/(20(1 +¹²_ε)).

(2b) Picking a vertex proportionately at random from the setX∪(CX\I_U^?)yields a vertex v∈C with probability at least1/(4(1 +¹²_ε)).

ILemma 24(♣). Let(G, w,(C, I, U))be ahardinstance ofA-SVDand letε, OP T, C^?, I^?, C_U^?, I_U^? be as in Definition 13. Suppose (I_U^?, C_U^?)is a light pair. LetC^k={v∈C_U^? ; w(I_U^? \ (N(v)∩I_U^?))≥ ^w(I₄^U?)}be the set of vertices in C_U^? which have a “heavy” non-neighborhood in I_U^?, and letc^k be a heaviest vertex in C^k. Let I^k={v ∈I_U^? ; w(N(v)∩(C_U^? \ {c^k}))≥

w(C_U^?\{c^k})

4 } be the set of vertices in I_U^? which have a “heavy” neighborhood in the subset C_U^? \ {c^k}, and leti^k be a heaviest vertex inI^k. LetC^‡={v∈(C_U^? \ {c^k}) ; w((I_U^? \ {i^k})\ (N(v)∩I_U^?))≥ ^w(I?U\{i₄ ^k})} be the set of vertices in C_U^? \ {c^k} which have a “heavy” non-

neighborhoodinI_U^?\{i^k}, and letI^‡ ={v∈(I_U^?\{i^k}) ; w(N(v)∩(C_U^?\{c^k}))≥ ^w(CU?₄^\{ck})} be the set of vertices in(I_U^? \ {i^k})which have a “heavy” neighborhood inC_U^? \ {c^k}.

Then at least one of the following statements is true.

(1a) Picking a vertex proportionately at random from the set X∪(CX\I_U^?) yields a vertex v∈C^k with probability at least 1/(20(1 +¹²_ε)), or

(1b) Picking a vertex proportionately at random from the setX∪(CX\I_U^?)yields a vertex v∈C^‡ with probability at least1/(4(1 +¹²_ε)).

(2a) Picking a vertex proportionately at random from the set X∪(IX\C_U^?) yields a vertex v∈I^k with probability at least 1/(20(1 +¹²_ε)), or

(2b) Picking a vertex proportionately at random from the setX∪(IX\C_U^?)yields a vertex v∈I^‡ with probability at least1/(4(1 +¹²_ε)).

From Lemma 23 and Lemma 24 we get

ILemma 25. Let(G, w,(C, I, U))be ahardinstance ofA-SVDand letε, OP T, C^?, I^?, C_U^?, I_U^? be as in Definition 13. Then one of the following statements is true.

(1a) Picking a vertex proportionately at random from X∪(I_X\C_U^?) yields a vertex from {v∈I_U^? |w(N(v)∩C_U^?)≥^w(C₄^U?)}with probability at least 1/20(1 +¹²_ε).

(1b) Picking a vertex proportionately at random from X∪(I_X\C_U^?)yields a vertex from {v∈I_U^? |w(N(v)∩(C_U^? \ {c^?}))≥ ^w(CU?₄^\{c?})} with probability at least1/20(1 +¹²_ε), for some vertex c^?∈C_U^?.

(2a) Picking a vertex proportionately at random from X∪(C_X\I_U^?) yields a vertex from {v∈C_U^? |w(I_U^? \N(v))≥ ^w(I₄^U?)} with probability at least1/20(1 +¹²_ε).

(2b) Picking a vertex proportionately at random from X∪(CX\I_U^?)yields a vertex from {v∈C_U^? |w((I_U^? \ {i^?})\N(v))≥ ^w(I?U\{i₄ ^?})}with probability at least 1/20(1 +¹²_ε), for some vertex i^?∈I_U^?.

Proof. From Lemma 4 we get that (I_U^?, C_U^?) is either a heavy pair or a light pair. If (I_U^?, C_U^?) is a heavy pair then Lemma 23 applies, and at least one of the four options of that lemma holds. Option(1a)of Lemma 23 implies option(1a) of the current lemma. Option(1b)of Lemma 23 implies option(1b)of the current lemma. Options(2a)and(2b)of Lemma 23 both imply option(2b)of the current lemma.

If (I_U^?, C_U^?) is a light pair then Lemma 24 applies, and at least one of the four options of that lemma holds. Option(1a)of Lemma 24 implies option(2a)of the current lemma.

Option(1b)of Lemma 24 implies option(2b)of the current lemma. Options(2a)and(2b) of Lemma 24 both imply option(1b)of the current lemma.

Thus in every case, one of the four options of the current lemma holds. J ILemma 26(♣). Let(G, w,(C, I, U))be ahardinstance ofA-SVDand letε, OP T, C^?, I^?, C_U^?, I_U^? be as in Definition 13.

1. There is a randomized polynomial-time algorithm which, given (G, w,(C, I, U))as input, picks a vertex proportionately at random from the set X ∪(I_X \C_U^?) with probability at least ¹₂. That is, the algorithm runs in polynomial time and outputs a vertexv, and the following hold with probability at least ¹₂: (i) v ∈X∪(I_X \C_U^?), and (ii) for any x∈(X∪(IX\C_U^?)),P r[v=x] =w(x)/w(X∪(IX\C_U^?)).

2. There is a randomized polynomial-time algorithm which, given (G, w,(C, I, U))as input, picks a vertex proportionately at random from the set X ∪(CX \I_U^?) with probability at least ¹₂. That is, the algorithm runs in polynomial time and outputs a vertexv, and the following hold with probability at least ¹₂: (i) v ∈X∪(C_X\I_U^?), and (ii) for any x∈(X∪(CX\I_U^?)),P r[v=x] =w(x)/w(X∪(CX\I_U^?)).

3.1 Polynomially Bounded Weights

Let us first consider instances (G, w) of SVD which have polynomially bounded weights.

Letn=|V(G)|. Recall thatw(v)≥1 holds for each vertexv ofG. We say that the weight functionwis polynomially bounded if, in addition, P

v∈V(G)w(v)≤c₁n^c0 holds for every v∈V(G) and some constants c0, c1. For such instances we have the following theorem.

ITheorem 27. There exists a randomized algorithm that given a graph G, a polynomially bounded weight function wonV(G)and ε >0, runs in timeO(n^f(ε))and outputsS ⊆V(G) such thatG−S is a split graph and w(S)≤(2 +ε)w(OP T) with probability at least 1/2, whereOP T is a minimum weight split vertex deletion set ofG. Here,f(ε) = 6 + log(80(1 +

12

ε))·4c0log(c1)/log(4/3), wherec0, c1 are constants such that w(V(G))≤c1·n^c0.

Algorithm 1Approximation algorithm for the case of polynomially bounded weights.

Input: An instance (G, w,(C, I, U)) of A-SVD, a tuples (β₁^C, β₂^C, β₁^I, β₂^I) andε >0.

Output: A (2 +ε)-factor approximate solution to (G, w,(C, I, U)).

1: procedure ASVD-Approx((G, w,(C, I, U)), ε, β^C₁, β^C₂, β^I₁, β₂^I)) 2: if U =∅ then

3: Compute a 2-approximation S using Lemma 12 4: returnS

5: end if

6: X ←5-approximate solution to (G[U], w) from Theorem 6

7: I_X, C_X ←the independent set and the clique in the split partition ofG[U]−X.

8: Compute the setsS12andS34as described in Lemma 16.

9: Compute the setsS^† andS^‡ as described in Lemma 18.

10: if β₁^C≥0 andβ₂^C≥0 andβ₁^I ≥0 andβ₂^I ≥0then

11: for allj∈ {1,2, . . . , b(ε)} do . b(ε) =d80(1 +¹²_ε)e.

12: Sample a vertex v_I proportionally at random from the set X ∪(I_X \C_U^?) using Lemma 26.

13: SetZ_C←N(v_I)∩U.

14: SetC⁰ ←C∪ZC

15: SetU⁰ ←U\Z_C

16: SetS^C_j,1←ASVD-Approx((G, w,(C⁰, I, U⁰)), ε, β₁^C−1, β₂^C, β₁^I, β^I₂) 17: SetS^C_j,2←ASVD-Approx((G, w,(C⁰, I, U⁰)), ε, β₁^C, β₂^C−1, β₁^I, β^I₂)

18: Sample a vertex v_C proportionally at random from the set X ∪(C_X \I_U^?) using Lemma 26.

19: SetZ_I ←U\N(v_C).

20: SetI⁰ ←I∪ZI

21: SetU⁰ ←U\Z_I

22: SetS^I_j,1←ASVD-Approx((G, w,(C, I⁰, U⁰)), ε, β₁^C, β₂^C, β₁^I−1, β₂^I) 23: SetS^I_j,1←ASVD-Approx((G, w,(C, I⁰, U⁰)), ε, β₁^C, β₂^C, β₁^I, β₂^I−1) 24: end for

25: else

26: for allj∈ {1,2, . . . , b(ε)} do

27: S_j,1^C, S_j,2^C, S_j,1^I , S_j,2^I ←V(G), V(G), V(G), V(G) 28: end for

29: end if

30: S←a min weight set inS

j=1,2,...b(ε){S_j,1^C, S_j,2^C, S_j,1^I , S_j,2^I } S{S12, S34, S^†, S^‡}.

31: returnS 32: end procedure

Proof. Let us fix an optimum solutionOP T to (G, w). We treat the instance (G, w) ofSVD as an instance (G, w,(C =∅, I =∅, U =V(G))) of A-SVD, and apply Algorithm 1 to it, along with the given value ofεand four integersβ₁^C, β₂^C, β₁^I, β^I₂each set todlog_4/3(w(V(G)))e.

Note that, as w is polynomially bounded, we have w(V(G))≤ c₁n^c0 for some constants c0, c1, and hence β⁰≤c2log(n) for everyβ⁰ ∈ {β₁^C, β₂^C, β₁^I, β^I₂} wherec2 is a constant. We will show that the valueβ = 1 +β^C₁ +β₂^C+β^I₁+β₂^I ≤1 + 4c₂log(n) is an upper-bound on the depth of the recursion tree of Algorithm 1, and that in each recursive call this value drops by 1. Hence the depth of recursion is bounded byβ. Each recursive call is made on more constrained sub-instances of A-SVDwhere the underlying graphG, weight functionw,