Algorithms for the Treewidth and Minimum Fill-in of HHD-Free Graphs

摘要

A graph is HHD-free if it does not contain a house (i.e., the complement of P(sub5)), a hole (a cycle of length at least 5) or a domino (the graph obtained from two 4-cycles) by identifying an edge in one C(sub 4) with an edge in the other C(sub 4) as an induced subgraph. The minimum fill-in problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The treewidth problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this note, the authors show that both problems are solvable in polynomial time for HHD-free graphs.