CISPA
Browse

Incompressibility of H-free edge modification problems: Towards a dichotomy

Download (712.51 kB)
journal contribution
posted on 2023-11-29, 18:06 authored by Dániel MarxDániel Marx, R.B. Sandeep
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.

History

Preferred Citation

Dániel Marx and R.B. Sandeep. Incompressibility of H-free edge modification problems: Towards a dichotomy. In: Journal of Computer and System Sciences. 2022.

Primary Research Area

  • Trustworthy Information Processing

Legacy Posted Date

2022-04-29

Journal

Journal of Computer and System Sciences

Pages

25 - 58

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{cispa_all_3629, title = "Incompressibility of H-free edge modification problems: Towards a dichotomy", author = "Marx, Dániel and Sandeep, R.B.", journal="{Journal of Computer and System Sciences}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC