Exact algorithms for dominating induced matching based on graph partition

DOI10.1016/J.DAM.2015.04.012MaRDI QIDQ2352792zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 6 July 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph partitionexact algorithmsgraph algorithmsdominating induced matchingbranch-and-reduce

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A dominating induced matching, also called an efficient edge domination, of a graph $G=(V,E)$ with $n=|V|$ vertices and $m=|E|$ edges is a subset $FsubseteqE$ of edges in the graph such that no two edges in $F$ share a common endpoint and each edge in $EsetminusF$ is incident with exactly one edge in $F$. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a $1.1467^n{n}^{O(1)}$-time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts $I$ and $F$, where $I$ induces an independent set (a 0-regular graph) and $F$ induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some "good vertices", branching on which by including them to either $I$ or $F$ we can effectively reduce the graph. This leads to a fast exact algorithm to this problem.

Recommendations

• Exact algorithms for minimum weighted dominating induced matching
• \(O(n)\) time algorithms for dominating induced matching problems
• Fast algorithms for some dominating induced matching problems
• A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
• Dominating induced matching in some subclasses of bipartite graphs
• Dominating induced matching in some subclasses of bipartite graphs
• On the dominating induced matching problem: spectral results and sharp bounds
• Some results on dominating induced matchings
• Exact algorithms for maximum induced matching
• An improved exact algorithm for maximum induced matching

Cites work

• A refined exact algorithm for edge dominating set
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Efficient edge domination in regular graphs
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• Exact algorithms for edge domination
• Exact exponential algorithms.
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect edge domination and efficient edge domination in graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Weighted efficient domination problem on some perfect graphs

Cited in

(10)

• An improved exact algorithm for maximum induced matching
• Perfect edge domination: hard and solvable cases
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Kernelization of edge perfect code and its variants
• Dynamics of nonlinear three-dimensionalwaves on the interface between two fluids in a channel with low-sloping bottom and top
• Modelling and solving the perfect edge domination problem
• On the dominating induced matching problem: spectral results and sharp bounds
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
• Graphs whose vertices of degree at least 2 lie in a triangle
• Exact algorithms for minimum weighted dominating induced matching

This page was built for publication: Exact algorithms for dominating induced matching based on graph partition

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