Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2
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 graph, which is NP-hard.