NP-hard graph problems and boundary classes of graphs

DOI10.1016/J.TCS.2007.09.013MaRDI QIDQ2465640zbMATH OpenOpenAlexFDO

Authors R. Boliac, Dmitry V. Korobitsyn, Vadim Lozin, V. 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 complexityhereditary class of graphs

Mathematics Subject Classification ID

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

Recommendations

• Boundary classes of graphs for the dominating set problem
• Boundary classes of graphs for some recognition problems
• Boundary classes for graph problems involving non-local properties
• Boundary graph classes for some maximum induced subgraph problems
• Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Algorithmic graph theory and perfect graphs
• Alternating cycle-free matchings
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Betweenness, orders and interval graphs
• Boundary classes of graphs for the dominating set problem
• Characterizations of derived graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Computing independent sets in graphs with large girth
• Computing the Minimum Fill-In is NP-Complete
• Distance-hereditary graphs
• Domination in convex and chordal bipartite graphs
• Edge Dominating Sets in Graphs
• 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
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite graphs
• scientific article; zbMATH DE number 4204394 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 468640 (Why is no real title available?)
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• Independent domination in chordal graphs
• Independent domination in finitely defined classes of graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On maximum induced matchings in bipartite graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the clique-width of some perfect graph classes
• On the jump number problem in hereditary classes of bipartite graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Recent developments on graphs of bounded clique-width
• Satgraphs and independent domination. I
• Some APX-completeness results for cubic graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• The NP-Completeness of Edge-Coloring
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The strong perfect graph theorem
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Threshold graphs and related topics
• Totally-Balanced and Greedy Matrices

Cited in

(66)

• A boundary class for the k-path partition problem
• Boundary classes of graphs for the dominating set problem
• Hard problems that quickly become very easy
• 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 dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• On universally easy classes for NP-complete problems
• A boundary property for upper domination
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Max-Cut and containment relations in graphs
• Boundary classes of graphs for some recognition problems
• 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
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Tree-Width and Optimization in Bounded Degree Graphs
• Boundary Classes of Planar Graphs
• Boundary properties of well-quasi-ordered sets of graphs
• A decidability result for the dominating set problem
• Tracking the P-NP boundary for well-covered graphs
• \textsc{max-cut} and containment relations in graphs
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
• The coloring problem for classes with two small obstructions
• NP-hardness of multiple bondage in graphs
• Boundary properties of factorial classes of graphs
• Two complexity results for the vertex coloring problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Nearest neighbour graph realizability is NP-hard
• Critical hereditary graph classes: a survey
• The weighted k-path vertex cover problem on series-parallel graphs
• Critical elements in combinatorially closed families of graph classes
• Boundary properties of graphs for algorithmic graph problems
• Computing coverage kernels under restricted settings
• A \(5k\)-vertex kernel for 3-path vertex cover
• scientific article; zbMATH DE number 7742925 (Why is no real title available?)
• The maximum number of maximum dissociation sets in trees
• A fast approximation algorithm for the maximum 2-packing set problem on planar 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
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• The maximum number of maximum generalized 4-independent sets in trees
• On the A_-index of graphs with given order and dissociation number
• Maximum generalized 4-independent sets in subcubic trees
• A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
• A sharp lower bound on the generalized 4-independence number
• Dissociation in circulant graphs and integer distance graphs
• Complete complexity dichotomies for the dominating set problem
• On spectral extrema of graphs with given order and generalized 4-independence number
• Complexity framework for forbidden subgraphs. I: The framework
• Graph homomorphism, monotone classes and bounded pathwidth
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Upper domination: towards a dichotomy through boundary properties
• Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs

This page was built for publication: NP-hard graph problems and boundary classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465640)