Задача редактирования графа до графа с заданными степенями

Пётр Головач
Thursday, September 18, 2014 - 18:00
ПОМИ РАН, Мраморный зал

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph $G$, non-negative integers $d,k$ and a function $\delta \colon V(G) \to \{1,...,d\}$, whether it is possible to obtain a connected graph $G’$ from $G$ such that the degree of $v$ is $\delta(v)$ for any vertex $v$ by at most $k$ edge editing operations. As the problem is NP-complete even if $\delta(v)=2$, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by $d+k$. For the special case $\delta(v)=d$, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. We also investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. In particular, we obtain polynomial-time algorithms for the Edge Editing to an Eulerian Graph problem and its directed variant.