Complexity of Edge Editing to a Connected Graph of Bounded Degrees
Øyvind Stette Haarberg · NORA - Norwegian Open Research Archives · 2019
In the EDGE EDITING TO A CONNECTED GRAPH OF BOUNDED DEGREES problem we are given a graph G, an integer k and a function f that assigns each vertex in G an integer bound on the degree.The task is to answer if there exists some connected graph H on the same set of vertices such that for every vertex in H the degree is within the function bound, and the size of the symmetric difference between the edge set of G and the edge set of H is at most k.In this thesis we have considered both an upper bound and a lower bound.For the upper bound we show that the problem is NP-complete, and give a polynomial kernel with O(k 3 ) vertices and O(k 4 ) edges.In addition we give a 2 O(k) • |V (G)| O(1) FPT algorithm based on random separation, which we show is asymptotically optimal assuming ETH.For the lower bound we give a polynomial algorithm using matching techniques.