Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs

被引：33

作者：

Austrin, Per ^{[1
]}

Khot, Subhash ^{[2
]}

Safra, Muli ^{[3
]}

机构：

[1] Royal Inst Technol, KTH, Stockholm, Sweden

[2] CUNY, New York, NY USA

[3] Tel Aviv Univ, IL-69978 Tel Aviv, Israel

来源：

PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY | 2009年

基金：

美国国家科学基金会; 欧洲研究理事会;

关键词：

APPROXIMATE; ALGORITHMS; MIGHT; CUT;

D O I：

10.1109/CCC.2009.38

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + O-d (1)) log logd/log d. This exactly matches the algorithmic result of Halperin [1] up to the O-d(1) term. Independent Set is Unique Games-hard to approximate to within a factor O(d/log(2)d). This improves the d/log(O(1)) (d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].

引用

页码：74 / +

页数：3

共 15 条

[1] Balanced Max 2-Sat Might Not be the Hardest [J].

Austrin, Per .

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, :189-197

[2] On approximate graph colouring and MAX-k-CUT algorithms based on the υ-function [J].

De Klerk, E ;

Pasechnik, DV ;

Warners, JP .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (03) :267-294

[3] On the hardness of approximating minimum vertex cover [J].

Dinur, I ;

Safra, S .

ANNALS OF MATHEMATICS, 2005, 162 (01) :439-485

[4]

DINUR I, 2006, ACM STOC, P344

[5] Approximating maximum clique by removing subgraphs [J].

Feige, U .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (02) :219-225

[6]

Halldorsson M. M., 1999, Computing and Combinatorics. 5th Annual International Conference, COCOON'99. Proceedings (Lecture Notes in Computer Science Vol.1627), P261

[7] Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs [J].

Halperin, E .

SIAM JOURNAL ON COMPUTING, 2002, 31 (05) :1608-1623

[8] Clique is hard to approximate within n1-ε [J].

Håstad, J .

ACTA MATHEMATICA, 1999, 182 (01) :105-142

[9]

KHOT S, 2002, ACM S THEOR COMP STO, P767

[10] Vertex cover might be hard to approximate to within 2-ε [J].

Khot, Subhash ;

Regev, Oded .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (03) :335-349

← 1 2 →