NP-hard graph problems and boundary classes of graphs

DOI10.1016/j.tcs.2007.09.013zbMath1143.68058MaRDI 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

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satgraphs and independent domination. I
• The strong perfect graph theorem
• Domination in convex and chordal bipartite graphs
• Recent developments on graphs of bounded clique-width
• Distance-hereditary graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Independent domination in chordal graphs
• Computing independent sets in graphs with large girth
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Alternating cycle-free matchings
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Independent domination in finitely defined classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Some APX-completeness results for cubic graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Chordal bipartite graphs of bounded tree- and clique-width
• On maximum induced matchings in bipartite graphs
• Boundary classes of graphs for the dominating set problem
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• HAMILTONian circuits in chordal bipartite graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Betweenness, orders and interval graphs
• Totally-Balanced and Greedy Matrices
• Edge Dominating Sets in Graphs
• The NP-Completeness of Edge-Coloring
• Computing the Minimum Fill-In is NP-Complete
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Hamilton Paths in Grid Graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Characterizations of derived graphs
• On the jump number problem in hereditary classes of bipartite graphs