7
$\begingroup$

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.

This is similar to the rooted MST digraph problem, which the chu-liu algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.

Has anybody been working on this? Can you point me towards some papers that I should read?

Thanks.

$\endgroup$
  • $\begingroup$ MST means minimal spanning tree, right? What does it mean to have a non-rooted tree? $\endgroup$ – Dave Clarke Oct 12 '10 at 13:25
  • $\begingroup$ I guess "Minimal Spanning Tree" isn't the best term for what I'm looking for - "Minimal Spanning Subgraph", perhaps. Basically, a subset of the edges such that from any node you can get to any other node. Which is the same thing as an MST in an undirected graph, but not in a digraph. $\endgroup$ – Nate Oct 12 '10 at 13:28
  • $\begingroup$ Minimal spanning subgraph would do the trick. Except that I can remove some edges from it to get an MST, which would be 'more' minimal. $\endgroup$ – Dave Clarke Oct 12 '10 at 13:32
  • 2
    $\begingroup$ I would call it the “minimum strongly connected spanning subgraph,” and finding it is NP-complete as Warren Schudy explained in his answer. $\endgroup$ – Tsuyoshi Ito Oct 12 '10 at 14:58
  • 2
    $\begingroup$ Do a google search of the phrase "minimum strongly connected spanning subgraph" that Tsuyoshi suggested and read the literature you find. There seems to be a fair amount of prior work on this problem. $\endgroup$ – Warren Schudy Oct 12 '10 at 18:20
15
$\begingroup$

If I understand your question correctly you aren't looking for a tree, or an arborescence, but rather a minimum weight set of arcs that suffice to keep the graph strongly connected.

Your problem is NP-complete by reduction from Hamiltonian cycle problem. Given an input undirected graph that you wish to find the Hamiltonian cycle of create a directed graph by replacing each edge with a pair of oppositely directed arcs. Give all arcs weight 1. This directed graph has a set of arcs that leave the graph strongly connected with weight at most the number of vertices if and only if it has a Hamiltonian cycle.

You can get a two-approximation by picking an arbitrary root, finding the minimum weight spanning tree with arcs pointing towards the root, finding the minimum weight spanning tree with arcs pointing away from the root, and then unioning the two sets of arcs.

I don't recognize this problem off the top of my head but have you tried looking in the various NP-complete problem directories for it?

$\endgroup$
  • 1
    $\begingroup$ In this problem, you're allowed to visit a vertex as many times as you want. Correct me if I'm wrong, but the Hamiltonian cycle requires you visit each vertex only once. Remove that stipulation, and it's no longer NP-complete, correct? $\endgroup$ – Nate Oct 12 '10 at 13:41
  • 2
    $\begingroup$ Hamiltonian cycle does require you to visit each vertex exactly once. An equivalent formulation of Hamiltonian cycle is a cycle which visits each of the $n$ vertices at least once and uses at most $n$ edges. This equivalent formulation is helpful for understanding my reduction. $\endgroup$ – Warren Schudy Oct 12 '10 at 14:46
  • 3
    $\begingroup$ Nate: I think you're missing the point. Warren's using Ham cycle for the reduction TO your problem to show NP-hardness. He's not trying to give you an algorithm. $\endgroup$ – Suresh Venkat Oct 12 '10 at 15:30
  • 2
    $\begingroup$ As you say a spanning subgraph may or may not be a Hamiltonian cycle. However a spanning subgraph of length $n$ must necessarily be a Hamiltonian cycle. Therefore there is a spanning subgraph of length $n$ if and only if there is a Hamiltonian cycle. If this still doesn't make sense I'm not sure what else to say other than suggesting that you look in some textbook for example NP-hardness proofs, try to write a similar proof for this problem, and if that fails discuss this problem with a theory-minded person face to face. $\endgroup$ – Warren Schudy Oct 12 '10 at 18:07
  • 2
    $\begingroup$ Perhaps it would help if you read the literature on the minimum strongly connected spanning subgraph problem (start with a Google search). A quick glance at that literature suggests that that problem is NP-complete and that it is the same as your problem. Please either tell us how your problem differs from the minimum strongly connected spanning subgraph problem, or else locate an NP-completeness proof in the literature, point us to it, and let us know which specific step of the proof you don't understand. $\endgroup$ – Warren Schudy Oct 12 '10 at 22:55
4
$\begingroup$

As has been explained repeatedly above, finding the minimum-weight strongly-connected spanning subgraph ("SCSS") of a given weighted digraph is NP-complete, even in the special case when all weights are one and even when you only want to distinguish the case that there is a subgraph of weight n from the case that the optimal weight is larger than n.

However, to follow up on a comment of Warren Schudy: there is a simple polynomial-time approximation algorithm that gets an approximation ratio of 2: choose an arbitrary vertex s, find the minimum-weight arborescence out of s (subgraph that includes a path from s to all other vertices), find the minimum-weight arborescence into s, and take the union of the two arborescences. I believe this idea is due to Frederickson and JáJá, "Approximation algorithms for several graph augmentation problems", SIAM J. Comput. 1981.

Better approximations are known for the unweighted problem e.g. 1.64 by Khuller, Raghavachari, and Young, SIAM J. Comput. 1995. I don't know of improvements for the weighted version but that may merely indicate that I didn't search hard enough.

$\endgroup$
0
$\begingroup$

@warren sorry mate I couldn't understand your reduction either, it seems to be saying that finding ham cycle in a directed graph is NPC as finding ham cycle in an undirected graph is NPC, which i feel is a bit off the topic. It would be better if you could rephrase your reduction more clearly.

also this problem is not NP complete as it's a puzzle from facebook, of course I am guilty of assuming that they have a polynomial time solution for it. has anyone solved it yet?

$\endgroup$
  • $\begingroup$ Read the comments under Warren's answer. $\endgroup$ – Kaveh Dec 28 '10 at 5:26
  • $\begingroup$ oh I got it now, it's NPC, $\endgroup$ – jackace Dec 28 '10 at 6:13

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.