Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
Parameterizing edge modification problems above lower bounds
Vincent Froese (TU Berlin)
For a fixed graph F, we study the parameterized complexity of a variant of the F-free Editing problem: Given a graph G and a natural number k, is it possible to modify at most k edges in G so that the resulting graph contains no induced subgraph isomorphic to F? In our variant, the input additionally contains a vertex-disjoint packing H of induced subgraphs of G, which provides a lower bound h(H) on the number of edge modifications required to transform G into an F-free graph.
While earlier works used the number k as parameter or structural parameters of the input graph G, we consider the parameter l := k − h(H) instead, that is, the number of edge modifications above the lower bound h(H). We show fixed-parameter tractability with respect to for K_3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing
when the packing H contains subgraphs with bounded modification cost. For K_3-Free Editing, we also prove NP-hardness in case of edge-disjoint packings of K_3's and l = 0, while for K_q-Free Editing and q >= 6, NP-hardness for l = 0 even holds for vertex-disjoint packings of K_q's.
This is joint work with René van Bevern and Christian Komusiewicz.
Date | Speaker | Location | Language |
---|---|---|---|
28.01.2016 16:15 | Vincent Froese | TEL 512 | English |
Back to the research colloquium site.