The following undirected version of Bounded Diameter Spanning Tree problem is solvable in Polynomial Time.

Undirected Version: Given an undirected Graph $G = (V, E)$ with each edge weight either 1 or 2; 2 positive integers $B$, and $D<=3$.

Problem Statement: Is there a spanning tree $T$ of $G$ such that the sum of weights of the edges in T does not exceed $B$ and such that $T$ contains no simple path with more than $D$ edges?

Directed Version: Now lets consider a same problem for a Directed Graph. With much more simpler constraints: Let each edge have the same weight 1, let $B=\infty$ (thus irrelevant), and let $D<2$.

Problem Statement: Is there a "spanning forest" $T$ of $G$ such that the sum of weights of the edges in T does not exceed $B$ and such that $T$ contains no simple path with more than $D$ edges?

I am struggling with how to approach the problem for the Directed version (though it has much less constraints than the undirected version). Can anyone please provide some inputs on the approach?

  • 1
    $\begingroup$ How do you solve the undirected version? Does the algorithm carry over? If not, why not? $\endgroup$ – Raphael Apr 15 '17 at 8:27
  • $\begingroup$ Much Thanks. To be honest, the information I have is that from Garey and Jhonson [ND4] where they mentioned the following "Can be easily solved in Polynomial Time if D<=3 or if all edges are weighted equal". But, I believe (without much direction to go about it), that the simpler version with less constraints would follow from it. The reduction is using Exact cover by 2-sets. But, frankly I haven't been able to come up with a similar correspondence or an idea for directed version . $\endgroup$ – TheoryQuest1 Apr 15 '17 at 8:46
  • $\begingroup$ 1. Do I understand that Garey & Johnson gave you a citation (namely, [ND4]) for where you can read more? If so, have you read the paper they cited? If not, a good next step would be to read that paper, understand their polynomial-time algorithm, then update the question with a summary of that information. 2. What have you tried? Have you tried to find an algorithm for the undirected version for $D=2$? Have you tried thinking about an algorithm for the directed version for $D=2$? What ideas have you considered so far? What's your definition of "spanning tree" for the latter? $\endgroup$ – D.W. Apr 15 '17 at 10:00
  • $\begingroup$ Thanks. 1.) I don't have the access to the paper and I am trying to get it. 2.) The definition of a Directed Spanning Tree is as follows: Assuming we ignore the direction of the edges the resultant sub-Graph is a spanning tree for the undirected graph. 3.) Regarding D<=2. It implies that there are no 2 pair of Nodes (a, b) in the directed version of Spanning tree such that there exists a path [a-> x -> y -> b] as if this were the case it violates D <=2 as here D=3. $\endgroup$ – TheoryQuest1 Apr 15 '17 at 10:54
  • $\begingroup$ 4.) Moreover on second thought even if the constraint was: (a) D<2 (b) the Spanning Tree was relaxed to Spanning Forest. Even then the Problem for the directed Graph under new constraints I am struggling with. Thus, I am updating the Question. [P.S. For the undirected one, I assume we can simply do a BFS Tree or something similar]. $\endgroup$ – TheoryQuest1 Apr 15 '17 at 11:07

Your Answer

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

Browse other questions tagged or ask your own question.