Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651911 | Electronic Notes in Discrete Mathematics | 2015 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics