arXiv:1705.02822v2 [] 10 May 2017

Rank Vertex Cover as a Natural Problem for Algebraic
Compression∗
S. M. Meesum†

Fahad Panolan‡

Saket Saurabh†‡

Meirav Zehavi‡

Abstract
The question of the existence of a polynomial kernelization of the Vertex Cover
Above LP problem has been a longstanding, notorious open problem in Parameterized
Complexity. Five years ago, the breakthrough work by Kratsch and Wahlström on
representative sets has finally answered this question in the affirmative [FOCS 2012].
In this paper, we present an alternative, algebraic compression of the Vertex Cover
Above LP problem into the Rank Vertex Cover problem. Here, the input consists
of a graph G, a parameter k, and a bijection between V (G) and the set of columns of a
representation of a matriod M , and the objective is to find a vertex cover whose rank
is upper bounded by k.

1

Introduction

The field of Parameterized Complexity concerns the study of parameterized problems, where
each problem instance is associated with a parameter k that is a non-negative integer.
Given a parameterized problem of interest, which is generally computationally hard, the
first, most basic question that arises asks whether the problem at hand is fixed-parameter
tractable (FPT). Here, a problem Π is said to be FPT if it is solvable in time f (k) · |X|O(1) ,
where f is an arbitrary function that depends only on k and |X| is the size of the input
instance. In other words, the notion of FPT signifies that it is not necessary for the combinatorial explosion in the running time of an algorithm for Π to depend on the input size,
but it can be confined to the parameter k. Having established that a problem is FPT, the
second, most basic question that follows asks whether the problem also admits a polynomial
kernel. A concept closely related to kernelization is one of polynomial compression. Here,
b and a
a problem Π is said to admit a polynomial compression if there exist a problem Π
polynomial-time algorithm such that given an instance (X, k) of Π, the algorithm outputs
∗

Supported by Parameterized Approximation, ERC Starting Grant 306992, and Rigorous Theory of
Preprocessing, ERC Advanced Investigator Grant 267959.
†
The Institute of Mathematical Sciences, HBNI, Chennai, India. {meesum|saket}@imsc.res.in
‡
Department of Informatics, University of Bergen, Norway. {fahad.panolan|meirav.zehavi}@ii.uib.no

1

b b
b where |X|
b = b
an equivalent instance (X,
k) of Π,
kO(1) and b
k ≤ k. Roughly speaking,
compression is a mathematical concept that aims to analyze preprocessing procedures in
b the problem is further said to
a formal, rigorous manner. We note that in case Π = Π,
b
b
admit a polynomial kernelization, and the output (X, k) is called a kernel.
The Vertex Cover problem is (arguably) the most well-studied problem in Parameterized Complexity [10, 7]. Given a graph H and a parameter k, this problem asks whether
H admits a vertex cover of size at most k. Over the years, a notable number of algorithms
have been developed for the Vertex Cover problem [2, 1, 11, 25, 5, 3, 6]. Currently, the
best known algorithm solves this problem in the remarkable time 1.2738k · nO(1) [6]. While
it is not known whether the constant 1.2738 is “close” to optimal, it is known that unless
the Exponential Time Hypothesis (ETH) fails, Vertex Cover cannot be solved in time
2o(k) · nO(1) [16]. On the other hand, in the context of kernelization, the picture is clear
in the following sense: It is known that Vertex Cover admits a kernel with O(k2 ) vertices and edges [2], but unless NP ⊆ co-NP/poly, it does not admit a kernel with O(k 2−ǫ )
edges [9]. We remark that it is also known that Vertex Cover admits a kernel not only
of size O(k2 ), but also with only 2k vertices [5, 20], and it is conjectured that this bound
might be essentially tight [4].
It has become widely accepted that Vertex Cover is one of the most natural test
beds for the development of new techniques and tools in Parameterized Complexity. Unfortunately, the vertex cover number of a graph is generally large—in fact, it is often linear
in the size of the entire vertex set of the graph [10, 7]. Therefore, alternative parameterizations, known as above guarantee parameterizations, have been proposed. The two most well
known such parameterizations are based on the observation that the vertex cover number
of a graph H is at least as large as the fractional vertex cover number of H, which in turn is
at least as large as the maximum size of a matching of H. Here, the P
fractional vertex cover
number of H is the solution to the linear program that minimizes v∈V (H) xv subject to
the constraints xu + xv ≥ 1 for all {u, v} ∈ E(H), and xv ≥ 0 for all v ∈ V (H). Accordingly, given a graph H and a parameter k, the Vertex Cover Above MM problem asks
whether H admits a vertex cover of size at most µ(H) + k, where µ(H) is the maximum
size of a matching of H, and the Vertex Cover Above LP problem asks whether H
admits a vertex cover of size at most ℓ(H) + k, where ℓ(H) is the fractional vertex cover
number of H.
On the one hand, several parameterized algorithms for these two problems have been
developed in the last decade [28, 27, 8, 24, 21]. Currently, the best known algorithm for
Vertex Cover Above LP, which is also the best known algorithm Vertex Cover
Above MM, runs in time 2.3146k · nO(1) [21]. On the other hand, the question of the
existence of polynomial kernelizations of these two problems has been a longstanding, notorious open problem in Parameterized Complexity. Five years ago, the breakthrough work
by Kratsch and Wahlström on representative sets has finally answered this question in the
affirmative [19]. Up to date, the kernelizations by Kratsch and Wahlström have remained
the only known (randomized) polynomial compressions of Vertex Cover Above MM
2

and Vertex Cover Above LP. Note that since ℓ(H) is necessarily at least as large as
µ(H), a polynomial compression of Vertex Cover Above LP also doubles as a polynomial compression of Vertex Cover Above MM. We also remark that several central
problems in Parameterized Complexity, such as the Odd Cycle Transversal problem,
are known to admit parameter-preserving reductions to Vertex Cover Above LP [21].
Hence, the significance of a polynomial compression of Vertex Cover Above LP also
stems from the observation that it simultaneously serves as a polynomial compression of
additional well-known problems, and can therefore potentially establish the target problem
as a natural candidate to express compressed problem instances.
Recently, a higher above-guarantee parameterization of Vertex Cover, resulting in
the Vertex Cover Above Lovász-Plummer, has been introduced by Garg and Philip
[12]. Here, given a graph H and a parameter k, the objective is to determine whether H
admits a vertex cover of size at most (2ℓ(H) − µ(H)) + k. Garg and Philip [12] showed
that this problem is solvable in time 3k · nO(1) , and Kratsch [18] showed that it admits a
(randomized) kernelization that results in a large, yet polynomial, kernel. We remark that
above-guarantee parameterizations can very easily reach bars beyond which the problem at
hand is no longer FPT. For example, Gutin et al. [14] showed that the parameterization of
Vertex Cover above m/∆(H), where ∆(H) is the maximum degree of a vertex in H and
m is the number of edges in H, results in a problem that is not FPT (unless FPT=W[1]).
Our Results and Methods. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem.
We remark that Rank Vertex Cover was originally introduced by Lovász as a tool for
the examination of critical graphs [22]. Given a graph H, a parameter ℓ, and a bijection
between V (G) and the set of columns of a representation of a matroid M , the objective
of Rank Vertex Cover is to find a vertex cover of H whose rank, which is defined by
the set of columns corresponding to its vertices, is upper bounded by ℓ. Note that formal
definitions of the terms used in the definition of Rank Vertex Cover can be found in
Section 2.
We obtain a (randomized) polynomial compression of size Õ(k7 + k4.5 log(1/ε))1 , where
ε is the probability of failure. Here, by failure we mean that we output an instance of Rank
Vertex Cover which is not equivalent to the input instance. In the first case, we can
simply discard the output instance, and return an arbitrary instance of constant size; thus,
we ensure that failure only refers to the maintenance of equivalence. Our work makes use
of properties of linear spaces and matroids, and also relies on elementary probability theory.
One of the main challenges it overcomes is the conversion of the methods of Lovász [22]
into a procedure that works over rationals with reasonably small binary encoding.
1

Õ hide factors polynomial in log k

3

2

Preliminaries

We use N to denote the set of natural numbers. For any n ∈ N, we use [n] as a shorthand
for {1, 2, . . . , n}. In this paper, the notation F will refer to a finite field of prime size.
Accordingly, Fn is an n-dimensional linear space over the field F, where a vector v ∈ Fn
is a tuple of n elements from the field F. Here, the vector v is implicitly assumed to be
represented as a column vector, unless stated otherwise. A finite set of vectors
P S over the
field F is said to be linearly independent if the only solution to the equation v∈S λv v = 0,
where it holds that λv ∈ F for all v ∈ S, is the one that assigns zero to all of the scalars
λv . A set S that is not linearly independent is said to bePlinearly dependent. The span of
a set of vectors S, denoted by S (or span(S)), is the set { v∈S αv v : αv ∈ F}, defined over
the linear space Fn .
For a graph G, we use V (G) and E(G) to denote the vertex set and the edge set of G,
respectively. We treat the edge
set of an undirected graph G as a family of subsets of size
V (G)
2 of V (G), i.e. E(G) ⊆ 2 . An independent set in a graph G is a set of vertices X such
that for all u, v ∈ X, it holds that {u, v} ∈
/ E(G). For a graph G and a vertex v ∈ V (G),
we use G \ v to denote the graph obtained from G after deleting v and the edges incident
with v.

2.1

Matroids

Definition 1. A matroid X is a pair (U, I), where U is a set of elements and I is a set of
subsets of U , with the following properties: (i) ∅ ∈ I, (ii) if I1 ⊂ I2 and I2 ∈ I, then I1 ∈ I,
and (iii) if I1 , I2 ∈ I and |I1 | < |I2 |, then there is x ∈ (I2 \ I1 ) such that I1 ∪ {x} ∈ I.
A set I ′ ∈ I is said to be independent; otherwise, it is said to be dependent. A set B ∈ I
is a basis if no superset of B is independent. For example, Ut,n = ([n], {I : I ⊆ [n], |I| ≤ t})
forms a matroid known as a uniform matroid. For a matroid X = (U, I), we use E(X), I(X)
and B(X) to denote the ground set U of X, the set of independent sets I of X, and the set
of bases of X, respectively. Here, we are mainly interested in linear matroids, which are
defined as follows. Given a matroid X = (U, I), a matrix M having |U | columns is said to
represent X if (i) the columns of M are in bijection with the elements in U , and (ii) a set
A ⊆ U is independent in X if and only if the columns corresponding to A in M are linearly
independent. Accordingly, a matroid is a linear matroid if it has a representation over some
field. For simplicity, we use the same symbol to refer to a matroid M and its representation.
For a matrix M and some subset B of columns of M , we let M [⋆, B] denote the submatrix
of M that is obtained from M be deleting all columns not in B. The submatrix of M over
a subset of rows R and a subset of columns B is denoted using M [R, B].
We proceed by stating several basic definitions related to matroids that are central to
our work. For this purpose, let X = (U, I) be a matroid. An element x ∈ U is called
a loop if it does not belong to any independent set of X. If X is a linear matroid, then
loops correspond to zero column vectors in its representation. An element x ∈ U is called
4

a co-loop if it occurs in every basis of X. Note that for a linear matroid X, an element x
is a co-loop if it is linearly independent from any subset of U \ {x}. For a subset A ⊆ U ,
the rank of A is defined as the maximum size of an independent subset of A, that is,
rankX (A) := maxI ′ ⊆A {|I ′ | : I ′ ∈ I}. We remove the subscript of rankX (A), if the matroid
is clear from the context.
The rank function of X is the function rank : 2U → N that assigns rank(A) to each
subset A ⊆ U . Note that this function satisfies the following properties.
1. 0 ≤ rank(A) ≤ |A|,
2. if A ⊆ B, then rank(A) ≤ rank(B), and
3. rank(A ∪ B) + rank(A ∩ B) ≤ rank(A) + rank(B).
A subset F ⊆ U is a flat if rank(F ∪ {x}) > rank(F ) for all x ∈
/ F . Let F be the
set ofTall flats of the matroid X. For any subset A of U , the closure A is defined as
A = F ∈F {F : A ⊆ F }. In other words, the closure of a set is the flat of minimum rank
containing it. Let F be a flat of the matroid X. A point x ∈ F is said to be in general
position on F if for any flat F ′ of X, if x is contained in span(F ′ \ {x}) then F ⊆ F ′ .

Deletion and Contraction. The deletion of an element u from X results in a matroid
X ′ , denoted by X \ u, with ground set E(X ′ ) = E(X) \ {u} and set of independent sets
I(X ′ ) = {I : I ∈ I(X), u ∈
/ I}. The contraction of a non-loop element u from X results in
a matroid X ′ , denoted by X/u, with ground set E(X ′ ) = E(X)\{u} and set of independent
sets I(X ′ ) = {I \ {u} : u ∈ I and I ∈ I(X)}. Note that B is a basis in X/u if and only
if B ∪ {u} is a basis in X.
When we are considering two matroids X and X/u, then for any subset
T ⊆ E(X) \ {u}, T represents the closure of T with respect to the matroid X.
A matroid can be also be represented by a ground set and a rank function, and for our
purposes, it is sometimes convenient to employ such a representation. That is, we also use
a pair (U, r) to specify a matroid, where U is the ground set and r is rank function. Now,
we prove several lemmata regarding operations on matroids, which are used later in the
paper.
Observation 1. Let M be a matroid, u ∈ E(M ) be a non-loop element in M and v be a
co-loop in M . Then, rank(M/u) = rank(M ) − 1 and v is a co-loop in M/u.
Given a matrix (or a linear matroid) A and a column v ∈ A, by moving the vector v
to another vector u, we refer to the operation that replaces the column v by the column u
in A.
Lemma 1. Let X = (U, I) be a linear matroid, W ⊆ U , and let u, v ∈
/ W be two elements
that are each a co-loop in X. Let X ′ be the linear matroid obtained by moving u to a general
position on the flat spanned by W . Then, v is also a co-loop in X ′ .

5

Proof. Let u′ denote the vector to which u was moved (that is in general position on the
span of W ). Notice that the only modification performed with respect to the vectors of X
is the update of u to u′ . Suppose, by way of contradiction, that v is not a co-loop in X ′ .
Then, there exists a set of elements S ⊆ E(X ′ ), where v ∈
/ S, whose span contains v. If
′
u ∈
/ S, then S ⊆ U , which implies that v was not a co-loop in X. Since this results in a
contradiction, we have that u′ ∈ S. As u′ is in the span of W , v must be in the span of
(W ∪ S) \ {u′ }. Since (W ∪ S) \ {u′ } ⊆ U and v ∈
/ (W ∪ S) \ {u′ }, we have thus reached a
contradiction.
We remark that the proof of Lemma 1 does not require the vector u to be moved to a
general position on the flat, but it holds true also if u is moved to any vector in span(W).
Lemma 2. Let X = (U, I) be a matroid and u ∈ U be an element that is not a loop in X.
If v ∈ U is a co-loop in X, then v is also a co-loop in the contracted matroid X/u.
Proof. Suppose, by way of contradiction, that v is not a co-loop in X/u. Then, there exists
an independent set I ∈ I(X/u), where v ∈
/ I, whose span contains v. In particular, this
implies that I ∪ {v} is a dependent set in X/u. By the definition of contraction, I ∪ {u} is
an independent set in X. As v is a co-loop in X, I ∪ {u, v} is also an independent set in X.
By the definition of contraction, I ∪ {v} is an independent set in X/u, which contradicts
our previous conclusion that I ∪ {v} is a dependent set in X/u.
Lemma 3 (Proposition 3.9 [13]). Let v be an element in a matroid X = (U, I), which is not
a loop in X. Let T be a subset of U such that v ∈ T . Then, rankX (T ) = rankX/v (T \{v})+1.
The lemma above can be rephrased as follows: if T is a set of elements in a matroid
X = (U, I) such that an element v ∈ U is contained in the span of T , then the rank of T
in the contracted matroid X/v is smaller by 1 than the rank of T in X.

3

Compression

Our objective is to give a polynomial compression of Vertex Cover Above LP. More
precisely, we develop a polynomial-time randomized algorithm that given an instance of
Vertex Cover Above LP with parameter k and ε > 0, with probability at least 1 − ε
outputs an equivalent instance of Rank Vertex Cover whose size is bounded by a
polynomial in k and ǫ. It is known that there is a parameter-preserving reduction from
Vertex Cover Above LP to Vertex Cover Above MM such that the parameter of
the output instance is linear in the parameter of the original instance [19]. Thus, in order to
give a polynomial compression of Vertex Cover Above LP to Rank Vertex Cover
where the size of the output instance is bounded by Õ(k7 + k4.5 log(1/ε)), it is enough to
give a polynomial compression of Vertex Cover Above MM to Rank Vertex Cover
with the same bound on the size of the output instance. For a graph H, we use µ(H)
6

and β(H) to denote the maximum size of a matching and the vertex cover number of H,
respectively. Let (G, k) be an instance of Vertex Cover Above MM. Let n = |V (G)|
and In denote the n × n identity matrix. That is, In is a representation of Un,n . Notice that
(G, k) is a Yes-instance of Vertex Cover Above MM if and only if (G, In , µ(G) + k),
with any arbitrary bijection between V (G) and columns of In , is a Yes-instance of Rank
Vertex Cover.
In summary, to give the desired polynomial compression of Vertex Cover Above LP,
it is enough to give a polynomial compression of instances of the form (G, In , µ(G) + k) of
Rank Vertex Cover where the size of the output instance is bounded by Õ(k7 + k4.5 log(1/ε)).
Here, the parameter is k. For instances of Rank Vertex Cover, we assume that the
columns of the matrix are labeled by the vertices in V (G) in a manner corresponding to a
bijection between the input graph and columns of the input matrix. As discussed above,
we again stress that now our objective is to give a polynomial compression of an instance
of the form (G, In , µ(G) + k) of Rank Vertex Cover to Rank Vertex Cover, which
can now roughly be thought of as a polynomial kernelization. We achieve the compression
in two steps.
1. In the first step, given (G, M = In , µ(G) + k), in polynomial time we either conclude
that (G, In , µ(G) + k) is a Yes-instance of Rank Vertex Cover or (with high
probability of success) output an equivalent instance (G1 , M1 , ℓ) of Rank Vertex
Cover where the number of rows in M1 , and hence rank(M1 ), is upper bounded by
O(k3/2 ). More over we also bound the bits required for each entry in the matrix to
be Õ(k5/2 + log(1/ε)) This step is explained in Section 3.2. Notice that after this
step, the graph G1 need not be bounded by kO(1) .
2. In the second step, we work with the output (G1 , M1 , ℓ) of the first step, and in
polynomial time we reduce the number of vertices and edges in the graph G1 (and
hence the number of columns in the matrix M1 ). That is, output of this step is an
equivalent instance (G2 , M2 , ℓ) where the size of G2 is bounded by O(k3 ). This step
is explained in Section 3.3.
Throughout the compression algorithm, we work with Rank Vertex Cover. Notice
that the input of Rank Vertex Cover consists of a graph G, an integer ℓ, and a linear
representation M of a matroid with a bijection between V (G) and the set of columns of M .
In the compression algorithm, we use operations that modify the graph G and the matrix
M simultaneously. To employ these “simultaneous operations” conveniently, we define (in
Section 3.1) the notion of a graph-matroid pair. We note that the definition of a graphmatroid pair is the same as a pre-geometry defined in [22], and various lemmas from [22]
which we use here are adapted to this definition. We also define deletion and contraction
operations on a graph-matroid pair, and state some properties of these operations.

7

3.1

Graph-Matroid Pairs

We start with the definition of a graph-matroid pair.
Definition 2. A pair (H, M ), where H is a graph and M is a matroid over the ground set
V (H), is called a graph-matroid pair.
Notice that there is natural bijection between V (H) and E(M ), which is the identity
map. Now, we define deletion and contraction operations on graph-matroid pairs.
Definition 3. Let P = (H, M ) be a graph-matroid pair, and let u ∈ V (H). The deletion
of u from P , denoted by P \ u, results in the graph-matroid pair (H \ u, M \ u). If u is not
a loop in M , then the contraction of u in P , denoted by P/u, results in the graph-matroid
pair (H \ u, M/u). For an edge e ∈ E(H), P \ e represents the pair (H \ e, M )
We remark that matroid deletion and contraction can be done time polynomial in the
size of ground set for a linear matroid. For details we refer to [13, 26].
Definition 4. Given a graph-matroid pair P = (H, M ), the vertex cover number of P is
defined as τ (P ) = min{rankM (S) : S is a vertex cover of H}.
For example, if M is an identity matrix (where each element is a co-loop), then τ (P )
is the vertex cover number of H. Moreover, if we let M be the uniform matroid Ut,n such
that t is at least the size of the vertex cover number of H, then τ (P ) again equals the
vertex cover number of H.
Let P = (H, M ) be a graph-matroid pair where M is a linear matroid. Recall that M is
also used to refer to a given linear representation of the matroid. For the sake of clarity, we
use vM to refer explicitly to the column vector associated with a vertex v ∈ V (H). When
it is clear from context, we use v and vM interchangeably.
Lemma 4 (see Proposition 4.2 in [22]). Let P = (H, M ) be a graph-matroid pair and
v ∈ V (H) such that the vector vM is a co-loop in M , where M is a linear matroid. Let
P ′ = (H, M ′ ) be the graph-matroid pair obtained by moving vM to a vector vM ′ in general
position on a flat containing the neighbors of v, NH (v). Then, τ (P ′ ) = τ (P ).
Proof. Note that the operation in the statement of the lemma does not change the graph
H. The only change occurs in the matroid, where we map an co-loop vM to a vector lying
in the span of its neighbors. It is clear that such an operation does not increase the rank of
any vertex cover. Indeed, given a vertex cover T of H, in case it excludes v, the rank of T
is the same in both M and M ′ , and otherwise, since vM is an co-loop, the rank of T cannot
increase when M is modified by replacing vM with any other vector. Thus, τ (P ′ ) ≤ τ (P ).
For the other inequality, let T be the set of vectors corresponding to a minimum rank
vertex cover of the graph H in the graph-matroid pair P ′ (where we have replaced the
vector vM by the vector vM ′ ). In what follows, note that as we are working with linear
matroids, the closure operation is the linear span. We have the following two cases:
8

/ T In this case T is still a vertex cover of H with the same rank. Thus,
Case 1: vM ′ ∈
τ (P ′ ) = rankM ′ (T ) = rankM (T ) ≥ τ (P ).
Case 2: vM ′ ∈ T

Here, we have two subcases:

/ T \ {vM ′ }, then note that τ (P ′ ) = rankM ′ (T ) = rankM ′ (T \ {vM ′ }) + 1 =
• If vM ′ ∈
rankM ((T \ {vM ′ }) ∪ {vM }) ≥ τ (G). The third equality follows because vM is an
co-loop.
• If vM ′ ∈ T \ {vM ′ }, then as vM ′ is in general position on the flat of its neighbors, by
definition this means that all of the neighbors of vM ′ are also present in T \ {vM ′ }.
Since vM and vM ′ have the same neighbors (as the graph H has not been modified),
all of the neighbors of vM belong to in T \ vM ′ . Thus, T \ {vM ′ } is a vertex cover of H.
Therefore, τ (P ′ ) = rankM ′ (T ) = rankM ′ (T ) = rankM ′ (T \ vM ′ ) = rankM (T \ vM ′ ) ≥
τ (P ). The second equality crucially relies on the observation that rank of a set is
equal to the rank of the span of the set.
This completes the proof of the lemma.
Lemma 5 (see Proposition 4.3 in [22]). Let P = (H, M ) be a graph-matroid pair, and let v
be a vertex of H that is contained in a flat spanned by its neighbors. Let P ′ = P/v. Then,
τ (P ′ ) = τ (P ) − 1.
Proof. Recall that the contraction of a vertex v in P results in the graph-matroid pair
P ′ = (H \ v, M/vM ), i.e. the vertex is deleted from the graph and contracted in the
matroid. Denote the contracted matroid M/vM by M ′ .
We first prove that τ (P ) ≤ τ (P ′ ) + 1. Let T be a minimum rank vertex cover in P ′ ,
i.e. rankM ′ (T ) = τ (P ′ ). Let W be a maximum sized independent set in I(M ′ ) contained
in T . Then, by the definition of contraction, W ∪ {v} is a maximum sized independent set
in I(M ) contained in T ∪ {v}. Moreover, T ∪ {v} is a vertex cover in H, and therefore we
get that τ (P ) ≤ rankM (T ∪ {v}) = |W ∪ {v}| = rank′M (T ) + 1 = τ (P ′ ) + 1.
Now we prove that τ (P ′ ) ≤ τ (P ) − 1. Assume that T is a minimum rank vertex cover
of P . In case v ∈
/ T , it holds that all of the neighbors of v must belong T to cover edges
incident to v. By our assumption, v is in the span of its neighbors in M . Therefore, v
necessarily belongs to the span of T . Note that T \{v} is a vertex cover of H ′ . By Lemma 3,
we have that τ (P ) = rankM (T ) = rankM ′ (T \ {v}) + 1 ≥ τ (P ′ ) + 1. This completes the
proof.

3.2

Rank Reduction

In this section we explain the first step of our compression algorithm. Formally, we want
to solve the following problem.

9

Rank Reduction
Input: An instance (G, M = In , µ(G) + k) of Rank Vertex Cover, where
n = |V (G)|.
Output: An equivalent instance (G′ , M ′ , ℓ) such that the number of rows in M ′
is at most O(k3/2 ).
Here, we give a randomized polynomial time algorithm for Rank Reduction. More
precisely, along with the input of Rank Reduction, we are given an error bound ε > 0,
and the objective is to output a “small” equivalent instance with probability at least 1 − ε.
We start with a reduction rule that reduces the rank by 2.
Reduction Rule 1 (Vertex Deletion). Let (P, ℓ) be an instance of Rank Vertex Cover,
where P = (G, M ) is a graph-matroid pair. Let v ∈ V (G) be a vertex such that vM is a
co-loop in M . Let M1 be the matrix obtained after moving the vM to a vector vM1 in
general position on the flat spanned by NG (v). Let P1 = (G, M1 ) and let P ′ = P1 /vM1 .
Then output (P ′ , ℓ − 1)
Lemma 6. Reduction Rule 1 is safe.
Proof. We need to show that (P, ℓ) is a Yes-instance if and only if (P ′ , ℓ−1) is a Yes-instance,
which follows from Lemmata 4 and 5.
Lemma 7. Let (P, ℓ) be an instance of Rank Vertex Cover, where P = (G, M ) is a
graph-matroid pair. Let (P ′ , ℓ − 1) be the output of Reduction Rule 1, where P ′ = (G′ , M ′ ).
Then rank(M ′ ) = rank(M ) − 2.
Proof. In Reduction Rule 1, we move a co-loop vM of M to a vector vM1 , obtaining a matrix
M1 . Note that vM1 lies in the span of NG (v), and therefore vM1 is not a co-loop in M1 .
Hence, we have that rank(M1 ) = rank(M )−1. By the definition of general position, it holds
that vM1 is not a loop in M1 . Notice that M ′ = M1 /vM1 . Therefore, by Observation 1,
rank(M ′ ) = rank(M1 ) − 1 = rank(M ) − 2.
The following lemma explain how to apply Reduction Rule 1 efficiently. Later we will
explain (Lemma 10) how to keep the bit length of each entries in the matrix bounded by
polynomial in k.
Lemma 8. Let M be a linear matroid with |E(M )| = n and let p > 2n be an integer. Then,
n
Reduction Rule 1 can be applied in polynomial time with success probability at least 1 − 2p .
The number of bits required for each entry in the output representation matrix is O(log p)
times the number of bits required for each entry in the input representation matrix2 .
2

We remark that we are unaware of a procedure to derandomize the application of Reduction Rule 1.

10

Proof. Let F be the set of columns in M corresponding
P to NG (v). Using formal indeterminates x = {xh : h ∈ F }, obtain a vector g(x) =
h∈F xh h. Suppose the values of
∗
the indeterminates have been fixed to some numbers x such that for any independent set
I ∈ M which does not span F , I ∪ {g(x∗ )} is also independent. We claim that g(x∗ ) is in
general position on F . By definition, if g(x∗ ) is not in general position, then there exists a
flat F ′ with g(x∗ ) ∈ F ′ \ {g(x∗ )} but it does not contain F . Let I be a basis of F ′ \ {g(x∗ )},
clearly I does not span F but I ∪ {g(x∗ )} is a dependent set, which is a contradiction due
to the choice of x∗ .
Let I be an independent set which does not span F . We need to select x in such a way
that DR,I (x) = det(M [R, I ∪ {g(x)}]) is not identically zero for some R. First of all, note
that there is a choice of R for which the polynomialP
DR,I (x) is not identically zero and
has total degree one. This is so because DR,I (x) = h∈F xh det(M [R, I ∪ {h}]); if it is
identically zero for every R, then det(M [R, I ∪ {h}]) = 0 which implies that every element
h ∈ F is spanned by I. Thus, this case does not arise due to the choice of I. If we choose
x ∈ [p]|F | uniformly at random, for some number p, then the probability that DR,I (x) = 0
is at most p1 by Schwartz-Zippel Lemma. The number of independent sets in M , which
does not span F , is at most 2n . By union bound, the probability that DR,I (x) = 0 for
n
some I, an independent set of M , is at most 2p . Therefore, the success probability is at
n
least 1 − 2p .
The procedure runs in polynomial time and the process of matroid contraction can at
most double the matrix size, this gives us the claimed bit sizes.
In the very first step of applying Reduction Rule 1, the theorem above makes the bit
sizes O(log p). On applying the the rule again the bit length of entries double each time
due to Gaussian elimination performed for the step of matroid contraction. This can make
the numbers very large. To circumvent this, we show that given a linear matroid (U, I) of
low rank and where the ground set U is small, along with a representation matrix M over
the field R, for a randomly chosen small prime q, the matrix M mod q is also a linear
representation of M (see Lemma 9). To prove this result, we first observe that for any
number n, the number of distinct prime factors is bounded by O(log n).
Observation 2. There is a constant c such that number of distinct prime factors of any
number n, denoted by ω(n), is at most c log n.
The well-known prime number theorem implies that
Proposition 1. There is a constant c such that the number of distinct prime numbers
smaller than or equal to n, denoted by π(n), is at least c logn n .
Lemma 9. Let X = (U, I) be a rank r linear matroid representable by an r × n matrix M
′
′
over R with each entry between −nc r (1/δ) and nc r (1/δ) for some constants c′ and δ. Let
ε > 0. There is a number c ∈ O(log 1ε ) such that for a prime number q chosen uniformly at
11

2r+3

2

(n log n+log(1/δ))
, the
random from the set of prime numbers smaller than or equal to c n
ε
matrix Mq = M mod q over R represents the matroid X with probability at least 1 − nε .

Proof. To prove that Mq is a representation of X (with high probability), it is enough
to show that for any basis B ∈ B(X), the corresponding columns in Mq are linearly
independent. For this purpose, consider some basis B ∈ B(X). Since B is an independent
set in M , we have that the determinant of M [⋆, B], denoted by det(M [⋆, B]), is non-zero.
The determinant of Mq [⋆, B] is equal to det(M [⋆, B]) mod q. Let a = det(M [⋆, B]), and let
b = a mod q. The value b is equal to zero only if q is prime factor of b. Since the absolute
′
value of each entry in M is at most nc r (1/δ), the absolute value of a is upper bounded by
′ 2
r!nc r (1/δ)r . By Observation 2, the number of prime factors of a is at most c1 (log(r!) +
c′ r 2 log n + r log(1/δ)) for some constant c1 . The total number of bases in X is at most nr .
Hence the cardinality of the set F = {z : z is a prime factor of det(M [⋆, B]) for some B ∈
B(X)} is at most nr · c1 (log(r!) + c′ r 2 log n + r log(1/δ)) ≤ c2 nr+1 (n log n + log(1/δ)) for
some constant c2 .
By Proposition 1, there is a constant c3 such that the number of prime factors less than
2r+3 (n log n+log(1/δ))2
is at least
or equal to c n
ε
t = c3 c

n2r+3 (n log n + log(1/δ))2
ε log( n

2r+3 (n log n+log(1/δ))2

ε

)

.

The probability that Mq is not a representation of X (denote it by Mq 6≡ M ) is,
Pr[Mq 6≡ M ] = Pr[q ∈ F ] ≤

|F |
t

2r+3

≤

2

n
(n log n+log(1/δ))
) ε
c2 log(
ε
· r+1
·
c3 c n (n log n + log(1/δ)) n

For any ε > 0, there is a number c ∈ O(log 1ε ) such that the above probability is at most
ε
n . This completes the proof of the lemma.
By combining Lemmata 8 and 9, we can apply Reduction Rule 1, such that each entry
in the output representation matrix has bounded value.
Lemma 10. Given ε > 0, Reduction Rule 1 can be applied in polynomial time with success
probability at least 1 − nε . Moreover, each entry in the output representation matrix is at

most c n

2r+3 (n log n+log(1/ǫ))2

ǫ

, where c ∈ O(log 1ǫ ).

Proof. Let M be the input representation matrix. Let ǫ′ = ε/(2n). Now we apply Lemma 8
n
using p > 2ǫ′ . Let M ′ be the output representation matrix of Lemma 8. By Lemma 8, M ′
represents M with probability at least 1 − ǫ′ . Observe that the absolute values of matrix
entries are bounded by the value of q as given in Lemma 9, thus each entry in M ′ has
′
absolute value bounded by nc n /ǫ2 for some constant c′ . Now, applying Lemma 9 again
completes the proof.
12

We would like to apply Reduction Rule 1 as may times as possible in order to obtain
a “good” bound on the rank of the matroid. However, for this purpose, after applying
Reduction Rule 1 with respect to some co-loop of the matroid, some other co-loops need to
remain co-loops. Thus, instead of applying Reduction Rule 1 blindly, we choose vectors vM
whose vertices belong to a predetermined independent set. To understand the advantage
behind a more careful choice of the vectors vM , suppose that we are given an independent
set U in the graph G such that every vertex in it is a co-loop in the matroid. Then, after
we apply Reduction Rule 1 with one of the vertices in U , it holds that every other vertex in
U is still a co-loop (by Lemma 1 and Observation 1). In order to find a large independent
set (in order to apply Reduction Rule 1 many times), we use the following two known
algorithmic results about Vertex Cover Above MM.
Lemma 11 ([21]). There is a 2.3146k · nO(1) -time deterministic algorithm for Vertex
Cover Above MM.
Recall that for a graph G, we let β(G) denote the vertex cover number of G.
Lemma 12 ([23]). For any ǫ > 0, there is a randomized polynomial-time approximation
algorithm
that given a graph G, outputs a vertex cover of G of cardinality at most µ(G) +
√
O( log n)(β(G) − µ(G)), with probability at least 1 − ǫ.
In what follows, we also need the following general lemma about linear matroids.
Lemma 13 ([13]). Let M be an a × b matrix representing some matroid. If M ′ is a matrix
consisting of a row basis of M then M ′ represents the same matroid as M .
We are now ready to give the main lemma of this subsection.
Lemma 14. There is a polynomial time randomized algorithm that given an instance
(G, M = In , µ(G) + k) of Rank Vertex Cover and ε̂ > 0, with probability at least 1 − ε̂
outputs an equivalent instance (G′ , M ′ , ℓ) of Rank Vertex Cover such that the number
of rows in M ′ is at most O(k3/2 ). Here, M ′ is a matrix over the field R where each entry
is Õ(k5/2 + log(1/ε̂)) bits long.
Proof. Recall that n = |V (G)|. If k ≤ log n, then we use Lemma 11 to solve the problem
in polynomial time. Next, we assume that log n < k. Let δ = ε̂/2. Now, by using
Lemma
12, in polynomial time we obtain a vertex cover Y of G of size at most µ(G) +
√
′
c log n · k ≤ µ(G) + c′ · k3/2 , with probability at least 1 − δ, where c′ is some constant.
If we fail to compute such a vertex cover, then we output an arbitrary constant sized
instance as output; and this will happen only with probability at most δ. Otherwise, let
S = V (G) \ Y . Since Y is a vertex cover of G, we have that S is an independent set of
G. Hence, |S| ≥ n − (µ(G) + c′ · k3/2 ). Since M = In , all the elements of M , including
the ones in S, are co-loops in M . Now, we apply Reduction Rule 1 with the elements of S
(one by one). By Lemma 1 and Observation 1, after each application of Reduction Rule 1,
13

the remaining elements in S are still co-loops. In particular, we apply Reduction Rule 1
|S| many times. Let (G′ , M ′ , ℓ) be the instance obtained after these |S| applications of
Reduction Rule 1 using Lemma 10 (substituting ε = δ in Lemma 10).
By Lemma 7, we know that after each application of Reduction Rule 1, the rank reduces
by 2. Hence,
rank(M ′ ) = rank(M ) − 2|S|


′
3/2
= n − 2 n − (µ(G) + c · k )
= −n + 2µ(G) + 2c′ · k3/2 ≤ 2c′ · k3/2

(because 2µ(G) ≤ n).

During each application of Reduction Rule 1, by Lemma 13, we can assume that the
number of rows in the representation matrix is exactly same as the rank of the matrix.
Now, we return (G′ , M ′ , ℓ) as the output. Notice that the number of rows in M ′ is at most
O(k3/2 ).
Now, we analyze the probability of success. As finding the approximate vertex cover Y
using Lemma 12 fails with probability at most δ = 2ε̂ , in order to get the required success
probability of 1 − ε̂, |S| applications of Reduction Rule 1 should succeed with probability
at least 1 − 2ε̂ . We suppose that the matrix M = In is over the field R. Recall that the
instance (G′ , M ′ , ℓ) is obtained after |S| applications of Reduction Rule 1. The failure
probability of each application of Reduction Rule 1 is at most nδ . Hence, by union bound
the probability failure in at least one application of Reduction Rule 1 is at most δ. Hence
the total probability of success is at least 1 − (δ + δ) = 1 − ε̂. By Lemma 10 each entry in
2r+3 (n log n+log(2/ε̂))2
. Hence the bits required
the output representation matrix is at most c n
ε̂
′
to represent an entry in M is at most Õ(r log n + log(2/ε̂)) = Õ(k5/2 + log(1/ε̂)).

3.3

Graph Reduction

In the previous subsection we have seen how to reduce the number of rows in the matroid.
In this subsection we move to second step of our compression algorithm. That is, to reduce
the size of the graph. Formally, we want to solve the following problem.
Graph Reduction
Input: An instance (G′ , M, ℓ) of Rank Vertex Cover such that the number
3
of rows in M is at most O(k 2 )
Output: An equivalent instance (G′′ , M ′ , ℓ) such that |V (G′′ )|, |E(G′′ )| ≤ O(k3 )
Here, we give an algorithm to reduce the number of edges in the graph. Having reduced the
number of edges, we also obtain the desired bound on the number of vertices (as isolated
vertices are discarded). Towards this, we first give some definitions and notations. In this
section, we use F to denote either a finite field or R.

14

Definition 5 (Symmetric Square). For a set of vectors S over a field F, the symmetric
square, denoted by S (2) , is defined as S (2) = {uv T + vuT : u, v ∈ S}, where the operation is
matrix multiplication. The elements of S (2) are matrices. We can define the rank function
r (2) : S (2) → Z by treating the matrices as “long” vectors over the field F.
With a rank function r (2) , the pair (S (2) ), r (2) ) forms a matroid. For details we refer
the reader to [22].
The dot product of two column vectors a, b ∈ Fn is the scalar aT b and is denoted by
ha, bi. Two properties of dot product are (i)ha, bi = hb, ai and (ii)ha, b + ci = ha, bi + ha, ci.
Definition 6. Given a vector space Fd and a subspace F of Fd , the orthogonal space of F
is defined as F ⊥ = {x ∈ Fd : hy, xi = 0 for all y ∈ F }.
The following observation can be proved using associativity of matrix multiplication
and dot product of vectors.
Observation 3. Let u, v, w be three n-length vectors. Then, uv T w = hv, wiu.
Definition 7 (2-Tuples Meeting a Flat). For a flat F in a linear matroid S (here S is a set
of vectors), the set of 2-tuples meeting F is defined as F2 := {uv T + vuT : v ∈ F, u ∈ S}.
For the sake of completeness, we prove the following lemmata using elementary techniques from linear algebra.
Lemma 15 (see Proposition 2.8 in [22]). For any flat F in a linear matroid S with rank
function r, it holds that F2 (the set of 2-tuples meeting F ) forms a flat in the matroid
(S (2) , r (2) ).
Proof. Suppose, by way of contradiction, that F2 is not a flat. Then, there exist a, b ∈ S
such that e = abT + baT ∈ S (2) is not in F2 and
r (2) (F2 ∪ {e}) = r (2) (F2 ).
As e lies in the span of F2 , there exist scalars λuv such that
X
abT + baT =
λuv (uv T + vuT ).

(1)

u∈F,v∈S

Note that neither a nor b belongs to F , because if at least one of them belongs to F ,
then e lies in F2 (by the definition of F2 ). Therefore, F 6= S and it is a proper subspace
of S, which implies that F ⊥ is non-empty (follows from Proposition 13.2 in [17]). Pick an
element x ∈ F ⊥ . By right multiplying the column matrix x with the terms in Equation 1,

15

we get
abT x + baT x =

X

λuv (uv T x + vuT x)

X

λuv hv, xiu + hu, xiv

X

λuv hv, xiu

u∈F,v∈S

hb, xia + ha, xib =
=

u∈F,v∈S

u∈F,v∈S

(2)

The second equality follows from Observation 3, and the third equality follows from
the fact that hu, xi = 0 (because u ∈ F and x ∈ F ⊥ ). Now, by taking dot product with x,
from Equation 2, we have that
X
2ha, xihb, xi =
λuv hv, xihu, xi = 0
(3)
u∈F,v∈S

The last equality follows from the fact that hu, xi = 0. As the choice of x was arbitrary,
Equations 2 and 3 hold for all x ∈ F ⊥ .
By Equation 3, for all x ∈ F ⊥ , at least one of hb, xi or ha, xi is zero. If exactly one of
hb, xi or ha, xi is zero for some x ∈ F ⊥ , then at least one of a or b is a linear combination of
vectors from F (by Equation 2) and hence it belongs to F , which is a contradiction (recall
that we have argued that both a and b do not belong to the flat F ). Now, consider the
case where both hb, xi and ha, xi are zero for all x ∈ F ⊥ . Then, both a and b belong to
F ⊥⊥ . Since F ⊥⊥ = F (in the case F is over a finite field, see Theorem 7.5 in [15]), again
we have reached a contradiction.
For a graph-matroid pair P = (H, M ) (here M represents a set of vectors), define
E(P ) ⊆ M (2) as E(P ) = {uv T + vuT : {u, v} ∈ E(H)}. Note that E(P ) forms a matroid
with the same rank function as the one of M (2) . Moreover, the elements of E(P ) are in
correspondence with the edges of H. For simplicity, we refer to an element of E(P ) as an
edge. Using Lemma 15, we prove the following lemma.
Lemma 16 (see Proposition 4.7 in [22]). Let P = (H, M ) be a graph-matroid pair, and
let r (2) be the rank function of E(P ). For an edge e that is not a co-loop in (E(P ), r (2) ), it
holds that τ (P \ e) = τ (P ).
Proof. The deletion of edges cannot increase the vertex cover number, thus τ (P \e) ≤ τ (P ).
Next, we show that it also holds that τ (P \ e) ≥ τ (P ).
Let T be a vertex cover of H \ e. Notice that T is a flat in M . Denote e = {u, v}
and F = T . If at least one of u or v lies in F , then F is a vertex cover of H and hence
τ (P \ e) ≥ τ (P ). Hence, to conclude the proof, it is sufficient to show that at least one
of u or v lies in F . Suppose, by way of contradiction, that u, v ∈
/ F . Then, the edge
T
T
e = uv + vu does not belong to F2 (the set of 2-tuples meeting F ). By Theorem 16, we
16

have that F2 is a flat in (M (2) , r (2) ). Since F is a vertex cover of H \ e, by the definition of
F2 and E(P ), we have that E(P ) \ {e} ⊆ F2 . Recall that e is not a co-loop in (E(P ), r (2) ).
This implies that e belongs to the closure of E(P ) \ {e}, and hence it belongs to its superset
F2 . We have thus reached a contradiction. This completes the proof.
Using Lemma 16, we get the following bound on the number of edges analogously to
Theorem 4.6 in [22].
Lemma 17. Let (H, M, ℓ) be an instance of Rank Vertex Cover and r = rank(M ).
Applying thereduction given by Lemma 16 on (H, M ) exhaustively results in a graph with
at most r+1
edges.
2

Proof. Observe that the dimension of the matroid (E(P ), r (2) ) is bounded by r+1
2 , and
the reduction given by Lemma 16 deletes any edge that is not a co-loop in this matroid.
In other words, once the reduction can no longer be applied, every edge is a co-loop in the
matroid (E(P ), r (2) ), and hence the graph has at most r+1
edges.
2
Lemma 17 bounds the number of edges of the graph. To bound the number of vertices
in the graph, we apply the following simple reduction rule.
Reduction Rule 2. Let (G, M, ℓ) is an instance of Rank Vertex Cover. For v ∈ V (G)
of degree 0 in G, output (G \ v, M \ v, ℓ).
Reduction Rule 2 and Lemma 17 lead us to the main result of this subsection:
Corollary 1. There is a polynomial time algorithm, which given an instance (G′ , M ′ , ℓ)
3
of Rank Vertex Cover such that the number of rows in M is at most O(k 2 ), outputs
an equivalent instance (G′′ , M ′′ , ℓ) such that |V (G′′ )|, |E(G′′ )| = O(k3 ). Here, M ′′ is a
restriction of M ′ .
By combining both the steps we get a polynomial compression of size Õ(k7 + k4.5 log(1/ε))
for Vertex Cover Above LP.

4

Conclusion

In this paper, we presented a (randomized) polynomial compression of the Vertex Cover
Above LP problem into the algebraic Rank Vertex Cover problem. With probability
at least 1−ε, the output instance is equivalent to the original instance and it is of bit length
Õ(k7 + k4.5 log(1/ε)). Here, the probability ε is part of the input. Recall that having our
polynomial compression at hand, one also obtains polynomial compressions of additional
well-known problems, such as the Odd Cycle Transversal problem, into the Rank
Vertex Cover problem.
Finally, we note that we do not know how to derandomize our polynomial compression,
and it is also not known how to derandomize the polynomial kernelization by Kratsch
17

and Wahlström [19]. Thus, to conclude our paper, we would like to pose the following
intriguing open problem: Does there exist a deterministic polynomial compression of the
Vertex Cover Above LP problem?

References
[1] R. Balasubramanian, M. R. Fellows, and V. Raman. An improved fixed-parameter
algorithm for vertex cover. Information Processing Letters, 65(3):163–168, 1998.
[2] J. F. Buss and J. Goldsmith. Nondeterminism within p. SIAM J. Comput., 22(3):560–
572, June 1993.
[3] L. S. Chandran and F. Grandoni. Refined memorization for vertex cover. Information
Processing Letters, 93(3):125–131, 2005.
[4] J. Chen, H. Fernau, I. A. Kanj, and G. Xia. Parametric duality and kernelization:
Lower bounds and upper bounds on kernel size. SIAM J. Comput., 37(4):1077–1106,
Nov. 2007.
[5] J. Chen, I. A. Kanj, and W. Jia. Vertex cover: Further observations and further
improvements. Journal of Algorithms, 41(2):280 – 301, 2001.
[6] J. Chen, I. A. Kanj, and G. Xia. Improved upper bounds for vertex cover. Theoretical
Computer Science, 411(40-42):3736–3756, 2010.
[7] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015.
[8] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut
parameterized above lower bounds. ACM Trans. Comput. Theory, 5(1):3:1–3:11, May
2013.
[9] H. Dell and D. Van Melkebeek. Satisfiability allows no nontrivial sparsification unless
the polynomial-time hierarchy collapses. Journal of the ACM (JACM), 61(4):23, 2014.
[10] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts
in Computer Science. Springer, 2013.
[11] R. G. Downey, M. R. Fellows, and U. Stege. Parameterized complexity: A framework
for systematically confronting computational intractability. In Contemporary trends in
discrete mathematics: From DIMACS and DIMATIA to the future, volume 49, pages
49–99, 1999.

18

[12] S. Garg and G. Philip. Raising the bar for vertex cover: Fixed-parameter tractability
above A higher guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2016,, pages 1152–1166. SIAM, 2016.
[13] G. Gordon and J. McNulty. Matroids: A Geometric Introduction. Cambridge University Press, 2012. Cambridge Books Online.
[14] G. Gutin, E. J. Kim, M. Lampis, and V. Mitsou. Vertex cover problem parameterized
above and below tight bounds. Theory of Computing Systems, 48(2):402–410, 2011.
[15] R. Hill. A First Course in Coding Theory. Oxford Applied Linguistics. Clarendon
Press, 1986.
[16] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential
complexity? Journal of Computer and System Sciences, 63:512–530, 2001.
[17] S. Jukna. Extremal Combinatorics: With Applications in Computer Science. Texts in
Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2011.
[18] S. Kratsch. A randomized polynomial kernelization for vertex cover with a smaller
parameter. In 24th Annual European Symposium on Algorithms, ESA 2016, volume 57
of LIPIcs, pages 59:1–59:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
[19] S. Kratsch and M. Wahlström. Representative sets and irrelevant vertices: New tools
for kernelization. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd
Annual Symposium on, pages 450–459. IEEE, 2012.
[20] M. Lampis. A kernel of order 2k − c log k for vertex cover. Information Processing
Letters, 111(23):1089–1091, 2011.
[21] D. Lokshtanov, N. Narayanaswamy, V. Raman, M. Ramanujan, and S. Saurabh. Faster
parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG), 11(2):15, 2014.
[22] L. Lovász. Flats in matroids and geometric graphs. Combinatorial Surveys, pages
45–86, 1977.
[23] S. Mishra, V. Raman, S. Saurabh, S. Sikdar, and C. R. Subramanian. The complexity of könig subgraph problems and above-guarantee vertex cover. Algorithmica,
61(4):857–881, 2011.
[24] N. Narayanaswamy, V. Raman, M. Ramanujan, and S. Saurabh. Lp can be a cure
for parameterized problems. In STACS’12 (29th Symposium on Theoretical Aspects
of Computer Science), volume 14, pages 338–349. LIPIcs, 2012.

19

[25] R. Niedermeier and P. Rossmanith. Upper bounds for vertex cover further improved.
In Annual Symposium on Theoretical Aspects of Computer Science, pages 561–570.
Springer Berlin Heidelberg, 1999.
[26] J. G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press, Inc., New York, NY, USA, 2006.
[27] V. Raman, M. Ramanujan, and S. Saurabh. Paths, flowers and vertex cover. In
European Symposium on Algorithms, pages 382–393. Springer Berlin Heidelberg, 2011.
[28] I. Razgon and B. O’Sullivan. Almost 2-sat is fixed-parameter tractable. Journal of
Computer and System Sciences, 75(8):435–450, 2009.

20

