(2022) Incompressibility of H-free edge modification problems: Towards a dichotomy.
|
Text
2004.11761.pdf Download (729kB) | Preview |
Abstract
Given a graph G and an integer k, the H-free 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 H-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set of nine 5-vertex graphs such that if for every , H-free Edge Editing is incompressible and the complexity assumption holds, then H-free 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 H-free 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 |