direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.

Vincent Froese
TEL 512


Back to the research colloquium site.



Zusatzinformationen / Extras