Hereditary efficiently dominatable graphs
Presented by Dr. Martin MILANIC
Type: Oral presentation
Track: Algorithmic Graph Theory
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a decomposition theorem for (bull, fork, C_4)-free graphs, we derive the forbidden induced subgraph characterization of hereditary efficiently dominatable graphs. We also present a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs, by reducing the problem to the maximum weight independent set problem in claw-free graphs.