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

DOI10.1016/J.TCS.2019.06.007zbMATH Open1434.68354arXiv1803.04327OpenAlexW2963116939WikidataQ127567155 ScholiaQ127567155MaRDI QIDQ2330102FDOQ2330102

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Total Roman domination for proper interval graphs
• A simple optimal algorithm for \(k\)-tuple dominating problem in 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)