TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 09.01.2014


Page Content

to Navigation

Kernelization for Degree Sequence Completion Problems Using f-Factors

Vincent Froese (TU Berlin)

We answer an open question by Mathieson and Szeider [JCSS 2012] concerning the existence of polynomial-size kernels for the Degree Constraint Editing Problem. Given a graph G together with a list of admissible degrees for each vertex, the task is to modify G by applying at most k editing operations such that, for each vertex in the resulting graph, its degree is an element of its list. We give an O(kr^2)-vertex kernel for the case of edge additions where r is the maximum admissable degree over all vertices. We further transfer this kernel into an O(r^5)-vertex kernel using a strategy based on previous work by Liu and Terzi [SIGMOD 2008] and Hartung et al. [ICALP 2013]. The method relies on transforming the graph completion problem into an efficiently solvable number problem. A solution for the number problem is then translated back into the graph setting using f-factor computations.
As an additional contribution, we generalize our methods to obtain a framework that is applicable to a wider range of degree sequence completion problems.

09.01.2014 16:15
Vincent Froese
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe