Efficient Generation of One-Factorizations through Hill Climbing

arXiv1707.00477MaRDI QIDQ6288575FDOQ6288575

Authors: Maya Dotan, Nathan Linial 

Publication date: 3 July 2017

Abstract: It is well known that for every even integer $n$, the complete graph $K_n$ has a one-factorization, namely a proper edge coloring with $n-1$ colors. Unfortunately, not much is known about the possible structure of large one-factorizations. Also, at present we have only woefully few explicit constructions of one-factorizations. Specifically, we know essentially nothing about the {em typical} properties of one-factorizations for large $n$. Suppose that $cal{C}_{mn}$ is a graph whose vertex set includes the set of all order-$n$ one-factorizations and that $Psi:V(cal{C}_{mn})omathbbR$ takes its minimum precisely at the one-factorizations. Given $cal{C}_{mn}$ and $Psi$, we can generate one-factorizations via hill climbing. Namely, by taking a walk on $cal{C}_{mn}$ that tends to go from a vertex to a neighbor of smaller $Psi$. For over 30 years, hill-climbing has been essentially the only method for generating many large one-factorizations. However, the validity of such methods was supported so far only by numerical evidence. Here, we present for the first time hill-climbing algorithms that provably generate an order-$n$ one-factorization in $extpolynomial(n)$ steps regardless of the starting state, while all vertex degrees in the underlying graph are appropriately bounded. We also raise many questions and conjectures regarding hill-climbing methods and concerning the possible and typical structure of one-factorizations.

This page was built for publication: Efficient Generation of One-Factorizations through Hill Climbing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288575)