Upper domination: towards a dichotomy through boundary properties
From MaRDI portal
Publication:722525
Abstract: An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in classes of graphs defined by finitely many forbidden induced subgraphs and conjecture that the problem admits a dichotomy in this family, i.e. it is either NP-hard or polynomial-time solvable for each class in the family. A helpful tool to study the complexity of an algorithmic problem on finitely defined classes of graphs is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem and prove the dichotomy for classes defined by a single forbidden induced subgraph.
Recommendations
Cites work
- scientific article; zbMATH DE number 4204394 (Why is no real title available?)
- scientific article; zbMATH DE number 4049086 (Why is no real title available?)
- A boundary property for upper domination
- A dichotomy for upper domination in monogenic classes
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Boundary Classes of Planar Graphs
- Boundary classes of graphs for the dominating set problem
- Boundary properties of factorial classes of graphs
- Boundary properties of graphs for algorithmic graph problems
- Boundary properties of the satisfiability problems
- Boundary properties of well-quasi-ordered sets of graphs
- Chordal graphs and upper irredundance, upper domination and independence
- Clique-width for 4-vertex forbidden subgraphs
- Computing independent sets in graphs with large girth
- Contributions to the theory of domination, independence and irredundance in graphs
- Critical properties of graphs of bounded clique-width
- Graph minors. V. Excluding a planar graph
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- NP-hard graph problems and boundary classes of graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- On the computational complexity of upper fractional domination
- Recent developments on graphs of bounded clique-width
- Some simplified NP-complete graph problems
- Upper bounds to the clique width of graphs
- Upper domination: complexity and approximation
Cited in
(14)- Between clique-width and linear clique-width of bipartite graphs
- A boundary property for upper domination
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Algorithmic aspects of upper edge domination
- Upper Clique Transversals in Graphs
- (In)approximability of maximum minimal FVS
- scientific article; zbMATH DE number 2196476 (Why is no real title available?)
- scientific article; zbMATH DE number 7742925 (Why is no real title available?)
- In)approximability of Maximum Minimal FVS
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Boundary classes of graphs for the dominating set problem
- Binary programming formulations for the upper domination problem
- A complexity dichotomy and a new boundary class for the dominating set problem
- A dichotomy for upper domination in monogenic classes
This page was built for publication: Upper domination: towards a dichotomy through boundary properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722525)
