K onig Deletion Sets and Vertex Covers Above the

Matching Size
Sounaka Mishra
1
, Venkatesh Raman
2
, Saket Saurabh
3
and Somnath Sikdar
2
1
Indian Institute of Technology,
Chennai 600 036, India.
sounak@iitm.ac.in
2
The Institute of Mathematical Sciences,
Chennai 600 113, India.
{vraman|somnath}@imsc.res.in
3
The University of Bergen, Norway.
saket.saurabh@ii.uib.no
Abstract. A graph is K onig-Egerv ary if the size of a minimum vertex cover
equals the size of a maximum matching in the graph. We show that the problem
of deleting at most k vertices to make a given graph K onig-Egerv ary is xed-
parameter tractable with respect to k. This is proved using interesting structural
theorems on matchings and vertex covers which could be useful in other contexts.
We also show an interesting parameter-preserving reduction from the vertex-
deletion version of red/blue-split graphs [4, 9] to a version of Vrarrx Covra and
as a by-product obtain
1. the best-known exact algorithm for the optimization version of Ooo C.cir
Taxxsvrasxi [15];
2. xed-parameter algorithms for several vertex-deletion problems including
the following: deleting k vertices to make a given graph (a) bipartite [17],
(b) split [5], and (c) red/blue-split [7].
1 Introduction
The classical notions of matchings and vertex covers have been at the center of se-
rious study for several decades in the area of Combinatorial Optimization [11]. In
1931, K onig and Egerv ary independently proved a result of fundamental importance:
in a bipartite graph the size of a maximum matching equals that of a minimum ver-
tex cover [11]. This led to a polynomial-time algorithm for nding a minimum vertex
cover in bipartite graphs. In fact, a maximum matching can be used to obtain a 2-
approximation algorithm for the Mrxrmtm Vrarrx Covra problem in general graphs,
which is still the best-known approximation algorithm for this problem. Interestingly,
this min-max relationship holds for a larger class of graphs known as K onig-Egerv ary
graphs and it includes bipartite graphs as a proper subclass. K onig-Egerv ary graphs will
henceforth be called K onig graphs.
K onig graphs have been studied for a fairly long time from a structural point of
view [1, 3, 9, 10, 18, 15]. Both Deming [3] and Sterboul [18] gave independent charac-
terizations of K onig graphs and showed that K onig graphs can be recognized in polyno-
2
mial time. Lov asz [10] used the theory of matching-covered graphs to give an excluded-
subgraph characterization of K onig graphs that contain a perfect matching. Korach et
al. [9] generalized this and gave an excluded-subgraph characterization for the class of
all K onig graphs.
A natural optimization problem associated with a graph class G is the following:
given a graph G, what is the minimum number of vertices to be deleted from G to ob-
tain a graph in G? For example, when G is the class of empty graphs, forests or bipartite
graphs, the corresponding problems are Vrarrx Covra, Frroaxck Vrarrx Srr and Ooo
C.cir Taxxsvrasxi, respectively. We call the vertex-deletion problem corresponding
to class of K onig graphs the K oxro Vrarrx Drirrrox problem. A set of vertices whose
deletion makes a given graph K onig is called a K onig vertex deletion set. In the pa-
rameterized setting, the parameter for vertex-deletion problems is the solution size, that
is, the number of vertices to be deleted so that the resulting graph belongs to the given
graph class.
An algorithmic study of the K oxro Vrarrx Drirrrox problem was initiated in [12],
where it was shown that when restricted to the class of graphs with a perfect match-
ing, K oxro Vrarrx Drirrrox xed-parameter reduces to a problem known as Mrx 2-Cxr
Drirrrox. This latter problem was shown to be xed-parameter tractable by Razgon
and OSullivan [16]. This immediately implies that K oxro Vrarrx Drirrrox is xed-
parameter tractable for graphs with a perfect matching. But the parameterized com-
plexity of the problem in general graphs remained open.
In this paper, we rst establish interesting structural connections between minimum
vertex covers and minimum K onig vertex deletion sets. Using these, we show that
1. the parameterized K oxro Vrarrx Drirrrox problem is xed-parameter tractable,
and
2. there exists an O

(1.221
n
) algorithm
4
for the optimization version of K oxro Vrarrx
Drirrrox problem, where n denotes the number of vertices in the graph.
Note that K onig graphs are not hereditary, that is, not closed under taking induced sub-
graphs. For instance, a 3-cycle is not K onig but attaching an edge to one of the vertices
of the 3-cycle results in a K onig graph. In fact, K oxro Vrarrx Drirrrox is one of the
few vertex-deletion problems associated with a non-hereditary graph class whose pa-
rameterized complexity has been resolved. Another such example can be found in [13].
Our second result is an interesting parameter-preserving reduction from the vertex-
deletion version of red/blue-split graphs [4, 9] to a version of Vrarrx Covra called
Aaovr Gtxaxxrrr Vrarrx Covra. A red/blue graph [7] is a tuple (G = (V, E), c),
where G = (V, E) is a simple undirected graph and c : E 2
{r,b}
\ is an assignment of
colors red and blue to the edges of the graph. An edge may be assigned both red and
blue simultaneously and we require that R, the set of red edges, and B, the set of blue
edges, both be nonempty. A red/blue graph G = (V, R B) is red/blue-split if its vertex
set can be partitioned into a red independent set V
R
and a blue independent set V
B
. A
red (resp. blue) independent set is an independent set in the red graph G
R
= (V, R) (resp.
blue graph G
B
= (V, B)). A graph G is split if its vertex set can be partitioned into an
4
The O

() notation suppresses polynomial terms. We write O

(T(n)) for a time complexity of

the form O(T(n) poly(n)), where T(n) grows exponentially with n.
3
independent set and a clique. A 2-clique graph is a graph whose vertex set can be parti-
tioned into two cliques. Note that a graph is 2-clique if and only if it is the complement
of a bipartite graph. We will see that red/blue-split graphs are a generalization of K onig
(and hence bipartite) graphs, split and 2-clique graphs [7].
As a by-product of the reduction from Rro/Bitr-Srirr Vrarrx Drirrrox to Aaovr
Gtxaxxrrr Vrarrx Covra we obtain:
1. an O

(1.49
n
) algorithm for the optimization version of Rro/Bitr-Srirr Vrarrx
Drirrrox, Ooo C.cir Taxxsvrasxi, Srirr Vrarrx Drirrrox and 2-Cirotr Vrarrx
Drirrrox.
5
2. xed parameter algorithms for all the above problems.
For Ooo C.cir Taxxsvrasxi, this gives the best-known exact algorithm for the opti-
mization version improving over the previous best of O

(1.62
n
) [15].
This paper is organized as follows. In Section 2 we give a brief outline of parameter-
ized complexity, the notations and known results that we use in the rest of the paper. In
Section 3 we show the K oxro Vrarrx Drirrrox problemto be xed-parameter tractable.
In Section 4 we show that a number of vertex-deletion problems xed-parameter reduce
to Rro/Bitr-Srirr Vrarrx Drirrrox which xed-parameter reduces to Aaovr Gtxaxx-
rrr Vrarrx Covra. Finally in Section 5 we end with some concluding remarks and
directions for further research.
2 Preliminaries
In this section we summarize the necessary concepts concerning parameterized com-
plexity, x our notation and outline some results that we make use of in the paper.
2.1 Parameterized Complexity
A parameterized problem is a subset of

Z
0
, where is a nite alphabet and Z
0
is the set of nonnegative numbers. An instance of a parameterized problem is therefore
a pair (I, k), where k is the parameter. In the framework of parameterized complexity,
the running time of an algorithm is viewed as a function of two quantities: the size of
the problem instance and the parameter. A parameterized problem is said to be xed-
parameter tractable (FPT) if there exists an algorithm that takes as input (I, k) and
decides whether it is a .rs or xo-instance in time O( f (k) |I|
O(1)
), where f is a function
depending only on k. The class FPT consists of all xed parameter tractable problems.
A parameterized problem
1
is xed-parameter reducible to a parameterized prob-
lem
2
if there exist functions f , g : Z
0
Z
0
, :

Z
0

and a polynomial
p() such that for any instance (I, k) of
1
, ((I, k), g(k)) is an instance of
2
computable
in time f (k) p(|I|) and (I, k)
1
if and only if ((I, k), g(k))
2
. Two parame-
terized problems are xed-parameter equivalent if they are xed-parameter reducible
to each other. The basic complexity class for xed-parameter intractability is W[1] as
5
Since a 2-clique graph is the complement of a bipartite graph, the 2-Cirotr Vrarrx Drirrrox
problem is NP-complete [17].
4
there is strong evidence that W[1]-hard problems are not xed-parameter tractable. To
show that a problem is W[1]-hard, one needs to exhibit a xed-parameter reduction
from a known W[1]-hard problem to the problem at hand. For more on parameterized
complexity see [14].
2.2 Notation
Given a graph G, we use (G), (G) and (G) to denote, respectively, the size of a
maximum matching, a minimum vertex cover and a minimum K onig vertex deletion
set of G. When the graph being referred to is clear from the context, we simply use
, and . Given a graph G = (V, E) and two disjoint vertex subsets V
1
, V
2
of V,
we let (V
1
, V
2
) denote the bipartite graph with vertex set V
1
V
2
and edge set {{u, v} :
{u, v} E and u V
1
, v V
2
}. If B is a bipartite graph with vertex partition LR then we
let (L, R) denote the size of the maximummatching of B. If M is matching and {u, v}
M then we say that u is the partner of v in M. If the matching being referred to is
clear from the context we simply say u is a partner of v. The vertices of G that are the
endpoints of edges in the matching M are said to be saturated by M; all other vertices
are unsaturated by M.
2.3 Related Results
We next mention some known results about K onig graphs and the Aaovr Gtxaxxrrr
Vrarrx Covra problem.
Fact 1 (See for instance [12].) A graph G = (V, E) is K onig if and only if there exists
a polynomial-time algorithm that partitions V(G) into V
1
and V
2
such that V
1
is a
minimumvertex cover of G and there exists a matching across the cut (V
1
, V
2
) saturating
every vertex of V
1
.
Given a graph G it is clear that (G) (G). The Aaovr Gtxaxxrrr Vrarrx Covra
problem is this: given a graph G and an integer parameter k decide whether (G)
(G)+k. As was shown in [12], for this problemwe may assume that the input graph G =
(V, E) has a perfect matching.
Theorem 1. [12] Let G = (V, E) be a graph with a maximum matching M and let I :=
V \V(M). Construct G

by replacing every vertex u I by a vertex pair u, u

and adding
the edges {u, u

} and {u

, v} for all {u, v} E. Then G has a vertex cover of size (G) + k

if and only if G

has a vertex cover of size (G

) + k.
In [12], we also showed that the Aaovr Gtxaxxrrr Vrarrx Covra problem xed-
parameter reduces to Mrx 2-Sxr Dri which is the problemof deciding whether k clauses
can be deleted from a given 2-Cxr Sxr formula to make it satisable. Since Mrx 2-Sxr
Dri is xed-parameter tractable [16], so is Aaovr Gtxaxxrrr Vrarrx Covra. The algo-
rithmfor Aaovr Gtxaxxrrr Vrarrx Covra actually outputs a vertex cover of size (G)+
k if there exists one.
Corollary 1. Given a graph G = (V, E) and an integer k, one can decide whether G
has a vertex cover of size at most (G) + k in time O(15
k
k |E|
3
). If G has a vertex
cover of size (G) + k then the algorithm actually outputs one such vertex cover.
5
Note that Theorem 1 says that for the Aaovr Gtxaxxrrr Vrarrx Covra problem it
is sucient to consider graphs with a perfect matching. In [12], we showed that the
K oxro Vrarrx Drirrrox problem on graphs with a perfect matching xed-parameter
reduces to Aaovr Gtxaxxrrr Vrarrx Covra. This shows that K oxro Vrarrx Drirrrox on
graphs with a perfect matching is xed-parameter tractable. However this does not seem
to resolve the parameterized complexity status of K oxro Vrarrx Drirrrox in general
graphs. We do not knowof a xed-parameter reduction fromthe general case to the case
with a perfect matching as in the case of Aaovr Gtxaxxrrr Vrarrx Covra. However,
in the next section, we show the general problem to be xed-parameter tractable using
some new structural results between maximum matchings and vertex covers.
3 The K onig Vertex Deletion Problem
We now consider the K oxro Vrarrx Drirrrox Paoairm in general graphs and show it
xed-parameter tractable.
Suppose Y is a vertex cover in a graph G = (V, E). Consider a maximum matching
M between Y and V \ Y. If M saturates every vertex of Y then the graph is K onig.
If not, then Y \ V(M), the set of vertices of Y unsaturated by M, is a K onig deletion
set by Fact 1. What we prove in this section is that if Y is a minimum vertex cover,
then Y \ V(M) is a minimum K onig vertex deletion set.
Our rst observation is that any minimum K onig vertex deletion set is contained in
some minimum vertex cover.
Theorem 2. Let G be an undirected graph with a minimumK onig vertex deletion set K.
Let V(G \ K) = V
1
V
2
where V
2
is independent and there is a matching M from V
1
to V
2
saturating V
1
. Then V
1
K is a minimum vertex cover for G.
Proof. Suppose S is a vertex cover of G such that |S | < |V
1
| + |K|. We will show
that there exists a K onig vertex deletion set of size smaller than |K|, contradicting our
hypothesis. Dene V

1
= V
1
S , V

2
= V
2
S and K

= K S . Let A
1
be the vertices
of V

1
whose partner in M is in V

2
and let A
2
be the vertices of V

1
whose partner in M is
not in V

2
. See Figure 1. We claim that A
1
K

is a K onig vertex deletion set of G and

V1 V2
K
K

1
V

2
A1
A2
M
Fig. 1. The sets that appear in the proof of Theorem 2. The matching M consists of the solid edges
across V
1
and V
2
.
6
|A
1
K

| < |K|, which will produce the required contradiction and prove the theorem.
This claim is proved using the following three claims:
Claim 1. |A
1
K

| < |K|.
Claim 2. A
2
V

2
is a vertex cover in G \ (A
1
K

).
Claim 3. There exists a matching between A
2
V

2
and V \ (V

1
K

2
) saturating
every vertex of A
2
V

2
.
Proof of Claim 1. Clearly |S | = |V

1
| + |V

2
| + |K

|. Note that S intersects |A

1
| of the
edges of M in both end points and |M| |A
1
| edges of M in one end point (in either V

1
or V

2
). Furthermore V

2
has |V

2
\V(M)| vertices of S that do not intersect any edge of M.
Hence |M| +|A
1
| +|V

2
\ V(M)| = |V

1
| +|V

2
|. That is, |V

1
| +|V

2
| = |V
1
| +|A
1
| +|V

2
\ V(M)|
(as |M| = |V
1
|). Hence |S | < |V
1
| + |K| implies that |A
1
| + |V

2
\ V(M)| + |K

| < |K| which

implies that |A
1
| + |K

| < |K| proving the claim.

Proof of Claim 2. Since S = A
1
A
2
V

2
K

is a vertex cover of G, clearly A

2
V

2
covers all edges in G \ (A
1
K

).
Proof of Claim 3. Since the partner of a vertex in A
2
in M is in V \ (V

1
K

2
), we
can use the edges of M to saturate vertices in A
2
. To complete the proof, we show that
in the bipartite graph (V

2
, (V
1
\ V

1
) (K \ K

)) there is a matching saturating V

2
. To
see this, note that any subset D V

2
has at least |D| neighbors in (V
1
\ V

1
) (K \ K

).
For otherwise, let D

be the set of neighbors of D in (V

1
\ V

1
) (K \ K

) where we
assume |D| > |D

|. Then (S \ D) D

is a vertex cover of G of size strictly less than |S |,

contradicting the fact that S is a minimum vertex cover. To see that (S \ D) D

is
indeed a vertex cover of G, note that S \ V

2
covers all edges of G except those in the
graph (V

2
, (V
1
\ V

1
) (K \ K

)) and all these edges are covered by (V

2
\ D) D

. Hence
by Halls theorem, there exists a matching saturating all vertices of V

2
in the bipartite
graph (V

2
, (V
1
\ V

1
) (K \ K

)), proving the claim.

This completes the proof of the theorem.
Theorem 2 has interesting consequences.
Corollary 2. For any two minimum K onig vertex deletion sets (KVDSs) K
1
and K
2
,
(G \ K
1
) = (G \ K
2
).
Proof. Since K
1
is a minimum KVDS of G, (G \ K
1
) = (G \ K
1
). By Theorem 2,
(G \ K
1
) + |K
1
| = (G) and (G \ K
2
) + |K
2
| = (G). Since |K
1
| = |K
2
|, it follows
that (G \ K
1
) = (G \ K
2
) and hence (G \ K
1
) = (G \ K
2
).
From Theorem 2 and Fact 1, we get
Corollary 3. Given a graph G = (V, E) and a minimum K onig vertex deletion set for G,
one can construct a minimum vertex cover for G in polynomial time.
Our goal now is to prove the converse of Corollary 3. In particular, we would
like to construct a minimum K onig vertex deletion set from a minimum vertex cover.
Our rst step is to show that if we know that a given minimum vertex cover contains a
minimum K onig vertex deletion set then we can nd the K onig vertex deletion set in
7
polynomial time. Recall that given a graph G = (V, E) and A, B V such that AB = ,
we use (A, B) to denote a maximum matching in the bipartite graph comprising of the
vertices in A B and the edges in {{u, v} E : u A, v B}. We denote this graph
by (A, B).
Lemma 1. Let K be a minimum KVDS and Y a minimum vertex cover of a graph G =
(V, E) such that K Y. Then (G \ K) = (Y, V \ Y) and |K| = |Y| (Y, V \ Y).
Proof. If G is K onig then the theorem clearly holds. Therefore assume that K .
Note that Y \ K is a minimum vertex cover of the K onig graph G \ K. Thus (G \ K) =
(Y \ K, V \ Y). We claim that (Y \ K, V \ Y) = (Y, V \ Y). For if not, we must
have (Y \ K, V \ Y) < (Y, V \ Y). Then let M be a maximum matching in the bipartite
graph (Y, V \ Y) and K

Y be the set of vertices unsaturated by M. Note that K

is a KVDS for G. Since (Y, V \ Y) = |Y| |K

| and (Y \ K, V \ Y) = |Y| |K| we

have |K

| < |K|, a contradiction, since by hypothesis K is a smallest KVDS for G.

Therefore we must have (G \ K) = (Y, V \ Y) and |K| = |Y| (Y, V \ Y).
The next lemma says that (Y, V \ Y) is the same for all minimum vertex covers Y
of a graph G. Together with Lemma 1, this implies that if K is a minimum K onig vertex
deletion set and Y is a minimum vertex cover of a graph G = (V, E), then (G \ K) =
(Y, V \ Y). This result is crucial to our FPT-algorithm for the K oxro Vrarrx Drirrrox
problem.
Lemma 2. For any two minimumvertex covers Y
1
and Y
2
of G, (Y
1
, V\Y
1
) = (Y
2
, V\
Y
2
).
Proof. Suppose without loss of generality that (Y
1
, V \ Y
1
) > (Y
2
, V \ Y
2
). Let M
1
be
a maximum matching in the bipartite graph (Y
1
, V \ Y
1
). To arrive at a contradiction, we
study how Y
2
intersects the sets Y
1
and V \ Y
1
with respect to the matching M
1
. To this
end, we dene the following sets (see Figure 2):
Y1 V \ Y1
B
P
A1
A2
M1
Fig. 2. The sets that appear in the proof of Lemma 2. The solid edges across Y
1
and V \ Y
1
constitute the matching M
1
.
A = Y
2
Y
1
V(M
1
).
B = Y
2
(V \ Y
1
) V(M
1
).
A
1
is the set of vertices in A whose partners in M
1
are also in Y
2
.
A
2
is the set of vertices in A whose partners in M
1
are not in Y
2
.
8
We rst show that
Claim. In the bipartite graph (Y
2
, V \ Y
2
) there is a matching saturating each vertex
in A
2
B.
It will follow from the claim that (Y
2
, V \ Y
2
) |A
2
| + |B|. However, note that Y
2
intersects every edge of M
1
at least once (as Y
2
is a vertex cover). More specically, Y
2
intersects |A
1
| edges of M
1
twice and |M
1
| |A
1
| edges once (either in Y
1
or in V \ Y
1
).
Hence, |A|+|B| = |M
1
|+|A
1
| and so |A
2
|+|B| = |M
1
| and so (Y
2
, V\Y
2
) |A
2
|+|B| = |M
1
|
a contradiction to our assumption at the beginning of the proof. Thus it suces to prove
the claim.
Proof of Claim. Let P denote the partners of the vertices of A
2
in M
1
. Since P V \ Y
2
,
we use the edges of M
1
to saturate vertices of A
2
. Hence it is enough to show that
the bipartite graph B = (B, (V \ Y
2
) \ P) contains a matching saturating the vertices
in B. Suppose not. By Halls Theorem there exists a set D B such that |N
B
(D)| <
|D|. We claim that the set Y

2
:= Y
2
\ D + N
B
(D) is a vertex cover of G. To see this,
note that the vertices in Y
2
\ D cover all the edges of G except those in the bipartite
graph (D, Y
1
(V \ Y
2
)) and these are covered by N
B
(D). Therefore Y

2
is a vertex cover
of size strictly smaller than Y
2
, a contradiction. This proves that there exists a matching
in (Y
2
, V \ Y
2
) saturating each vertex in A
2
B.
This completes the proof of the lemma.
The next theorem shows how we can obtain a minimum K onig vertex deletion set
from a minimum vertex cover in polynomial time.
Theorem 3. Given a graph G = (V, E), let Y be any minimum vertex cover of G and M
a maximummatching in the bipartite graph (Y, V\Y). Then K := Y\V(M) is a minimum
K onig vertex deletion set of G.
Proof. Clearly K is a KVDS. Let K
1
be a minimum KVDS of G. By Theorem 2, there
exists a minimum vertex cover Y
1
such that K
1
Y
1
and
|K
1
| = |Y
1
| (Y
1
, V \ Y
1
) (By Lemma 1.)
= |Y| (Y
1
, V \ Y
1
) (Since Y
1
and Y are minimum vertex covers.)
= |Y| (Y, V \ Y) (By Lemma 2.)
= |K|
This proves that K is a minimum KVDS.
Corollary 4. Given a graph G = (V, E) and a minimum vertex cover for G, one can
construct a minimum K onig vertex deletion set for G in polynomial time.
Note that although both these problemsVrarrx Covra and K oxro Vrarrx Drirrrox
Srrare NP-complete, we know of very few pairs of such parameters where we can
obtain one from the other in polynomial time (e.g. edge dominating set and minimum
maximal matching, see [8]). In fact, there are parameter-pairs such as dominating set
and vertex cover where such a polynomial-time transformation is not possible unless
P = NP. This follows since in bipartite graphs, for instance, a minimum vertex cover
9
is computable in polynomial time whereas computing a minimum dominating set is
NP-complete.
To show that the K oxro Vrarrx Drirrrox problem is xed-parameter tractable we
make use of the following
Lemma 3. [12] If G is a graph such that (G) = (G) + k, then k (G) 2k.
We are now ready to prove that the K oxro Vrarrx Drirrrox problem is xed-
parameter tractable in general graphs.
Theorem 4. Given a graph G = (V, E) and an integer parameter k, the problem of
whether G has a subset of at most k vertices whose deletion makes the resulting graph
K onig can be decided in time O(15
k
k
2
|E|
3
).
Proof. Use the FPT algorithm from Corollary 1 to test whether G has a vertex cover
of size at most (G) + k. If not, by Lemma 3, we know that the size of a minimum
K onig vertex deletion set is strictly more than k. Therefore return xo. If yes, then nd
the size of a minimum vertex cover by applying Corollary 1 with every integer value
between 0 and k for the excess above (G). Note that for .rs-instances of the Aaovr
Gtxaxxrrr Vrarrx Covra problem, the FPT algorithm actually outputs a vertex cover
of size (G) + k. We therefore obtain a minimum vertex cover of G. Use Theorem 3 to
get a minimum K onig vertex deletion set in polynomial time and depending on its size
answer the question. It is easy to see that all this can be done in time O(15
k
k
2
|E|
3
).
We know that computing a maximum independent set (or equivalently a minimum
vertex cover) in an n-vertex graph can be done in time O

(2
0.288n
) [6]. By Corollary 4,
we can compute a minimum K onig vertex deletion set in the same exponential time.
Given a graph G together with a tree-decomposition for it of width w, one can obtain
a minimum vertex cover in time O

(2
w
) [14]. For the denitions of treewidth and tree-
decomposition, refer [14]. In general, algorithms on graphs of bounded treewidth are
based on dynamic programming over the tree-decomposition of the graph. It is not
obvious how to nd such a dynamic programming algorithm for the K oxro Vrarrx
Drirrrox problem. By applying Corollary 4, we can nd a minimum K onig deletion set
in time O

(2
w
) in graphs of treewidth w. The above discussion results in the following
corollary.
Corollary 5. 1. Given a graph G = (V, E) on n vertices we can nd a minimum K onig
vertex deletion set in time O

(2
0.288n
) = O

(1.221
n
).
2. If a tree-decomposition for G of width w is given, we can nd a minimum K onig
vertex deletion set in time O

(2
w
).
4 Red/Blue-Split Graphs and Above Guarantee Vertex Cover
In this section we introduce the Rro/Bitr-Srirr Vrarrx Drirrrox problem and show
that a number of vertex-deletion problems xed-parameter reduce to it. Recall that a
red/blue-graph is one in which the edges are colored red or blue and where an edge
may receive multiple colors. A red/blue-graph G = (V, R B) is red/blue-split if its
10
vertex set can be partitioned into a red independent set and a blue independent set,
where a red (blue) independent set is an independent set in the red graph G = (V, R)
(blue graph G = (V, B)). In what follows we use r/b as an abbreviation for red/blue
and E
c
to denote the set of edges assigned color c.
The R/B-Srirr Vrarrx Drirrrox problem is the following: given an r/b-graph G =
(V, RB) and an integer k, are there k vertices whose deletion makes G r/b-split? We rst
show that R/B-Srirr Vrarrx Drirrrox xed-parameter reduces to the Aaovr Gtxaxx-
rrr Vrarrx Covra problem. Since Aaovr Gtxaxxrrr Vrarrx Covra is xed-parameter
tractable, this will show that R/B-Srirr Vrarrx Drirrrox is xed-parameter tractable
too.
At this point, we note that r/b-split graphs can be viewed as a generalization of
K onig graphs as follows. A graph G = (V, E) with a maximum matching M is K onig
if and only if the 2-colored graph G

= (V, R B), where R = E and B = M, is r/b-

split. It is important to realize that while this gives a recognition algorithm for K onig
graphs using one for r/b-split graphs, it does not seem to give any relationship between
the corresponding vertex-deletion problems. In fact, we do not know of any parameter-
preserving reduction from K oxro Vrarrx Drirrrox to the R/B-Srirr Vrarrx Drirrrox
problem for general graphs.
For graphs with a perfect matching, we show by an independent argument based
on the structure of a minimum K onig vertex deletion set that the K oxro Vrarrx Drir-
rrox problem does indeed xed-parameter reduce to Aaovr Gtxaxxrrr Vrarrx Covra
(and also to R/B-Srirr Vrarrx Drirrrox) [12]. But this structural characterization of
minimum K onig vertex deletion sets does not hold in general graphs. Therefore the
xed-parameter tractability result for K oxro Vrarrx Drirrrox Srr cannot be obtained
from that of R/B-Srirr Vrarrx Drirrrox.
Theorem 5. Let G = (V, E = E
r
E
b
) be an r/b graph. Construct G

= (V

, E

) as
follows: the vertex set V

consists of two copies V

1
, V
2
of V and for all u V, u
1
V
1
and u
2
V
2
the edge set E

= {{u
1
, u
2
} : u V} {{u
1
, v
1
} : {u, v} E
r
} {{u
2
, v
2
} :
{u, v} E
b
}. Then there exists k vertices whose deletion makes G r/b-split if and only
if G

has a vertex cover of size (G

) + k.
Proof. Clearly G

has 2|V| vertices and a perfect matching of size |V|. It suces to show
that G has an r/b-split subgraph on t vertices if and only if G

has an independent set of

size t. This would prove that there exists |V| t vertices whose deletion makes G r/b-split
if and only if G

has a vertex cover of size 2|V| t. Finally, plugging in k = |V| t will

prove the theorem.
Therefore let H be an r/b-split subgraph of G on t vertices with a red independent
set V
r
and a blue independent set V
b
. Then the copy V
1
r
of V
r
in V
1
and the copy V
2
b
of V
b
in V
2
are independent sets in G

. Since V
r
V
b
= , V
1
r
V
2
b
is an independent set
in G

on t vertices. Conversely if H

is an independent set in G

of size t, then for i = 1, 2

let V(H

) V
i
= W
i
and |W
i
| = t
i
so that t
1
+ t
2
= t. For i = 1, 2, let

W
i
be the vertices
in V(G) corresponding to the vertices in W
i
. Then

W
1
is an independent set of size t
1
in the red graph G
r
= (V(G), E
r
) and

W
2
is an independent set of size t
2
in the blue
graph G
b
= (V(G), E
b
). Since W
1
and W
2
do not both contain copies of the same vertex
of V(G), as W
1
W
2
is independent, we have

W
1


W
2
= . Thus G[

W
1


W
2
] is an
r/b-split graph of size t in G.
11
Since a maximum independent set in an n-vertex graph can be obtained in time
O

(2
0.288n
) [6], we immediately have the following
Corollary 6. The optimization version of the R/B-Srirr Vrarrx Drirrrox problem can
be solved in time O

(2
0.576n
) = O

(1.49
n
) on input graphs on n vertices.
Since Aaovr Gtxaxxrrr Vrarrx Covra is xed-parameter tractable (Corollary 1) we
have
Corollary 7. The parameterized version of the R/B-Srirr Vrarrx Drirrrox problem is
xed-parameter tractable and can be solved in time O(15
k
k
2
m
3
), where m is the
number of edges in the input graph.
As mentioned before, K onig (and hence bipartite) and split graphs can be viewed
as r/b-split graphs. Since 2-clique graphs are complements of bipartite graphs it fol-
lows that they can also be viewed as r/b-split graphs. The vertex-deletion problems
Ooo C.cir Taxxsvrasxi, Srirr Vrarrx Drirrrox and 2-Cirotr Vrarrx Drirrrox xed-
parameter reduce to R/B-Srirr Vrarrx Drirrrox. We showthis reduction for Ooo C.cir
Taxxsvrasxi as the proofs in the other cases are quite similar.
Theorem 6. Given a simple undirected graph G = (V, E), construct an r/b-graph G

=
(V

, E

) as follows: dene V

= V and E

= E; E
r
(G

) = E and E
b
(G

) = E. Then there
exists k vertices whose deletion makes G bipartite if and only if there exist k vertices
whose deletion makes G

r/b-split.
Proof. Suppose deleting k vertices fromG makes it bipartite with vertex bipartition V
1

V
2
. Then V
1
and V
2
are independent in both the red graph G

r
= (V

, E
r
) and in the blue
graph G

b
= (V

, E
b
). Thus G

[V
1
V
2
] is r/b-split. Conversely if k vertices can be
deleted from G

to make it r/b-split, let V

r
and V
b
be the red and blue independent sets
respectively. Then both these sets must be independent in G and therefore the subgraph
of G induced on V
r
V
b
is bipartite.
From Theorem 6 and Corollaries 6 and 7 the following result follows immediately.
Corollary 8. The parameterized version of Ooo C.cir Taxxsvrasxi, Srirr Vrarrx
Drirrrox and 2-Cirotr Vrarrx Drirrrox are xed-parameter tractable and their op-
timization versions can be solved in time O

(2
0.576n
) = O

(1.49
n
) on input graphs on n
vertices.
5 Conclusion
We showed that the K oxro Vrarrx Drirrrox problem is xed-parameter tractable in
general graphs. To prove this, we made use of a number of structural results involving
minimumvertex covers, minimumK onig vertex deletion sets and maximummatchings.
We also showed that a number of vertex-deletion problems, in particular, R/B-Srirr
Vrarrx Drirrrox, and Ooo C.cir Taxxsvrasxi xed-parameter reduce to Aaovr Gtxa-
xxrrr Vrarrx Covra. Since the latter problemis FPT, all these vertex-deletion problems
are also FPT.
12
An interesting open problem is the parameterized complexity of the K oxro Eoor
Drirrrox problem: given G = (V, E) and an integer parameter k, does there exist at
most k edges whose deletion makes the resulting graph K onig? Deriving a problem
kernel for K oxro Vrarrx Drirrrox Srr is an interesting open problem. Another natural
open problem to design better FPT algorithms for Aaovr Gtxaxxrrr Vrarrx Covra
perhaps without using the reduction to Mrx 2-Sxr Drirrrox.
Acknowledgements. We thank anonymous referees of ISAAC 2008 for suggestions that
helped improve the presentation.
References
1. J .M. Botasoii. xxo W. R. Ptiir.aixxk. K onig-Egerv ary Graphs, 2-Bicritical Graphs and
Fractional Matchings. Disc. Appl. Math. Vol. 24, pp. 63-82, 1989.
2. L. Cxr. Fixed-Parameter Tractability of Graph Modication Problems for Hereditary Prop-
erties. Inform. Proc. Lett. Vol. 58, Issue 4, pp. 171-176, 1996.
3. R. W. Drmrxo. Independence Numbers of Graphs An Extension of the K onig-Egerv ary
Theorem. Disc. Math. Vol. 27, pp. 23-33, 1979.
4. U. Fxroir, B. Ftcns xxo B. Wrrxxxo. Covering Graphs by Colored Stable Sets. Electronic
Notes in Disc. Math. Vol. 17, pp. 145-149, 2004.
5. S. F oiors xxo P. L. Hxmmra. Split graphs. In Proc. of the 8th Southeastern Conference on
Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La.,
1977), pp. 311-315, Winnipeg: Congressus Numerantium, No. XIX, Utilitas Math.
6. F. V. Fomrx, F. Gaxxooxr xxo D. Kaxrscn. Measure and Conquer: A Simple O(2
0.288n
) Inde-
pendent Set Algorithm. In Proc. of SODA 2006, pp. 18-25, 2006.
7. F. Gxvari. An Eciently Solvable Graph Partition Problem to Which Many Problems are
Reducible. Inform. Proc. Lett. Vol. 45, pp. 285-290, 1993.
8. F. Gxvari xxo M. Yxxxxkxkrs. Edge Dominating Sets in Graphs. SIAM Jour. Appl. Math.
Vol. 38, Issue 3, pp. 364-372, 1980.
9. E. Koaxcn, T. Not.rx xxo B. Prrs. Subgraph Characterization of Red/Blue-Split Graphs
and K onig-Egerv ary Graphs. In the Proc. of SODA 2006, pp. 842-850, 2006.
10. L. Lov xsz. Ear-Decompositions of Matching-covered Graphs. Combinatorica Vol. 3, pp.
105-118, 1983.
11. L. Lov xsz xxo M. D. Pitmmra. Matching Theory. North Holland, 1986.
12. S. Mrsnax, V. Rxmxx, S. Sxtaxan, S. Srkoxa xxo C. R. Staaxmxxrxx. The Complexity of
Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number. In Proc. of
ISAAC 2007, Springer LNCS Vol. 4835, pp. 268-279, 2007.
13. H. Mosra xxo D. M. Tnrirkos. Parameterized Complexity of Finding Regular Induced Sub-
graphs. In Proc. of ACiD 2006, pp. 107-118.
14. R. Nrroramrrra. An Invitation to Fixed-Parameter Algorithms. Oxford University Press,
2006.
15. V. Rxmxx, S. Sxtaxan xxo S. Srkoxa. Ecient Exact Algorithms Through Enumerat-
ing Maximal Independent Sets and Other Techniques. Theory Comput. Systems Vol. 41,
pp. 563-587, 2007.
16. I. Rxzoox xxo B. OStiirvxx. Almost 2-SAT is Fixed-Parameter Tractable. In Proc. of
ICALP 2008, Springer LNCS Vol. 5125, pp. 551-562.
17. B. Rrro, K. Smrrn xxo A. Vrrrx. Finding Odd Cycle Transversals. Operations Research
Letters Vol. 32, pp. 299-301, 2004.
18. F. Srraaoti. A Characterization of Graphs in which the Transversal Number Equals the
Matching Number. Jour. of Comb. Theory, Ser. B Vol. 27, pp. 228-229, 1979.