Does the Minimum Spanning Tree (MST) problem become NP-hard when adding edge profits?
Posted by John, at cstheory.stackexchange.com,
Let G be an undirected graph such that each edge e in G has a weight w(e). In addition, e has a profit p(e) where p(e) is in…