Event Entry
What and Who
Incompressibility of H-free edge modification problems: Towards a dichotomy
Dr. Sandeep R. B. is an Assistant Professor in the department of Computer Science and Engineering at Indian Institute of Technology (IIT) Dharwad, India. Before joining IIT Dharwad, he was a postdoc with Dr. Dániel Marx at Hungarian Academy of Sciences. He completed PhD from IIT Hyderabad in 2016 under the guidance of Dr. N. R. Aravind and Dr. Naveen Sivadasan. His research interests are in Algorithms and Graph Theory.
Date, Time and Location
Abstract
H-free Edge Completion are defined similarly, where only deletion of edges are allowed in the former and only completion of edges are allowed in the latter. Building upon the dichotomy results characterizing the polynomial-time solvable and NP-hard cases of these problems (Aravind et al., SIAM J. Discrete Math., 2017), we obtain dichotomy results on the incompressibility of these problems for regular graphs H. We prove that for regular graphs H, these problems
are incompressible if and only if H is neither complete nor empty, where the incompressibility assumes NP is not a subset of coNP/poly. Further, for H-free Edge Editing we obtain a set S of fourteen
small graphs such that, if for every H in S, H-free Edge Editing is incompressible, then H-free Edge Editing is incompressible for every graph H with at least five vertices but is neither complete nor empty.
Contact