Finding Induced Subgraphs via Minimal Triangulations

Fedor V. Fomin 1, * Yngve Villanger 1
* Auteur correspondant
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)).
Type de document :
Communication dans un congrès
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
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 11:09:22
Dernière modification le : mercredi 10 février 2010 - 11:11:04
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:14:44

Fichier

fomin_85.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

78