# Finding largest subgraph that contains a given edge and admits a cycle cover

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...

• ...where "disjoint" means "vertex-disjoint", i.e. no vertex appears more than once in the cycle? – user13407 Jan 22 '13 at 8:36
• 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. – Robert Jan 22 '13 at 18:03
• Is there any restriction in the number of cycles in the cover? – Marzio De Biasi Jan 22 '13 at 18:49
• No, no restrictions on the number of cycles in the cover. – Robert Jan 22 '13 at 19:56

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.
• 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. – Robert Jan 23 '13 at 17:12
• 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.) – Markus Bläser Jan 23 '13 at 21:42
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.