Which statement about maximum bipartite matching is correct?
Construct a flow network with source-to-left, left-to-right, and right-to-sink unit-capacity edges.
Which statement about the decision version of the Hamiltonian Path problem is correct?
Hamiltonian Path is a classic NP-complete problem.
If A <=_p B and B is NP-complete, which statement is guaranteed?
A polynomial reduction to an NP-complete problem does not by itself make A NP-hard or NP-complete. Membership of A in NP must be established separately.
Which reduction direction is sufficient to prove that problem B is NP-hard, assuming A is already known to be NP-hard?
If every instance of A can be transformed to B in polynomial time and A is NP-hard, then B is at least as hard as A.
Which statements about BFS on an unweighted graph are CORRECT?
The first, second, and fourth statements are correct; the exact BFS tree can depend on adjacency ordering.