Bellman-Ford algorithm can detect negative weight cycles.

An NP-hard problem does not have to be in NP

Approximation algorithms return solutions that are close to the optimal in some way. 

Every edge in the minimum cut must be fully saturated in the final flow

The Push-Relabel algorithm maintains a preflow and assigns heights to nodes, pushing excess flow from higher to lower nodes and relabeling nodes when necessary to find the maximum flow

What is the approximation ratio of the standard greedy algorithm for the Vertex Cover problem?

The capacity of a cut is the sum of the residual capacities of the edges crossing the cut.

List out all the false statements

By reducing 3SAT to Independent Set, we show that Independent Set is at least as hard as 3SAT, confirming its NP-completeness

Find the false statements if any