2010 | OriginalPaper | Chapter
Some Results on Incremental Vertex Cover Problem
Author : Wenqiang Dai
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the classical
k
-vertex cover problem, we wish to find a minimum weight set of vertices that covers at least
k
edges. In the incremental version of the
k
-vertex cover problem, we wish to find a sequence of vertices, such that if we choose the smallest prefix of vertices in the sequence that covers at least
k
edges, this solution is close in value to that of the optimal
k
-vertex cover solution. The maximum ratio is called
competitive ratio
. Previously the known upper bound of competitive ratio was 4
α
, where
α
is the approximation ratio of the
k
-vertex cover problem. And the known lower bound was 1.36 unless
P
=
NP
, or 2 −
ε
for any constant
ε
assuming the Unique Game Conjecture. In this paper we present some new results for this problem. Firstly we prove that, without any computational complexity assumption, the lower bound of competitive ratio of incremental vertex cover problem is
φ
, where
$\phi=\frac{\sqrt{5}+1}{2}\approx 1.618$
is the golden ratio. We then consider the restricted versions where
k
is restricted to one of two given values(Named 2-IVC problem) and one of three given values(Named 3-IVC problem). For 2-IVC problem, we give an algorithm to prove that the competitive ratio is at most
φα
. This incremental algorithm is also optimal for 2-IVC problem if we are permitted to use non-polynomial time. For the 3-IVC problem, we give an incremental algorithm with ratio factor
$(1+\sqrt{2})\alpha$
.