2015/01/01 by Fedor V. Fomin, Ioan Todinca, Yngve Villanger · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Exponential time hypothesis #Graph #Graph Labeling and Dimension Problems #Induced subgraph #Line graph #Mathematics #Parameterized complexity #Pathwidth #Running time #Time complexity #Treewidth #Vertex (graph theory)
paper · doi:10.1137/140964801
openalex publication_date 2015/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
We obtain an algorithmic metatheorem for the following optimization problem. Let φ be a counting monadic second order logic (CMSO) formula and t≥ 0 be an integer. For a given graph G=(V,E), the task is to maximize |X| subject to the following: there is a set F⊆ V such that X⊆ F , the subgraph G[F] induced by F is of treewidth at most t, and the structure (G[F],X) models φ, i.e., (G[F],X)\modelsφ. We give an algorithm solving this optimization problem on any n-vertex graph G in time \cal O(|ΠG| ⋅ nt+4⋅ f(t,φ)), where ΠG is the set of all potential maximal cliques in G and f is a function of t and φ only. Pipelined with the known bounds on the number of potential maximal cliques in different graph classes, there are a plethora of algorithmic consequences extending and subsuming many known results on polynomial-time algorithms for graph classes. We also show that all potential maximal cliques of G can be enumerated in time \cal O(1.7347n). This implies the existence of an exact exponential algorithm of running time \cal O(1.7347n) for many NP-hard problems related to finding maximum induced subgraphs with different properties.