FINDING GOOD APPROXIMATE VERTEX AND EDGE PARTITIONS IS NP-HARD

被引：203
|
作者：
BUI, TN
JONES, C
机构：
[1] Computer Science Department, The Pennsylvania State University, University Park
来源：
INFORMATION PROCESSING LETTERS | 1992年 / 42卷 / 03期
关键词：
COMBINATORIAL PROBLEMS; APPROXIMATION ALGORITHMS; GRAPH PARTITIONING;
D O I：
10.1016/0020-0190(92)90140-Q
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper we show that for n-vertex graphs with maximum degree 3, and for any fixed epsilon > 0, it is NP-hard to find alpha-edge separators and alpha-vertex separators of size no more than OPT + n1/2-epsilon, where OPT is the size of the optimal solution. For general graphs we show that it is NP-hard to find an alpha-edge separator of size no more than OPT + n2-epsilon. We also show that an O(f(n))-approximation algorithm for finding alpha-vertex separators of maximum degree 3 graphs can be used to find an O(f(n5))-approximation algorithm for finding alpha-edge separators of general graphs. Since it is NP-hard to find optimal alpha-edge separators for general graphs this means that it is NP-hard to find optimal vertex separators even when restricted to maximum degree 3 graphs.
引用
收藏
页码：153 / 159
页数：7
相关论文
共 50 条
12345