title: Two-directional spanning tree in a directed graph in subquadratic time
body: <p>Here's the problem I'm trying to solve. Given a directed graph G, does it contain a connected subgraph that:</p>
  
  <ul>
  <li>Contains every node from G</li>
  <li>Is acyclic</li>
  <li>Can be disconnected by removing any one edge</li>
  <li>Has a path between every source node and every sink node</li>
  </ul>
  
  <p>Intuitively, the subgraph I'm looking for consists of a downward pointing and an upward pointing tree that share the same root and together span G. I'm calling it the two-directional spanning tree problem, but it may have another name.</p>
  
  <p>The dumb algorithm I've thought of is to cycle through each node in the graph, do a backwards and a forwards DFS starting at that node and then concatenate the search trees. If a two-directional spanning tree exists, I'm pretty sure this will find one on some iteration. However, it runs in O(V(V + E)) time. My intuition is that there should be a faster algorithm. Am I correct?</p>