0
$\begingroup$

Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed cycle cover?

There are degree-constraints for the existence of Hamilton cycles in digraphs and I would like to know what the "maximal possible relaxation" of those constraints is if a whole crew of salespersons were available for visiting the cities.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The existence of such cover is equivalent to the existence of a bijection $f$ from $V$ to $V$ such that $(x, f(x)) \in E$ for all $x\in V$. The criterion is given by Hall lemma, and the sufficient conditions in terms of degrees are provided by double counting of edges. $\endgroup$
    – Fedor Petrov
    Commented May 31, 2021 at 7:14
  • 1
    $\begingroup$ In Section 3.1 of the linked paper, an example is given which has no Hamiltonian cycle, but also cannot be covered with vertex-disjoint cycles. So the semi-degree threshold for the existence of a Hamiltonian cycle in an oriented graph is the same as the existence of a vertex-disjoint directed cycle cover. In the language of Fedor's comment above, note that the out-neighborhood of $A\cup D$ is $A\cup B$ and $|A\cup D|>|A\cup B|$. $\endgroup$
    – Louis D
    Commented May 31, 2021 at 15:26
  • $\begingroup$ Perhaps something interesting would happen if you drop the requirement that the cycles be vertex-disjoint? $\endgroup$
    – Louis D
    Commented May 31, 2021 at 15:29
  • $\begingroup$ @LouisD If the requirement of vertex-disjointness is dropped, the problem can be solved by bipartite matching by an almost trivial transformation that allows one to impose lower bounds on the indegree and outdegree of a vertex; requiring that they both should at least be 1 suffices. The transformation I refer to also rules out pairs of antiparallel arcs. So having tight degree constraints would yield alternative heuristics for the NP hard directed 3-Cycle cover. $\endgroup$
    – Manfred Weis
    Commented May 31, 2021 at 15:39

0

Reset to default

You must log in to answer this question.