Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ has an $f$-factor or not? That is a subgraph $H$ such that for all $i$, degree of $i$th vertex in $H$ is $f(i)$.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes; in fact, one can find in polynomial time a subgraph that is "as close as possible" to being an $f$-factor, if no $f$-factor exists. See, for example, Hell-Kirkpatrick: http://www.sciencedirect.com/science/article/pii/S0196677483710060
$\begingroup$
$\endgroup$
There is also this recent paper of Meijer, Núñez-Rodríguez and Rappaport which gives a polynomial-time algorithm in the case that $f$ is identically $k$ for some fixed $k$. Interestingly, Meijer, Núñez-Rodríguez and Rappaport do not seem to be aware of the earlier paper of Hell and Kirkpatrick. However, two nice properties of their paper are that it is not behind a paywall and that their algorithm is a simple reduction to maximum matching.
answered Nov 3, 2014 at 22:53