2026-07-21T23:35:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2470 2024-03-06T10:33:24Z ddc:004 open_access

Finding Induced Subgraphs via Minimal Triangulations Fomin, Fedor V. Villanger, Yngve Bounded treewidth minimal triangulation moderately exponential time algorithms 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)}$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Yngve Villanger 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2470 urn:nbn:de:0030-drops-24708 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2470 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode