Maximal spanning acyclic subgraph

Question

Given a connected undirected graph (in particular as a directed one but with arcs in both ways), my problem is to find a subgraph such that:

1. is a directed acyclic graph
2. is possibly maximal in the number of arcs
3. has an arbitrarly selected root node with only outgoing arc
4. is connected and connects all nodes

Is there any algorithm to solve this? I've searched for the Minimum Spanning Tree but is not what I'm looking for since it doesn't necessarily have to be a tree neither to minimize path costs of a weighted graph

Answer 1

One way to make the graph acyclic is to first pick an arbitrary ordering of the vertices (imagine them being lined up left to right). For each pair of vertices $v,w$ that had an edge between them in the original graph, you're really thinking of that as a pair of directed edges: $v \to w$ and $w \to v$. Of these two edges, keep only the one that goes left to right.

This will be acyclic, because any directed path keeps going left, and therefore can't return to where you started. It's also the directed acyclic subgraph with the most arcs: you can't keep both arcs $v \to w$ and $w \to v$, because that would be a cycle of length $2$, so you can keep at most one of the arcs - and this algorithm keeps exactly one. Whichever node you put first will be the root.

Regarding connectivity, there are three options:

1. Assuming you could get from any node to any other in the original graph, you can still get from any node to any other if you ignore arrows in this graph.
2. You can't get from any node to any other while respecting the arrows, because you can't ever get from a node to another node earlier in the ordering. But this is an unavoidable problem if you have an acyclic graph: if you could get from node $v$ to node $w$, and also from node $w$ to node $v$, you'd have a cycle.
3. The most we could hope for is an ordering such that for any two nodes $v,w$ there is either a path from $v$ to $w$, or a path from $w$ to $v$. This is sometimes possible, but hard to find.

For option 3, note that if you have two nodes that are consecutive in the ordering, we can't hope for a path from the right node to the left node, and the only way we can hope for a left-to-right path is if there's an arc between the nodes. So we can only get an ordering of this type if the original undirected graph has a Hamiltonian path: a path that visits every vertex exactly once. (Then, we just take that path as our ordering.)

Unfortunately, finding a Hamiltonian path (or checking that there is one) is a well-known hard computational problem. But it's one you have to solve if you want the connectivity.

Answer 2

Minimum spanning tree (MST) algorithm works here, I think. Why?
Set the weight of each arc to be $-1$. Find the MST. This guarantees
your MST is maximal w.r.t. the number of arcs.

The most basic algorithms here are of Prim and Kruskal.

For this algorithm to work your initial graph has to be connected of course.

See also:

https://stackoverflow.com/questions/10414043/is-minimum-spanning-tree-afraid-of-negative-weights