Upper domination: towards a dichotomy through boundary properties

DOI10.1007/S00453-017-0346-9zbMATH Open1391.05241arXiv1609.01510OpenAlexW2964110022MaRDI QIDQ722525FDOQ722525

Jérôme Monnot, Vadim Lozin, Shahid Hussain, Hassan AbouEisha, Bernard Ries, Victor Zamaraev

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1609.01510

zbMATH Keywords

complexity dichotomyNP-hardnessboundary classupper dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Boundary classes of graphs for the dominating set problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Boundary properties of the satisfiability problems
• NP-hard graph problems and boundary classes of graphs
• Boundary properties of graphs for algorithmic graph problems
• Recent developments on graphs of bounded clique-width
• Graph minors. V. Excluding a planar graph
• Some simplified NP-complete graph problems
• A Dichotomy for Upper Domination in Monogenic Classes
• Boundary Classes of Planar Graphs
• Clique-width for 4-vertex forbidden subgraphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Boundary properties of well-quasi-ordered sets of graphs
• Title not available (Why is that?)
• Computing independent sets in graphs with large girth
• Boundary Properties of Factorial Classes of Graphs
• Contributions to the theory of domination, independence and irredundance in graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Critical properties of graphs of bounded clique-width
• A Boundary Property for Upper Domination
• Upper Domination: Complexity and Approximation
• Algorithmic Aspects of Upper Domination: A Parameterised Perspective
• Title not available (Why is that?)
• On the computational complexity of upper fractional domination

Cited In (9)

• Title not available (Why is that?)
• In)approximability of Maximum Minimal FVS
• Title not available (Why is that?)
• 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
• Algorithmic aspects of upper edge domination
• (In)approximability of maximum minimal FVS
• Upper Clique Transversals in Graphs
• Between clique-width and linear clique-width of bipartite graphs

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)