DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010 · 75 citations · 17 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsCombinatorial OptimizationComputational ComplexityGraph AlgorithmsGraph TheoryClique AlgorithmsCliquesCombinatorial SearchComputational Complexity Of Graph AlgorithmsEnumeration Algorithms For GraphsGraph EnumerationSubgraph IsomorphismSubgraph Mining
Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems including Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques, and an integer t, it is possible in time the number of potential maximal cliques times $O(n^{O(t)})$ to find a maximum induced subgraph of treewidth t in G and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time $O(1.734601^n)$, this yields that both the problems are solvable in time $1.734601^n$ * $n^{O(t)}$.
17
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
Graph minors. II. Algorithmic aspects of tree-width
Neil Robertson, Paul Seymour · Journal of Algorithms · 1986 · 1.5K citations
J. W. Moon, Leo Moser · Israel Journal of Mathematics · 1965 · 854 citations