For any edge e that is part of a minimum cut in a flow network G, if we increase the capacity of that edge by any integer k>1, then that edge will no longer be part of a
minimum cut.
FALSE
The scaled version of the Ford-Fulkerson algorithm can compute the maximum flow
in a flow network in polynomial time.
TRUE
Given a set of demands D = {dv} on a circulation network G(V,E), if the total demand over V is zero, then G has a feasible circulation with respect to D.
In a flow network, the maximum value of an flow could be less than the capacity of a given cut in that network.
If f is a max s-t flow of a flow network with source s and sink t, then the capacity of the min s-t cut in the residual graph Gf is 0.
In a graph with negative weight cycles, one such cycle can be found in O(nm) time
where n is the number of vertices and m is the number of edges in the graph.
An algorithm runs in weakly polynomial time if the number of operations is bounded by a polynomial in the number of bits in the input, but not in the number of integers in the input.
Let G(V,E) be an arbitrary flow network, with a source s, a sink t. Given a flow f of
maximum value in G, we can compute an s-t cut of minimum capacity in O(|E|) time.
The basic Ford-Fulkerson algorithm can be used to compute a maximum matching in
a given bipartite graph in strongly polynomial time.
The residual graph of a maximum flow f can be strongly connected.
Note: A directed graph is strongly connected if there is a path from every node to every other node in the graph.
The Ford-Fulkerson algorithm can be used to efficiently compute a maximum matching of a given bipartite graph.
In successive iterations of the Ford-Fulkerson algorithm, the total flow passing
through a vertex in the graph never decreases.
In a dynamic programming solution, the space requirement is always at least as big as
the number of unique sub problems.
Any problem that can be solved with a greedy algorithm can also be solved with dynamic programming.
The sequence alignment algorithm described in class can be used to find the longest
common subsequence between two given sequences.
In a flow network G, if we increase the capacity of one edge by a positive amount x
and we observe that the value of max flow also increases by x, then that edge must
belong to every min-cut in G.
If we have a dynamic programming algorithm with n^2
subproblems, it is possible that
the running time could be asymptotically strictly greater than Θ(n^2)
If we modify the Ford-Fulkerson algorithm by the following heuristic, then the time
complexity of the resulting algorithm will be strongly polynomial:
At each step, choose the augmenting path with fewest edges.
The dynamic programming solution (presented in class) to the 0/1 knapsack problem has a polynomial run time.
Bellman-Ford algorithm runs in strongly polynomial time.
It is possible for a dynamic programming algorithm to have an exponential running
time.
In a connected, directed graph with positive edge weights, the Bellman-Ford algorithm runs asymptotically faster than the Dijkstra algorithm.
There exist some problems that can be solved by dynamic programming, but cannot
be solved by greedy algorithm.
The Floyd-Warshall algorithm is asymptotically faster than running the Bellman-Ford
algorithm from each vertex.
If we have a dynamic programming algorithm with n^2 subproblems, it is possible that
the space usage could be O(n).
The Ford-Fulkerson algorithm solves the maximum bipartite matching problem in
polynomial time.
Given a solution to a max-flow problem, that includes the final residual graph Gf. We
can verify in a linear time that the solution does indeed give a maximum flow.
In a flow network, a flow value is upper-bounded by a cut capacity.
In a flow network, a min-cut is always unique.
A maximum flow in an integer capacity graph must have an integer flow on each edge.
For every node in a network, the total flow into a node equals the total flow out of a node.
Ford Fulkerson works on both directed and undirected graphs.
Suppose you have designed an algorithm which solves a problem of size n by
reducing it to a max flow problem that will be solved with Ford Fulkerson, however
the edges can have capacities which are O(2^n). Is this algorithm efficient?
NO
Is it possible for a valid flow to have a flow cycle (that is, a directed cycle in the graph, such that every edge has positive flow)?
Yes
Dynamic programming and divide and conquer are similar in that in each approach
the sub-problems at each step are completely independent of one another.
Ford Fulkerson has pseudo-polynomial complexity, so any problem that can be
reduced to Max Flow and solved using Ford Fulkerson will have pseudo-polynomial
complexity.
In a flow network, the value of flow from S to T can be higher than the number of edge disjoint paths from S to T.
Complexity of a dynamic programming algorithm is equal to the number of unique
sub-problems in the solution space.
In Ford-Fulkerson’s algorithm, when finding an augmentation path one can use either
BFS or DFS.
When finding the value of the optimal solution in a dynamic programming algorithm
one must find values of optimal solutions for all of its sub-problems.
If you have non integer edge capacities, then you cannot have an integer max flow.
The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in
the network.
For any graph there always exists an edge such that increasing the capacity on that
edge will increase the maximum flow from source s to sink t. (Assume that there is at
least one path in the graph from source s to sink t.)
If a problem can be solved using both the greedy method and dynamic programming,
greedy will always give you a lower time complexity.
The best time complexity to solve the max flow problem is O(Cm) where C is the total capacity of the edges leaving the source and m is the number of edges in the network.
In the Ford–Fulkerson algorithm, choice of augmenting paths can affect the number
of iterations.
0-1 knapsack problem can be solved using dynamic programming in polynomial time.
Bellman-Ford algorithm solves the shortest path problem in graphs with negative cost edges in polynomial time.
If a dynamic programming solution is set up correctly, i.e. the recurrence equation is
correct and the subproblems are always smaller than the original problem, then the
resulting algorithm will always find the optimal solution in polynomial time.
In the sequence alignment problem, the optimal solution can be found in linear time and space by incorporating the divide-and-conquer technique with dynamic programming.
Maximum value of an s-t flow could be less than the capacity of a given s-t cut in a
flow network.
One can efficiently find the maximum number of edge disjoint paths from s to t in a directed graph by reducing the problem to max flow and solving it using the Ford-Fulkerson algorithm.
In a network-flow graph, if the capacity associated with every edge is halved, then the
max-flow from the source to sink also reduces by half
The time complexity to solve the max flow problem can be better than O(Cm) where C is the total capacity of the edges leaving the source and m is the number of edges in the network.
Bellman-Ford algorithm can handle negative cost edges even if it runs in a distributed
environment using message passing.
If all edges in a graph have capacity 1, then Ford-Fulkerson runs in linear time.
If an iteration of the Ford-Fulkerson algorithm on a network places flow 1 through an
edge (u, v), then in every later iteration, the flow through (u, v) is at least 1.
For any flow network G and any maximum flow on G, there is always an edge e such
that increasing the capacity of e increases the maximum flow of the network.
Any Dynamic Programming algorithm with n subproblems will run in O(n) time.
A pseudo-polynomial time algorithm is always slower than a polynomial time
algorithm.
correct and each unique sub-problem is solved only once (memoization), then the
Maximum value of an s − t flow could be less than the capacity of a given s − t cut
in a flow network.
If all capacities in a network flow are rational numbers, then the maximum flow will
be a rational number, if exist.
The Ford-Fulkerson algorithm is based on the greedy approach.
The main difference between divide and conquer and dynamic programming is that
divide and conquer solves problems in a top-down manner whereas dynamic-
programming does this bottom-up.
The Ford-Fulkerson algorithm has a polynomial time complexity with respect to the
input size.
Given the Recurrence, T(n) = T(n/2 ) + θ(1), the running time would be O(log(n))
If all edge capacities of a flow network are increased by k, then the maximum flow will be increased by at least k.
In the Ford Fulkerson algorithm, choice of augmenting paths can affect the number of
iterations.
In the Ford Fulkerson algorithm, choice of augmenting paths can affect the min cut.
The problem of deciding whether a given flow f of a given flow network G is
maximum flow can be solved in linear time.
An edge that goes straight from s to t is always saturated when maximum s - t flow is
reached.
There always exists a maximum flow without cycles carrying positive flow.
In a directed graph with at most one edge between each pair of vertices, if we replace
each directed edge by an undirected edge, the maximum flow value remains
unchanged.
The Ford-Fulkerson algorithm finds a maximum flow of a unit-capacity flow network (all edges have unit capacity) with n vertices and m edges in O(mn) time.
Any Dynamic Programming algorithm with n unique subproblems will run in O(n)
The running time of a pseudo polynomial time algorithm depends polynomially on
the size of of the input
In dynamic programming you must calculate the optimal value of a subproblem twice,
once during the bottom up pass and once during the top down pass.
In the final residual graph constructed during the execution of the Ford–Fulkerson
Algorithm, there’s no path from source to sink.
In a flow network whose edges all have capacity 1, the maximum flow value equals
the maximum degree of a vertex in the flow network.
Memoization is the basis for a top-down alternative to the usual bottom-up approach to dynamic programming solutions.
The time complexity of a dynamic programming solution is always lower than that of
an exhaustive search for the same problem.
If we multiply all edge capacities in a graph by 5, then the new maximum flow value
is the original one multiplied by 5.
For any graph G with edge capacities and vertices s and t, there always exists an edge
such that increasing the capacity on that edge will increase the maximum flow from s
to t. (Assume that there is at least one path in the graph from s to t. )
Let G be a weighted directed graph with exactly one source s and exactly one sink t.
Let (A, B) be a maximum cut in G, that is, A and B are disjoint sets whose union is V,
s ∈ A,t ∈ B, and the sum of the weights of all edges from A to B is the maximum
for any two such sets. Now let H be the weighted directed graph obtained by adding 1
to the weight of each edge in G. Then (A, B) must still be a maximum cut in H.
Ford-Fulkerson algorithm will always terminate as long as the flow network G has
edges with strictly positive capacities.
Any problem that can be solved using dynamic programming has a polynomial time
worst case time complexity with respect to its input size.
For edge any edge e that is part of the minimum cut in G, if we increase the capacity of that
edge by any integer k>1, then that edge will no longer be part of the minimum cut.
Any problem that can be solved using dynamic programming has a polynomial worst case
time complexity with respect to its input size.
In a dynamic programming solution, the space requirement is always at least as big as the
number of unique sub problems
If f is a max s-t flow of a flow network G with source s and sink t, then the value of the min
s-t cut in the residual graph Gf is 0.
Given a directed graph G=(V,E) and the edge costs, if every edge has a cost of either 1 or -1
then we can determine if it has a negative cost cycle in O(|V|^3) time..
The space efficient version of the solution to the sequence alignment problem (discussed in
class), was a divide and conquer based solution where the divide step was performed using
dynamic programming.
Max-flow in a flow network can be found with a polynomial-time greedy algorithm
Suppose we have two minimum s-t cuts (A1, B1) and (A2, B2) and some max flow f.
Total flow from A1 to B1 is equal to the total capacities of edges going from A2 to B2.
A Weakly polynomial time algorithm is always slower than a strongly polynomial time
divide and conquer solves problems in a top-down manner whereas dynamic
We can solve the weighted interval scheduling problem in linear time using dynamic
programming.
A flow network with unique edge capacities could have more than one min cut.
Ford-Fulkerson Algorithm can solve the max-flow problem in a flow network in
polynomial time if the augmenting path with the fewest number of edges is chosen in
each iteration.
The Ford-Fulkerson Algorithm can find a maximum matching in a bipartite graph in
O(n3) time where n is the number of nodes in the graph.
In a flow network with integer edge capacities, if the capacity of an edge which is not on
a min cut is decreased by k, the value of max flow will go down by at most k-1.
An algorithm runs in weakly polynomial time if the number of operations is bounded by the numerical value of input terms, but not in the number of integers in the input.
For every flow network with a unique min cut and where value of max flow is greater than zero, there is always an edge such that increasing the capacity on that edge will increase the value of the maximum flow in the network.
In a flow network, a flow that contains a negative flow cycle could be a valid flow.
In a flow network, a valid max flow may contain a positive flow cycle.
In a flow network, decreasing the capacity of an edge that does not belong to a min cut
could result in lowering the value of max flow.
In the scaled version of the Ford Fulkerson algorithm, if at a given augmentation step the
bottleneck value is exactly equal to 64 (the threshold value at that scaling phase) then the
bottleneck value for any subsequent augmentation step cannot be greater than 64.
The Ford-Fulkerson algorithm can be used to find the maximum flow through a graph
with cycles.
The Basic Ford-Fulkerson algorithm (without scaling) can be used to solve the feasible
circulation problem in strongly polynomial time.
Suppose, increasing the capacity of edge e by 1, increases value of max flow f by 1. Then it must be that f(e) = capacity (e).
Max flow problems can in general be solved using greedy techniques.
If all edges have unique capacities, the network has a unique minimum cut.
Flow f is maximum flow if and only if there are no augmenting paths.
Suppose a maximum flow allocation is known. Increase the capacity of an edge
by 1 unit. Then, updating a max flow can be easily done by finding an
augmenting path in the residual flow graph.
In order to apply divide & conquer algorithm, we must split the original problem
into at least half the size.
If all edge capacities in a graph are integer multiples of 5 then the maximum flow
value is a multiple of 5.
If all directed edges in a network have distinct capacities, then there is a unique
maximum flow.
Given a bipartite graph and a matching pairs, we can determine if the matching is
maximum or not in O(V+E) time
Maximum flow problem can be efficiently solved by dynamic programming
The difference between dynamic programming and divide and conquer techniques
is that in divide and conquer sub-problems are independent
Binary search could be called a divide and conquer technique
If you have non integer edge capacities, then you cannot have an integer max flow
The Ford Fulkerson algorithm with real valued capacities can run forever
If we have a 0-1 valued s-t flow in a graph of value f, then we have f edge disjoint s-t paths in the graph
Merge sort works because at each level of the algorithm, the merge step assumes that
the two lists are sorted
Suppose that a new max-flow algorithm operating on a flow network G with integer capacities finds a non-integer max-flow f, i.e., the flow assigned to each edge is notnecessarily an integer. Then there may exist some s-t cut (A,B) in G where f out(A) - f in(A) is non-integer.
In a 0-1 knapsack problem, a solution that uses up all of the capacity of the knapsackwill always be optimal.
For every min-cut (A,B) and max-flow f in a flow network G, if e=(u,v) is a directed edge with u ∊ A and v ∊ B, then f(e) = ce.
When the Ford-Fulkerson algorithm terminates, there must not be any directed edgegoing out of the source node S in the residual graph.
If removing an internal node u from a flow network G disconnects its source from its sink, then the number of iterations required for Ford-Fulkerson to find max-flow in G will be bounded by the sum of the capacities of the edges going into u.
In a flow network, if all s-t cuts have integer capacities then all edge capacities must be integers.
If all edge capacities in a flow network are the same constant integer, then a maximum flow can be found in linear time using the Ford-Fulkerson algorithm.
The Sequence Alignment problem discussed at length in lecture (between two strings of size m and n) can be solved given only O(k) memory space where k=min(m,n)
The time complexity of the space-efficient version of the sequence alignment algorithm is O(m + n) (between two strings of size m and n)
Last changed2 years ago
