NP-hard graph problems and boundary classes of graphs

DOI10.1016/j.tcs.2007.09.013zbMath1143.68058OpenAlexW2081207138MaRDI QIDQ2465640

R. Boliac, Vadim V. Lozin, Dmitry V. Korobitsyn, Vladimir E. Alekseev

Publication date: 7 January 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.09.013

zbMATH Keywords

computational complexity hereditary class of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Vertex coloring of graphs with few obstructions ⋮ Unnamed Item ⋮ Boundary classes for graph problems involving non-local properties ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ The maximum number of maximum dissociation sets in trees ⋮ A decidability result for the dominating set problem ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ On spectral extrema of graphs with given order and dissociation number ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Constant-degree graph expansions that preserve treewidth ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Unnamed Item ⋮ Boundary graph classes for some maximum induced subgraph problems ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Boundary properties of the satisfiability problems ⋮ The coloring problem for classes with two small obstructions ⋮ Two complexity results for the vertex coloring problem ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Critical hereditary graph classes: a survey ⋮ New potential functions for greedy independence and coloring ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ max-cut and Containment Relations in Graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Computing coverage kernels under restricted settings ⋮ A Boundary Property for Upper Domination ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ Critical elements in combinatorially closed families of graph classes ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

Cites Work