Finding Induced Subgraphs via Minimal Triangulations

Fedor V. Fomin 1, * Yngve Villanger 1
* Corresponding author
Abstract : Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulations 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 Pi_G, and an integer t, it is possible in time |Pi_G| * 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 problems are solvable in time 1.734601^n * n^(O(t)).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00455360
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:09:22 AM
Last modification on : Wednesday, February 10, 2010 - 11:11:04 AM
Long-term archiving on : Friday, June 18, 2010 - 6:14:44 PM

File

fomin_85.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455360, version 1

Collections

Citation

Fedor V. Fomin, Yngve Villanger. Finding Induced Subgraphs via Minimal Triangulations. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.383-394. ⟨inria-00455360⟩

Share

Metrics

Record views

145

Files downloads

111