I stumbled upon the following problem during my research.
I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting graph is 2.
Is this problem NP-hard? I was trying to come up with a polynomial time algorithm (and failed) and also tried to prove its NP-hardness, but also having a hard time.