Beyond NP-completeness for problems of bounded width (extended abstract)

DOI10.1145/195058.195229zbMath1345.68152OpenAlexW1966291420WikidataQ59567994 ScholiaQ59567994MaRDI QIDQ2817636

Michael R. Fellows, Michael T. Hallett, Hans L. Bodlaender

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195229

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Bandwidth of chain graphs, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Graph Minors and Parameterized Algorithm Design, Faster Exact Bandwidth, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, On fixed-parameter tractability and approximability of NP optimization problems, Online promise problems with online width metrics, The parameterized complexity of sequence alignment and consensus, Characterizations and algorithmic applications of chordal graph embeddings, \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], Parameterized circuit complexity and the \(W\) hierarchy, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}, An exponential time 2-approximation algorithm for bandwidth, Parameterized Complexity and Approximability of the SLCS Problem, Approximating the bandwidth for asteroidal triple-free graphs, Bandwidth and distortion revisited, Domino treewidth, On the difficulty of designing good classifiers, Surfing with Rod, Parameterized complexity and approximability of the longest compatible sequence problem, Bandwidth on AT-free graphs, Confronting intractability via parameters, The complexity of irredundant sets parameterized by size, Hardness of computing width parameters based on branch decompositions over the vertex set, Intervalizing k-colored graphs, On approximation intractability of the path-distance-width problem, Exact and approximate bandwidth, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Alternative parameterizations of \textsc{Metric Dimension}, On intervalizing \(k\)-colored graphs for DNA physical mapping, The complexity ecology of parameters: An illustration using bounded max leaf number, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Threshold dominating sets and an improved characterization of \(W[2\)], On the proper intervalization of colored caterpillar trees, Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs, An Exponential Time 2-Approximation Algorithm for Bandwidth, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Approximating the bandwidth via volume respecting embeddings, Bandwidth of bipartite permutation graphs in polynomial time, Parameterized computation and complexity: a new approach dealing with NP-hardness, The Proper Interval Colored Graph problem for caterpillar trees, Myhill-Nerode Methods for Hypergraphs