Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:

enter image description here

1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in linear time ? Basically, we don't want any edges that shortcuts our visit as every vertices need to be visited.

Here is something: Such edge removal can be achieved in linear time by scanning trough all the vertices in graph in the topological order, and for every outgoing edge(a, c) of v checking if the b comes after the vertex。

How can I correctly describe that if an algorithm remove (0,1),(3,4),(1,2) edges in this graph?

  • 2
    $\begingroup$ You can describe it in any way you want as long as it is clear and understandable to your audience. Helping you figure out how to explain ideas clearly might be beyond the scope of this site. $\endgroup$ – D.W. Apr 7 '19 at 20:47
  • $\begingroup$ Yes, and agree, I can't even convince myself now. would like something better to describe it. $\endgroup$ – JohnMax Apr 7 '19 at 21:02
  • $\begingroup$ What you should do is to explain the meaning of "we don't want any edges that shortcuts our visit as every vertices need to be visited." What is the expected output? Is it a subset of all edges such that there is at most one path between any two vertices in the given directed graph once edges in that subset have been removed? If so, we can also remove $\{(0, 1),(3,4), (7,2) \}$. We can also remove $\{(0, 3),(3,4), (1,2) \}$. You should also specify what kind of graph is given. There are several incompatible specifications of the expected input and the expected output. $\endgroup$ – John L. Apr 8 '19 at 0:53
  • $\begingroup$ Hi @Apass.Jack, Let us say that we need to visit every vertices in a directed acyclic graph, but in this case, we don't want to traversal with the shortest paths. Instead, we would like to visit every vertices, which means we need to delete all the edges that creating shortcuts. $\endgroup$ – JohnMax Apr 8 '19 at 1:53
  • $\begingroup$ @JohnMax I know what you mean, probably more than you know what you mean, which is sort of confusing me. It might not occur to you, but there are several ambiguous places. "We would like to visit every vertex". Do you mean visiting them by following a directed path? (Note that we do not have to.) Can we visit a vertex twice? There might not be a path that goes through all vertices without repetitions. If that happens, what are we supposed to do? $\endgroup$ – John L. Apr 8 '19 at 2:09

Your operation replaces your graph with one of its directed spanning trees. See for example lectuire notes of Uri Zwick.

| cite | improve this answer | |

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.