user1441057
  • Member for 5 years, 9 months
  • Last seen more than 4 years ago
Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2
1 votes

Figured out this is indeed NP-hard. This is equivalent to finding the maximum spanning star forest in a bipartite graph, which in turn is as hard as finding the minimum dominating set in a bipartite ...

View answer