English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

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

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0007-492A-9 Version Permalink: http://hdl.handle.net/21.11116/0000-0007-64EC-F
Genre: Paper

Files

show Files
hide Files
:
arXiv:2004.11761.pdf (Preprint), 660KB
Name:
arXiv:2004.11761.pdf
Description:
File downloaded from arXiv at 2020-10-26 09:40
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

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: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2004.11761
URI: https://arxiv.org/abs/2004.11761
BibTex Citekey: Marx_arXiv2004.11761
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show