Skip to main content
Share Your Experience: Take the 2024 Developer Survey
2 votes
Accepted

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

There is no poly-time approximation algorithm for this problem unless P=NP. For the metric case (when the graph is complete and the edge weights satisfy the triangle inequality), there is a poly-time ...
Neal Young's user avatar
  • 10.8k
1 vote

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

I think I can show that the problem is NP-hard, even in the case where the graph is unweighted. Specifically, given an undirected graph $G$, and values $p$ and $k$, I want to know if I can partition ...
a3nm's user avatar
  • 9,459

Only top scored, non community-wiki answers of a minimum length are eligible