FINDING GOOD APPROXIMATE VERTEX AND EDGE PARTITIONS IS NP-HARD

被引：204

作者：

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

共 9 条

[1] BUI T, 1989, ACM IEEE D, P775, DOI 10.1145/74382.74527
[2] GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR
BUI, TN
CHAUDHURI, S
LEIGHTON, FT
SIPSER, M
[J]. COMBINATORICA, 1987, 7 (02) : 171 - 191
[3] BUI TN, 1990, 1990 P INT C PAR PRO, V3, P150
[4] BUI TN, 1992, IN PRESS SIAM J COMP
[5] Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[6] Kernighan B. W., 1970, Bell System Technical Journal, V49, P291
[7] Leighton T., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P422, DOI 10.1109/SFCS.1988.21958
[8] A HEURISTIC ALGORITHM FOR SMALL SEPARATORS IN ARBITRARY GRAPHS
PLAISTED, DA
[J]. SIAM JOURNAL ON COMPUTING, 1990, 19 (02) : 267 - 280
[9] Rao S., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P225, DOI 10.1109/SFCS.1987.26

← 1 →