Thumbnail
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