Top

Journal of Combinatorial Optimization

Published in:

01-07-2016

A complexity dichotomy and a new boundary class for the dominating set problem

Author: D. S. Malyshev

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.

previous article New analysis and computational study for the planar connected dominating set problem

next article 2-Distance coloring of a planar graph without 3, 4, 7-cycles

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

AbouEisha H, Hussain S, Lozin V, Monnot J, Ries B (2014) A dichotomy for upper domination in monogenic classes. In: Combinatorial optimization and applications. Lecture notes in computer science, vol 8881. Springer, pp 258–267

Alekseev V (1983) On the local restrictions effect on the complexity of finding the graph independence number. In: Combinatorial-algebraic methods in applied mathematics. Gorkiy University Press, Gorkiy, pp 3–13 [in russian]

Alekseev V (1999) A polynomial algorithm for finding the largest independent sets in fork-free graphs. Diskretn Analiz i Issled Oper Ser 1 6(4):3–19 [in russian]MATH

Alekseev V (2003) On easy and hard hereditary classes of graphs with respect to the independent set problem. Discret Appl Math 132(1–3):17–26MathSciNetCrossRefMATH

Alekseev V, Boliac R, Korobitsyn D, Lozin V (2007) NP-hard graph problems and boundary classes of graphs. Theor Comput Sci 389(1–2):219–236MathSciNetCrossRefMATH

Alekseev V, Korobitsyn D, Lozin V (2004) Boundary classes of graphs for the dominating set problem. Discret Math 285(1–3):1–6MathSciNetCrossRefMATH

Bacsó G, Tuza Z (1990) Dominating cliques in \(P_5\)-free graphs. Period Math Hung 21:303–308CrossRefMATH

Bertossi A (1984) Dominating sets for split and bipartite graphs. Inform Process Lett 19(1):37–40MathSciNetCrossRefMATH

Brandstädt A, Dragan F, Le H-O, Mosca R (2005) New graph classes of bounded clique-width. Theory Comput Syst 38(5):623–645MathSciNetCrossRefMATH

Broersma H, Golovach P, Paulusma D, Song J (2012) Updating the complexity status of coloring graphs without a fixed induced linear forest. Theor Comput Sci 414(1):9–19MathSciNetCrossRefMATH

Clark B, Colbourn C, Johnson D (1990) Unit disk graphs. Ann Discret Math 48:165–177MathSciNetCrossRefMATH

Courcelle B, Makowsky J, Rotics U (2000) Linear time optimization problems on graphs of bounded clique width. Theory Comput Syst 33(2):125–150MathSciNetCrossRefMATH

Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York 1979MATH

Golovach P, Paulusma D (2014) List coloring in the absence of two subgraphs. Discret Appl Math 166:123–130MathSciNetCrossRefMATH

Golovach P, Paulusma D, Ries B (2015) Coloring graphs characterized by a forbidden subgraph. Discret Appl Math 180(1):101–110MathSciNetCrossRefMATH

Golovach P, Paulusma D, Song J (2013) 4-coloring \(H\)-free graphs when \(H\) is small. Discret Appl Math 161(1–2):140–150MathSciNetCrossRefMATH

Graphs: 5-vertices. Information system on graph classes and their inclusions. http://www.graphclasses.org/smallgraphs.html#nodes5. Accessed 27 Jan 2015

Graphclass: AT-free. Information system on graph classes and their inclusions. http://www.graphclasses.org/classes/gc_61.html. Accessed 27 Jan 2015

Korobitsyn D (1992) On the complexity of domination number determination in monogenic classes of graphs. Discret Math Appl 2(2):191–199MathSciNet

Kral’ D, Kratochvil J, Tuza Z, Woeginger G (2001) Complexity of coloring graphs without forbidden induced subgraphs. Lect. Notes Comput Sci 2204:254–262MathSciNetCrossRefMATH

Kratsch D (2000) Domination and total domination in asteroidal triple-free graphs. Discret Appl Math 99(1–3):111–123MathSciNetCrossRefMATH

Kratsch S, Schweitzer P (2012) Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Lect Notes Comput Sci 7551:34–45MathSciNetCrossRefMATH

Lokshtantov D, Vatshelle M, Villanger Y (2014) Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp 570–581

Lozin V (2008) Boundary classes of planar graphs. Comb Probab Comput 17(2):287–295MathSciNetCrossRefMATH

Lozin V, Malyshev D (2015) Vertex coloring of graphs with few obstructions. Discret Appl Math. doi:10.1016/j.dam.2015.02.015

Lozin V, Mosca R (2004) Independent sets in extensions of \(2K_2\)-free graphs. Discret Appl Math 146(1): 74–80MathSciNetCrossRefMATH

Malyshev D (2013) The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. Discret Math (submitted)

Malyshev D (2014) The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Sib Electron Math Rep 11:811–822MATH

Malyshev D (2014) Classes of graphs critical for the edge list-ranking problem. J Appl Ind Math 8(2): 245–255MathSciNetCrossRef

Problem: Domination. Information system on graph classes and their inclusions. http://www.graphclasses.org/classes/problem_Domination.html. Accessed 27 Jan 2015

Schweitzer P (2014) Towards an isomorphism dichotomy for hereditary graph classes. arXiv, arXiv:1411.1977

Yannakakis M, Gavril F (1980) Edge dominating sets in graphs. SIAM J Appl Math 38(3):364–372MathSciNetCrossRefMATH

Zverovich I (2003) The domination number of \((K_p, P_5)\)-free graphs. Australas J Comb 27:95–100MathSciNetMATH

Title: A complexity dichotomy and a new boundary class for the dominating set problem
Author: D. S. Malyshev
Publication date: 01-07-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9872-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Computing unique maximum matchings in time for König–Egerváry graphs and unicyclic graphs

Algorithms for the workflow satisfiability problem engineered for counting constraints

Efficient approximation algorithms for computing k disjoint constrained shortest paths

Strong minimum energy hierarchical topology in wireless sensor networks

Constrained pairwise and center-star sequences alignment problems

List edge and list total coloring of planar graphs with maximum degree 8

Premium Partner