A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all classes of graphs with a polynomial number of minimal separators.
Track: Operations Research
Published in: 9th Annual International Conference on Industrial Engineering and Operations Management, Bangkok, Thailand
Publisher: IEOM Society International
Date of Conference: March 5
-7
, 2019
ISBN: 978-1-5323-5948-4
ISSN/E-ISSN: 2169-8767