Skip to Main content Skip to Navigation
Conference papers

Finding Induced Subgraphs via Minimal Triangulations

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 metadata

https://hal.inria.fr/inria-00455360
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:09:22 AM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM
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

173

Files downloads

195