CISPA
Browse
cispa_all_3304.pdf (684.17 kB)

Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy

Download (684.17 kB)
conference contribution
posted on 2023-11-29, 18:14 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. The existence of polynomial kernels for H-free 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 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 ∈ ℋ, H-free Edge Editing is incompressible and the complexity assumption NP ⊈ 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 ℋ 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.

History

Preferred Citation

Dániel Marx and R. Sandeep. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. In: European Symposium on Algorithms (ESA). 2020.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

European Symposium on Algorithms (ESA)

Legacy Posted Date

2020-12-03

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3304, title = "Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy", author = "Marx, Dániel and Sandeep, R. B.", booktitle="{European Symposium on Algorithms (ESA)}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC