A complexity dichotomy for the dominating set problem

2015/05/31 by D. S. Malyshev, Malyshev, D. S.
Computer Science · #05C69 #05C85 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DM #msc:05C69 #msc:05C85

paper · pdf · doi:10.48550/arxiv.1506.00202

arxiv created 2015/05/31 · openalex publication_date 2015/05/31 · arxiv updated 2015/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.

Related

• Upper Domination: towards a dichotomy through boundary properties
• On the complexity of Dominating Set for graphs with fixed diameter
• Linear separation of connected dominating sets in graphs
• Complexity results for k-domination and \α-domination problems\n and their variants
• Domination Problems in Nowhere-Dense Classes of Graphs