Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs (Q805638)

A set of vertices in a graph is called a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The problem of locating a dominating clique of minimum cardinality is known to be NP-complete for general chordal graphs. The author shows that the problem is polynomially solvable for two important subclasses of chordal graphs: strongly chordal graphs and undirected path graphs. Special structural properties of these classes of graphs are used to design an O(m log n) algorithm for strongly chordal graphs an \(O(n^ 4)\) algorithm for undirected path graphs.