Potential Maximal Cliques Parameterized by Edge Clique Cover
share
We show that the number of minimal separators on graphs with edge clique cover of size cc is O(2^cc) and the number of potential maximal cliques is O(3^cc). Furthermore, potential maximal cliques can be listed in O^*(3^cc') time when an edge clique cover of size cc' is given. This yields O^*(3^cc') time algorithms for all problems in the framework of potential maximal cliques, for example Treewidth, Minimum Fill-In and Maximum Independent Set. The parameter cc is motivated by practice: our results imply that Treewidth can be solved in O^*(3^m) time for primal graphs of CSP instances with m constraints. Furthermore, Generalized Hypertree Width and Fractional Hypertree Width can be solved in O^*(4^m) and O^*(3^m) time. There are many real CSP applications where the number of constraints is much smaller than the number of variables. Other applications of the parameterization include Perfect Phylogeny. The bounds on the number of minimal separators and the number of potential maximal cliques are tight, and cc is orthogonal to the existing parameterizations for potential maximal cliques.
READ FULL TEXT