# Give an algorithm to solve the connector problem where negative costs are allowed

A connector problem is defined as: given a graph G and a positive cost c_e for each e in E, find a minimum-cost spanning connected subgraph of G.

When the edge costs are all positive, this problem-type can be solved using Minimum Spanning Tree (MST) algorithms. I'm not really sure what would change if the edge costs weren't strictly positive. My understanding of the two MST algorithms I know (Prim's and Kruskal's) is that both of these algorithms are greedy, in that they choose the most optimal (cheapest) edge connecting any two nodes to eventually span the graph. If the costs are negative, I assumed that the greediness of these algorithms would always favor the least costly (or most negative) edge cost if there existed an edge that was negative. Could someone explain to me why negative edge costs would inhibit these algorithms from solving the connector problem as an MST problem?

## 1 Answer

I think the main distinction is that your connector problem asks for a minimum-cost spanning connected subgraph of G, not specifically a tree. If the edge weights are all positive then a minimum cost spanning connected subgraph of $G$ will necessarily be a tree. However, if the edge weights are allowed to be negative then edges with negative weights will always be included in a minimum cost spanning connected subgraph and thus the answer will, in general, not be a tree.

So, to recap, if all edge weights are positive, then the both problems are equivalent.

• That makes a lot more sense now - if there are negative edge weights, they will always be chosen in a connector problem's subgraph because cycles/circuits are allowed and negative edge weights are always favorable whereas in a MST, we can't have cycles. Thanks so much for clearing that up for me. – too spicy Sep 20 '16 at 21:44
• @toospicy, no problem - I'm glad I could help! – Chris Harshaw Sep 21 '16 at 5:01