# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Incompressibility of H-free Edge Modification Problems: Towards a Dichotomy

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2004.11761.pdf

(Preprint), 660KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Marx, D., & Sandeep, R. B. (2020). Incompressibility of H-free Edge Modification Problems: Towards a Dichotomy. Retrieved from https://arxiv.org/abs/2004.11761.

Cite as: https://hdl.handle.net/21.11116/0000-0007-492A-9

##### Abstract

Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to

find whether there exists at most $k$ pairs of vertices in $G$ such that

changing the adjacency of the pairs in $G$ results in a graph without any

induced copy of $H$. The existence of polynomial kernels for $H$-free Edge

Editing received significant attention in the parameterized complexity

literature. Nontrivial polynomial kernels are known to exist for some graphs

$H$ with at most 4 vertices, but starting from 5 vertices, polynomial kernels

are known only if $H$ is either complete or empty. This suggests the conjecture

that there is no other $H$ with at least 5 vertices were $H$-free Edge Editing

admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of

nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge

Editing is incompressible and the complexity assumption $NP \not\subseteq

coNP/poly$ holds, then $H$-free Edge Editing is incompressible for every graph

$H$ with at least five vertices that is neither complete nor empty. That is,

proving incompressibility for these nine graphs would give a complete

classification of the kernelization complexity of $H$-free Edge Editing for

every $H$ with at least 5 vertices.

We obtain similar result also for $H$-free Edge Deletion. Here the picture is

more complicated due to the existence of another infinite family of graphs $H$

where the problem is trivial (graphs with exactly one edge). We obtain a larger

set $\mathcal{H}$ of nineteen graphs whose incompressibility would give a

complete classification of the kernelization complexity of $H$-free Edge

Deletion for every graph $H$ with at least 5 vertices. Analogous results follow

also for the $H$-free Edge Completion problem by simple complementation.

find whether there exists at most $k$ pairs of vertices in $G$ such that

changing the adjacency of the pairs in $G$ results in a graph without any

induced copy of $H$. The existence of polynomial kernels for $H$-free Edge

Editing received significant attention in the parameterized complexity

literature. Nontrivial polynomial kernels are known to exist for some graphs

$H$ with at most 4 vertices, but starting from 5 vertices, polynomial kernels

are known only if $H$ is either complete or empty. This suggests the conjecture

that there is no other $H$ with at least 5 vertices were $H$-free Edge Editing

admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of

nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge

Editing is incompressible and the complexity assumption $NP \not\subseteq

coNP/poly$ holds, then $H$-free Edge Editing is incompressible for every graph

$H$ with at least five vertices that is neither complete nor empty. That is,

proving incompressibility for these nine graphs would give a complete

classification of the kernelization complexity of $H$-free Edge Editing for

every $H$ with at least 5 vertices.

We obtain similar result also for $H$-free Edge Deletion. Here the picture is

more complicated due to the existence of another infinite family of graphs $H$

where the problem is trivial (graphs with exactly one edge). We obtain a larger

set $\mathcal{H}$ of nineteen graphs whose incompressibility would give a

complete classification of the kernelization complexity of $H$-free Edge

Deletion for every graph $H$ with at least 5 vertices. Analogous results follow

also for the $H$-free Edge Completion problem by simple complementation.