New algorithms for weighted k-domination and total k-domination problems in proper interval graphs

DOI10.1016/J.TCS.2019.06.007MaRDI QIDQ2330102zbMATH OpenOpenAlexWikidataFDO

Authors Nina Chiarelli, Tatiana Romina Hartinger, V. Leoni, Martin Milanič, Maria Inés Lopez Pujato

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time algorithmproper interval graph\(k\)-dominationtotal \(k\)-domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Given a positive integer $k$, a $k$-dominating set in a graph $G$ is a set of vertices such that every vertex not in the set has at least $k$ neighbors in the set. A total $k$-dominating set, also known as a $k$-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least $k$ neighbors in the set. The problems of finding the minimum size of a $k$-dominating, respectively total $k$-dominating set, in a given graph, are referred to as $k$-domination, respectively total $k$-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total $k$-domination). On the other hand, it follows from recent work of Kang et al.~(2017) that these two families of problems are solvable in time $mathcalO(|V(G){|}^{6k+4})$ in the class of interval graphs. We develop faster algorithms for $k$-domination and total $k$-domination in the class of proper interval graphs, by means of reduction to a single shortest path computation in a derived directed acyclic graph with $mathcalO(|V(G){|}^{2k})$ nodes and $mathcalO(|V(G){|}^{4k})$ arcs. We show that a suitable implementation, which avoids constructing all arcs of the digraph, leads to a running time of $mathcalO(|V(G){|}^{3k})$. The algorithms are also applicable to the weighted case.

Recommendations

• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
• Total 2-domination of proper interval graphs
• A unified approach to domination problems on interval graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs

Cites work

• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 19197 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• scientific article; zbMATH DE number 4121429 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• (Total) vector domination for graphs with bounded branchwidth
• A linear time algorithm for liar's domination problem in proper interval graphs
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• A new characterization of proper interval graphs
• A note on domination in bipartite graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A unified approach to domination problems on interval graphs
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Approximating clique-width and branch-width
• Bounds on the \(k\)-domination number of a graph
• Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
• Dominating sequences under atomic changes with applications in Sierpiński and interval graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Efficient algorithms for Roman domination on some classes of graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Finding outer-connected dominating sets in interval graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
• Independent domination in chordal graphs
• Introduction to algorithms.
• Labeling algorithms for domination problems in sun-free chordal graphs
• Latency-bounded target set selection in social networks
• Linear time algorithms on circular-arc graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Metric characterizations of proper interval graphs and tree-clique graphs
• Minimum 2-tuple dominating set of an interval graph
• On Dominating Sets and Independent Sets of Graphs
• On \(k\)-domination and \(j\)-independence in graphs
• On the algorithmic complexity of \(k\)-tuple total domination
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the total \(k\)-domination number of graphs
• Onk-domination and minimum degree in graphs
• Optimal greedy algorithms for indifference graphs
• Paired domination on interval and circular-arc graphs
• Power domination in circular-arc graphs
• Subexponential fixed-parameter algorithms for partial vector domination
• The Roberts characterization of proper and unit interval graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The eternal dominating set problem for proper interval graphs
• The parameterized complexity of domination-type problems and application to linear codes
• Total domination in graphs
• Total domination in interval graphs
• Total domination in interval graphs
• Total domination in interval graphs revisited
• Trees with equal 2-domination and 2-independence numbers
• Variations of \(Y\)-dominating functions on graphs
• Weighted independent perfect domination on cocomparability graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• \(k\)-tuple domination in graphs
• \(k\)-tuple total domination in graphs

Cited in

(11)

• A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
• Total Roman domination for proper interval graphs
• Algorithmic results of independent \(k\)-domination on weighted graphs
• An algorithm for the secure total domination problem in proper interval graphs
• Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination
• Total 2-domination of proper interval graphs
• The k-neighbor, r-domination problems on interval graphs
• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
• Defensive domination in proper interval graphs
• A linear algorithm for double Roman domination of proper interval graphs
• Algorithm and hardness results on neighborhood total domination in graphs

This page was built for publication: New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

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