Parameterizing edge modification problems above lower bounds

Author name not available (Why is that?)

Abstract: 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

m a t h c a l H

of induced subgraphs of

G

, which provides a lower bound

h (m a t h c a l 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 instead the parameter

e l l : = k - h (m a t h c a l H)

, that is, the number of edge modifications above the lower bound

h (m a t h c a l H)

. We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to

e l l

for

K_{3}

-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing

m a t h c a l H

contains subgraphs with bounded solution size. For

K_{3}

-Free Editing, we also prove NP-hardness in case of edge-disjoint packings of

K_{3}

s and

e l l = 0

, while for

K_{q}

-Free Editing and

q g e 6

, NP-hardness for

e l l = 0

even holds for vertex-disjoint packings of

K_{q}

s. In addition, we provide NP-hardness results for

F

-free Vertex Deletion, were the aim is to delete a minimum number of vertices to make the input graph

F

-free.

No records found.

No records found.

This page was built for publication: Parameterizing edge modification problems above lower bounds