0
$\begingroup$

I'm given a black box that on graph $G = (V,E)$ and integer $0< K<|V|$ outputs $1$ iff there is a simple path of length greater than $K$ in $G$. I want to find the actual edges of the longest path in $G$ using as few calls to my black box as possible.

What I've come up with thus far is using the same method as when binary searching, i.e. first calling my black box with $K = |V|/2$ and so forth, but I'm not really sure what to do once I've found the $K_{max}$.. I'd really want to go in and change the black box to output the actual edges but that's impossible.

Edit: So I can delete any edge $e_i$ from $G$ and see if my black box still returns 1 (once I've found the maximal length path) - if it still returns 1 i know $e_i$ isn't part of the longest path, and if it returns 0 I know $e_i$ is part of the longest path(s) and I append it to my data structure holding the longest path. But what should I do if there are several paths of the maximum length? It feels as if I will return all the edges of all the longest paths and not just one specific.

$\endgroup$
  • 2
    $\begingroup$ What does the oracle answer? And what, exactly, is your question? (are you looking for any old good algorithm, or do you want a proven lower bound on the number of necessary calls? The latter is unlikely; iff P=NP, then this problem can be solved in polynomial time with no oracle queries at all.) $\endgroup$ – Lieuwe Vinkhuijzen Apr 14 '17 at 15:49
  • 3
    $\begingroup$ Hint : Delete an edge and run the oracle on modified graph, if answer is true then deleted edge does not belong to longest path else it belongs to longest path ( I am assuming you know the length of longest path ) $\endgroup$ – aaag Apr 17 '17 at 9:20
  • $\begingroup$ That's an excellent hint, thanks alot Shiv! $\endgroup$ – Nyfiken Gul Apr 17 '17 at 21:04
1
$\begingroup$

Since you can find the actual length of the longest path using binary search, in $\log |V|$ steps, I'll assume you have access to an oracle which tells you the length of the longest path. Given a graph $G$ lets denote the length of the longest path in $G$ by $L(G)$.

If you remove an edge after finding out that it does not affect the length of the longest path in $G$, then you avoid the issue of having to commit to some specific longest path. Suppose you keep iterating over the remaining edges, and for each remainning edge $(u,v)$ you check if $L(G)=L\left(G\setminus\left\{(u,v)\right\}\right)$. If they are equal, remove $(u,v)$ from $E$ and return to the main loop. When there are no more edges to delete, $E$ consists of a longest path in $G$.

To prove this, let $\mathcal{P}$ be the set of longest paths in $G$. Note that in any iteration $i$ (each iteration consists of removing an edge which does not affect the longest path length), there exists some $P\in\mathcal{P}$ such that $P$ is a path in $G_i$. Using this observation, you can show that when there are no more edges to delete, your graph is a longest path.

$\endgroup$
  • $\begingroup$ Great explanation, thank you. So in the worst case, I have to make log|V| + |E| calls to my oracle? log|V| for finding the actual L(G) and then one call for every edge deleted (in the worst case)? $\endgroup$ – Nyfiken Gul Apr 18 '17 at 15:46
  • 1
    $\begingroup$ Yes. This is because you don't have to examine any edge twice (if you decided that you're not going to delete $(u,v)$ at some iteration $i$, then you won't want to delete it in any later iteration). $\endgroup$ – Ariel Apr 18 '17 at 18:18
  • $\begingroup$ As I thought then, thanks for clearing that out Ariel! $\endgroup$ – Nyfiken Gul Apr 19 '17 at 12:24

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.