Which of the following problems is NP-HARD but NOT in NP?
The Halting Problem is undecidable (not in NP, because solutions cannot even be verified in finite time), but it is NP-Hard because any NP problem can be reduced to it.
In Edmonds-Karp, what is the maximum number of augmentations in the worst case?
Edmonds-Karp performs at most O(VE) augmentations, and each BFS takes O(E), giving O(VE^2) total time.
What is the time complexity of finding Articulation Points in an undirected graph $G = (V$, E) using DFS?
Using DFS discovery times disc[] and lowest reachable discovery times low[], articulation points can be identified in a single DFS pass in O(V + E) time.
For a strongly connected directed graph G with V >= 2 vertices, what is the MINIMUM number of edges G must have?
A strongly connected graph requires at least a simple directed cycle containing all V vertices, which uses exactly V edges.
Which graph problem can be modeled as a Longest Path problem in a Directed Acyclic Graph (DAG)?
The Critical Path Method finds the longest path in a DAG (representing task dependencies) in linear time O(V + E) using Topological Sort and DP.