### 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.

As an additional contribution, we generalize our methods to obtain a framework that is applicable to a wider range of degree sequence completion problems.

Date | Speaker | Location | Language |
---|---|---|---|

09.01.2014 16:15 | Vincent Froese | TEL 512 | english |