Hardness of computing width parameters based on branch decompositions over the vertex set

被引：16

作者：

Saether, Sigve Hortemo ^{[1
]}

Vatshelle, Martin ^{[1
]}

机构：

[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 615卷

关键词：

NP-hard; Boolean-width; Maximum induced matching-width; Branch decompositions; COMPLEXITY;

D O I：

10.1016/j.tcs.2015.11.039

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Many width parameters of graphs are defined using branch decompositions over the vertex set of the graph and a corresponding cut-function. In this paper, we give a general framework for showing hardness of many width parameters defined in such a way, by reducing from the problem of deciding the exact value of the cut-function. We show that this implies NP-hardness for deciding both boolean-width and mim-width, and that mim-width is W[1]-hard, and not in APX unless NP = ZPP. (c) 2015 Elsevier B.V. All rights reserved.

引用

页码：120 / 125

页数：6

共 12 条

[1] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE
ARNBORG, S
CORNEIL, DG
PROSKUROWSKI, A
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02): : 277 - 284
[2] Bodlaender H. L., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P449, DOI 10.1145/195058.195229
[3] INDUCED MATCHINGS
CAMERON, K
[J]. DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) : 97 - 102
[4] Dregi M. S., 2014, P INT C AUT LANG PRO, P405
[5] Elbassioni K, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1210
[6] CLIQUE-WIDTH IS NP-COMPLETE
Fellows, Michael R.
Rosamond, Frances A.
Rotics, Udi
Szeider, Stefan
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) : 909 - 939
[7] The parameterized complexity of the induced matching problem
Moser, Hannes
Sikdar, Somnath
[J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 715 - 727
[8] Approximating Rank-Width and Clique-Width Quickly
Oum, Sang-Il
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2008, 5 (01)
[9] THE COMPLEXITY OF COUNTING CUTS AND OF COMPUTING THE PROBABILITY THAT A GRAPH IS CONNECTED
PROVAN, JS
BALL, MO
[J]. SIAM JOURNAL ON COMPUTING, 1983, 12 (04) : 777 - 788
[10] CALL ROUTING AND THE RATCATCHER
SEYMOUR, PD
THOMAS, R
[J]. COMBINATORICA, 1994, 14 (02) : 217 - 241

← 1 2 →