New polynomial cases of the weighted efficient domination problem

DOI10.1007/978-3-642-40313-2_19MaRDI QIDQ2849909zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Martin Milanič, Ragnar Nevries

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

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

zbMATH Keywords

\(P _{k }\)-free graphsefficient dominationpolynomial-time algorithmrobust algorithm

Mathematics Subject Classification ID

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

Abstract: Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes. In particular, the ED problem remains NP-complete for 2P3-free graphs and thus for P7-free graphs. We show that the weighted version of the problem (abbreviated WED) is solvable in polynomial time on various subclasses of 2P3-free and P7-free graphs, including (P2+P4)-free graphs, P5-free graphs and other classes. Furthermore, we show that a minimum weight e.d. consisting only of vertices of degree at most 2 (if one exists) can be found in polynomial time. This contrasts with our NP-completeness result for the ED problem on planar bipartite graphs with maximum degree 3.

Recommendations

• Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs
• Weighted efficient domination for P₆-free and for P₅-free graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Weighted efficient domination for P₅-free and P₆-free graphs
• Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs

Cited in

(23)

• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Weighted efficient domination problem on some perfect graphs
• A dichotomy for weighted efficient dominating sets with bounded degree vertices
• Perfect edge domination: hard and solvable cases
• Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
• Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs
• The weighted perfect domination problem and its variants
• On efficient domination for some classes of H-free bipartite graphs
• A note on efficient domination in a superclass of \(P_5\)-free graphs
• Efficient domination and efficient edge domination: a brief survey
• Efficient domination for some subclasses of P₆-free graphs in polynomial time
• Weighted efficient domination for P₅-free and P₆-free graphs
• Efficient domination through eigenvalues
• Weighted efficient domination for P₆-free and for P₅-free graphs
• Structure of squares and efficient domination in graph classes
• On weighted efficient total domination
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Weighted efficient domination for P₈-free bipartite graphs in polynomial time
• A study on the weighted efficient domination problem for C₄-free bipartite graphs
• Weighted efficient domination in two subclasses of P₆-free graphs

This page was built for publication: New polynomial cases of the weighted efficient domination problem

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