6
$\begingroup$

I am wondering whether there exists a fast algorithm for the following problem.

Given a digraph $G$ possibly with loops (that is edges that begin and end at the same vertex) and the choice of an edge $e \in G$, what is the largest (in terms of number of vertices) subgraph of $G$ that contains $e$ and admits a vertex disjoint cycle cover.

ps: sorry for the crosspost, but I originally posted at at stackoverflow and was directed here for a possibly more appropriate crowd...

Improve this question
$\endgroup$
4
  • $\begingroup$ ...where "disjoint" means "vertex-disjoint", i.e. no vertex appears more than once in the cycle? $\endgroup$
    – user13407
    Commented Jan 22, 2013 at 8:36
  • $\begingroup$ Yes, vertex disjoint cycle cover of $G' \subset G$ refers to a set of cycles such that each vertex of $G'$ appears in exactly one cycle. For example, if $G-G'$ contains a cycle, then $G'$ cannot be optimal (in the sense of the original question), since adding this cycle to $G'$ would yield a larger graph satisfying the conditions. $\endgroup$
    – Robert
    Commented Jan 22, 2013 at 18:03
  • $\begingroup$ Is there any restriction in the number of cycles in the cover? $\endgroup$
    – Marzio De Biasi
    Commented Jan 22, 2013 at 18:49
  • $\begingroup$ No, no restrictions on the number of cycles in the cover. $\endgroup$
    – Robert
    Commented Jan 22, 2013 at 19:56

2 Answers 2

Reset to default
6
$\begingroup$

Deterministically, you can do it as follows: Give your edge $e$ the weight $n+1$ and add a self-loop of weight zero to each node that does not have one so far. Existing edges get weight one. By removing the weight zero loops, a maximum weight cycle cover in the new graphs induces a partial cycle cover in the old graph that (1) contains your edge $e$ and (2) has a maximum number of edges. The vertices of the partial cycle cover induce the graph you are looking for. If the cycle cover in the new graph does not contain $e$ at all, then there is no such subgraph.

You can compute a maximum weight cycle cover by reducing it to maximum weight perfect matching.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. This seems correct to me at first reading; I did not think of playing with weights assigned to the edges to force the conditions. To clarify, $n$ above corresponds to the number of edges in the graph. $\endgroup$
    – Robert
    Commented Jan 23, 2013 at 17:12
  • $\begingroup$ No, $n$ is the number of vertices. By giving an edge $e$ weight $n+1$, it is ensured that this edge will be selected if possible. Every other cycle cover has weight at most $n$. (But choosing $n$ to be the number of edges will work, too.) $\endgroup$
    – Markus Bläser
    Commented Jan 23, 2013 at 21:42
5
$\begingroup$

There is at least a randomized $O(n^4)$ time algorithm. To make sure the specified arc $uv$ is part of the cycle cover, contract the arc into one vertex $w$ retaining $u$'s ingoing arcs and $v$'s outgoing arcs. Take the adjacency matrix $A$ of the resulting graph, replace each arc (i.e. $1$) with a random number, introduce an indeterminate $r$ and compute $p(r)=\operatorname{det}(J*r+A)$, where $J$ is the identity matrix except for the element corresponding to the vertex $w$, where it is zero. The smallest exponent $e$ such that the monomial $r^e$ has a non-zero coefficient in $p(r)$ is "proof" of the fact that there is an induced subgraph on $n-e$ vertices that has a cycle cover containing your arc. Conversely, if there are cycle covers on $n-e$ vertices, the coefficient of $r^e$ is most probably not zero.

Look at Edmonds matrix, and note that perfect matchings in balanced bipartite graphs is in one-to-one correspondence with cycle covers in digraphs. See also Schwartz-Zippel to see how to bound the probability of failures.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.