### Large induced subgraphs via triangulations and CMSO (2014)Large induced subgraphs via triangulations and CMSO (2014)

Access Restriction
Open

 Author Fomin, Fedor V. ♦ Todinca, Ioan ♦ Villanger, Yngve Source CiteSeerX Content type Text File Format PDF Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Description We obtain an algorithmic meta-theorem 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 structure (G[F], X) models ϕ, i.e. (G[F], X) = ϕ. Special cases of this optimization problem are the following generic examples. Each of these special cases contains various problems as a special subcase: • Maximum Induced Subgraph with ≤  copies of Fm-cycles, where for fixed nonnegative integers m and , the task is to find a maximum induced subgraph of a given graph with at most ` vertex-disjoint cycles of length 0 (mod m). For example, this encompasses the problems of finding a maximum induced forest or a maximum subgraph without even cycles. • Minimum F-Deletion, where for a fixed finite set of graphs F containing a planar graph, the task is to find a maximum induced subgraph of a given graph containing Educational Role Student ♦ Teacher Age Range above 22 year Educational Use Research Education Level UG and PG ♦ Career/Technical Study Learning Resource Type Article Publisher Date 2014-01-01 Publisher Institution in Proceedings of SODA 2014, SIAM