An Exact Algorithm for Lowest Edge Dominating Set

Ken IWAIDE  Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.3   pp.414-421
Publication Date: 2017/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
Category: 
Keyword: 
graph theory,  edge dominating set,  algorithm,  NP-completeness,  fixed parameter tractable,  

Full Text: PDF(304.7KB)
>>Buy this Article


Summary: 
Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.