0
$\begingroup$

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The algorithm needs to run in $O\left(V+E\right)$.

I've tried running a depth-first search on $G$ and trying to somehow partition the cross, back, and forward edges into cycleless sets, but this approach hasn't gotten me very far. I've tried looking at specific graph examples and finding specific solutions to the problem, but I haven't been able to generalize these solutions into an algorithm.

The homework tag seems to have been removed - this is a homework question so I'd appreciate hints rather than an outright solution.

EDIT: I think I may have solved it, but I'm having a difficult part formalizing a certain part of it.

Assume the graph is connected (otherwise just run the algorithm on each separate component). Take $v\in V$, and let $T=(V,E')$ be the tree computed by $DFS(v)$. Define $B$ to be the set of back edges, $F$ to be the set of forward eges, and $C$ to be the set of cross edges.

We define $E_1 = E'\cup F$, which clearly has no cycles.

$E_2$ will contain the back edges, and now we have to divide the cross edges in a manner such that they won't form a cycle. Intuitively I want the cross edges that "go left" to go into $E_1$ and the cross edges that "go right" to go into $E_2$ but I don't know how to formalize it, or if it's even correct.

$\endgroup$
0
$\begingroup$

It seems like things would be easier if you had no cross edges at all. Maybe you can modify your spanning-tree idea to make that happen.

$\endgroup$
  • $\begingroup$ Could you elaborate? I don't quite see how I can 'get rid' of my cross edges $\endgroup$ – Mark Nov 16 '14 at 17:32
  • $\begingroup$ What you're actually using from the DFS-tree is the tree-order, which lets you define "forward", "backward", and "cross" edges. How important is the tree itself in your idea? $\endgroup$ – Gregory J. Puleo Nov 16 '14 at 17:35
  • $\begingroup$ Pretty important, it gives me a set of edges that I know is cycleless. $\endgroup$ – Mark Nov 16 '14 at 17:38
  • $\begingroup$ If some of the edges in the "tree" were actually missing, would it hurt you? $\endgroup$ – Gregory J. Puleo Nov 16 '14 at 17:41
  • 1
    $\begingroup$ I'm not quite following your idea, and I think I've found a way of formalizing the last part of the proof I included in my question. During DFS I give each vertex a number - the root gets 1, his son gets 2, his son's son gets 3, and so forth - and I define "going left" to be going from a small number to a large, and "going right" to be the opposite. I think this completes the algorithm. $\endgroup$ – Mark Nov 16 '14 at 17:56
1
$\begingroup$

Lay the vertices out in a line $ 1, 2, 3, \ldots $. Put all the rightwards arcs in $E1$ and all the leftwards arcs in $E2$.

For $ V = \{ v_1, v_2, \ldots v_n \}$, for $ <v_i, v_j> \epsilon \ G $,

$$ <v_i, v_j> \epsilon \ E_1 \iff i < j \\ <v_i, v_j> \epsilon \ E_2 \iff i \ge j $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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