(2022) Incompressibility of Hfree edge modification problems: Towards a dichotomy.

Text
2004.11761.pdf Download (729kB)  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. 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 where Hfree Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set of nine 5vertex graphs such that if for every , Hfree Edge Editing is incompressible and the complexity assumption holds, then Hfree Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty. We obtain similar results also for Hfree Edge Deletion/Completion.
Item Type:  Article 

Divisions:  Dániel Marx (DM) 
Depositing User:  Dániel Marx 
Date Deposited:  29 Apr 2022 09:21 
Last Modified:  29 Apr 2022 09:21 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3629 
Actions
Actions (login required)
View Item 