(2020) Incompressibility of HFree Edge Modification Problems: Towards a Dichotomy.

Text
LIPIcsESA202072.pdf  Published Version Download (700kB)  Preview 
Abstract
Given a graph G and an integer k, the Hfree Edge Editing problem is to find whether there exist 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 Hfree Edge Editing (that is, whether it is possible to reduce the size of the instance to k^O(1) in polynomial time) received significant attention in the parameterized complexity literature. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices (e.g., path on 3 or 4 vertices, diamond, paw), 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 Hfree Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set ℋ of nine 5vertex graphs such that if for every H ∈ ℋ, Hfree Edge Editing is incompressible and the complexity assumption NP ⊈ coNP/poly holds, then Hfree 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 Hfree Edge Editing for every H with at least 5 vertices. We obtain similar result also for Hfree 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 ℋ of nineteen graphs whose incompressibility would give a complete classification of the kernelization complexity of Hfree Edge Deletion for every graph H with at least 5 vertices. Analogous results follow also for the Hfree Edge Completion problem by simple complementation.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Dániel Marx (DM) 
Conference:  ESA European Symposium on Algorithms 
Depositing User:  Dániel Marx 
Date Deposited:  03 Dec 2020 10:27 
Last Modified:  03 May 2021 12:15 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3304 
Actions
Actions (login required)
View Item 