True/False Exam 2

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.

The scaled version of the Ford-Fulkerson algorithm can compute the maximum flow

in a flow network in polynomial time.

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?

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)?

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.

If a dynamic programming solution is set up correctly, i.e. the recurrence equation is

correct and each unique sub-problem is solved only once (memoization), then the

resulting algorithm will always find the optimal solution in polynomial time.

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)

time.

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

algorithm.

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.

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)