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
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.383-394, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

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
Document(s) archivé(s) le : 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. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.383-394, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455360>

Share

Metrics

Record views

120

Document downloads

66