On complexities of minus domination

DOI10.1007/978-3-319-03780-6_16MaRDI QIDQ2867118zbMATH OpenOpenAlexFDO

Authors Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Tao-Ming Wang, Yue-Li Wang, Luerbio Faria

Publication date 10 December 2013

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: A function f: V ightarrow {-1,0,1} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x in V. The minus-domination number gamma^{-}(G) is the minimum weight over all minus-domination functions. The size of a minus domination is the number of vertices that are assigned 1. In this paper we show that the minus-domination problem is fixed-parameter tractable for d-degenerate graphs when parameterized by the size of the minus-dominating set and by d. The minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs. It is NP-complete for splitgraphs. Unless P=NP there is no fixed-parameter algorithm for minus-domination. 79,1 5%

Recommendations

• On complexities of minus domination
• The algorithmic complexity of minus domination in graphs
• Minus domination in small-degree graphs
• Algorithmic aspect of minus domination on small-degree graphs
• scientific article; zbMATH DE number 1262784

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Algorithmic aspects of majority domination
• Domination, independent domination, and duality in strongly chordal graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• FPT results for signed domination
• scientific article; zbMATH DE number 6678911 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 825134 (Why is no real title available?)
• Kernelization and Lower Bounds of the Signed Domination Problem
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• Lower bound on the minus-domination number
• Minus domination in small-degree graphs
• Signed and minus domination in complete multipartite graphs.
• The algorithmic complexity of minus domination in graphs
• The extremal function for complete minors
• Totally-Balanced and Greedy Matrices
• Treewidth. Computations and approximations
• Variations of \(Y\)-dominating functions on graphs

Cited in

(7)

• Efficient minus and signed domination in graphs
• On complexities of minus domination
• Algorithms and Hardness for Signed Domination
• Algorithmic aspect of minus domination on small-degree graphs
• scientific article; zbMATH DE number 1262784 (Why is no real title available?)
• scientific article; zbMATH DE number 2080250 (Why is no real title available?)
• Minus domination in small-degree graphs

This page was built for publication: On complexities of minus domination

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