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

<p>Look at <a href="http://en.wikipedia.org/wiki/Edmonds_matrix">Edmonds matrix</a>, and note that perfect matchings in balanced bipartite graphs is in one-to-one correspondence with cycle covers in digraphs. See also <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma">Schwartz-Zippel</a> to see how to bound the probability of failures.</p>

CC BY-SA 3.0
2013-01-23T07:53:39.547Z
2013-01-23T07:53:39.547Z
Andreas Björklund
<p>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.</p>

<p>You can compute a maximum weight cycle cover by reducing it to maximum weight perfect matching.</p>

CC BY-SA 3.0
2013-01-23T17:12:39.530Z
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
CC BY-SA 3.0
2013-01-23T21:42:18.020Z
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
CC BY-SA 3.0
2013-01-23T08:59:07.770Z
2013-01-23T08:59:07.770Z
Markus Bläser
<p>I am wondering whether there exists a fast algorithm for the following problem.</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2013-01-22T08:36:16.743Z
...where "disjoint" means "vertex-disjoint", i.e. no vertex appears more than once in the cycle?
user13407
CC BY-SA 3.0
2013-01-22T18:03:21.053Z
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
CC BY-SA 3.0
2013-01-22T18:49:01.523Z
Is there any restriction in the number of cycles in the cover?
Marzio De Biasi
CC BY-SA 3.0
2013-01-22T19:56:34.290Z
No, no restrictions on the number of cycles in the cover.
Robert
<graph-algorithms>
Finding largest subgraph that contains a given edge and admits a cycle cover
Robert
# Finding largest subgraph that contains a given edge and admits a cycle cover

(Asked by: username_0 on 2013-01-21)

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

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: ...where "disjoint" means "vertex-disjoint", i.e. no vertex appears more than once in the cycle?  
> **username_0**: 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.  
> **username_2**: Is there any restriction in the number of cycles in the cover?  
> **username_0**: No, no restrictions on the number of cycles in the cover.  

---

## 2 answers

### Answer by username_4 on 2013-01-23. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.)  

---

### Answer by username_3 on 2013-01-23. Score: 5

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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) to see how to bound the probability of failures.


---

