English

Item

ITEM ACTIONSEXPORT

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

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

Item is

show hide
Genre: Paper

Files

show Files
hide Files
:
arXiv:2004.11761.pdf (Preprint), 660KB
Name:
arXiv:2004.11761.pdf
Description:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

Creators

show
hide
Creators:
Marx, Dániel1, Author
Sandeep, R. B.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
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.

Details

show
hide
Language(s): eng - English
Dates: 2020-04-242020
Publication Status: Published online
Pages: 35 p.
Publishing info: -
Rev. Type: -
Identifiers: arXiv: 2004.11761
URI: https://arxiv.org/abs/2004.11761
BibTex Citekey: Marx_arXiv2004.11761
Degree: -

show

show

show

show