T/F Questions:
Practice Exam 2
1. (T/F) Problem X is in NP, and if it can be solved in polynomial time, then P=NP.
2. (T/F) If a problem X can be written as an Integer Linear Program, and X can be solved in polynomial time, then P = NP.
3. (T/F) X is the problem that determines whether there exists a cycle in an undirected graph. Then X can be reduced to the circuit satisfiability problem.
4. (T/F) For a flow network G = (V;E) that can carry a flow of up to k > 0 units, if the capacity of each edge in a flow network is multiplied by m, then the resulting flow network will have a max flow of value mk.
5. (T/F) Linear programming is Polynomial time reducible to Integer Linear Programming.
6. (T/F) For 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.
Multi-choice Questions:
1. Problem X is in NP. Then problem X is NP-Complete if:
a. Y is some problem in NP, and Y can be reduced to X in polynomial time.
b. Y is some problem in NP, and X can be reduced to Y in polynomial time.
c. X can be reduced to the independent set problem in polynomial time,
d. The independent set problem can be reduced to X in polynomial time.
2. For the following statements, which of them is true?
a. NP-Hard is a subset of NP-Complete.
b. X is a known NP-Complete problem, if we can reduce X to another
problem Y, then Y must be in the set of NP-Hard problems.
c. 3-SAT problem is the first problem that was proved as NP-Complete.
3. Consider four linear programs having the objectives
max 𝑐𝑇𝑥, min 𝑐𝑇𝑥, max − 𝑐𝑇𝑥, min − 𝑐𝑇 𝑥, with all four being subject to the
same set of a. b. c. d.
4. If the to be:
a. b. c. d.
constraints. Let the optimal objective values be α, β, γ, δ resp. Then: α ≥ β
α ≥ γ
α + γ = 0
α + δ = 0
dual of a linear program is feasible unbounded, it is possible for the primal
feasible bounded feasible unbounded infeasible
all of the above
5. What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
a. 𝑂(|𝐸|log|𝑉|) b. 𝑂(|𝐸|)
c. 𝑂(|𝐸|2|V|)
d. 𝑂(|𝐸||𝑉|)
6. Which of the following statements is the correct answer of max-flow?
a. If you have non integer edge capacities, then you cannot have an integer max flow.
b. The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the network.
c. 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 value remains unchanged.
d. In a flow network whose edges all have capacity 1, the maximum value equals the maximum degree of a vertex in the flow network.
Long Questions:
1. Video Game Test
You work at a video game company, and the company will release n types of games to the market. Before releasing the games, you need to do the game test first. You are trying to distribute n types of games to a total of m players. However, each type of video game is of interest to only a subset of m players. No video game should be given to a player for testing who is not interested in it. On the other hand, each player can receive at most k video games. No player can receive duplicated video games for testing.Design an efficient network flow based algorithm that maximizes the total number of video games given to the players, you need to make a claim and prove the claim in both directions. You can assume that m ≥ n.
2. Dual
Consider the following LP: min2𝑥1 + 3𝑥2 − 𝑥3
subject to 𝑥1 + 4𝑥2 = 2 3𝑥1 − 𝑥2 ≥ 1
𝑥1 + 2𝑥2+3𝑥3≤3
𝑥! ≥ 0, 𝑥2 ≤ 0
Find the dual of this LP having at most 3 variables and 3 constraints.
3. LP
Threenodes𝑢, 𝑣, 𝑤inagraph𝐺 = (𝑉, 𝐸)aresaidtoformatriangleif
(𝑢, 𝑣), (𝑣, 𝑤), (𝑢, 𝑤) ∈ 𝐸. A triangle-free subset 𝑇 ⊆ 𝑉is one such that no three nodes in 𝑇 form a triangle. Write an integer linear program to compute the largest triangle-free subset of 𝐺.
4. NP-Completeness
There are 𝑁cities, and there are some undirected roads connecting them, so they form an undirected graph 𝐺 = (𝑉, 𝐸). You want to know, given 𝐾 and 𝑀, if there exists a subset of cities of size 𝐾, and the total number of roads between these cities is larger or equal to 𝑀. Prove that the problem is NP-Complete.
5. Approximation
You are given a 2-approximation poly-time algorithm A for the Maximum Clique Problem. Show how can you use this algorithm to provide a α-approximation algorithm B for the Independent set problem, where α is a constant. Find the value of α.
Recall that independent set of a graph 𝐺 = (𝑉, 𝐸) is a subset 𝑉’ ⊆ 𝑉 of vertices such that each edge in 𝐸 is incident on at most one vertex in 𝑉’. The independent set
problem is to find a maximum-size independent set in 𝐺.
A clique of a graph 𝐺 = (𝑉, 𝐸) is a subset 𝑉’ ⊆ 𝑉 of vertices, each pair of which is connected by an edge in 𝐸. The clique problem is to find a maximum-size clique in 𝐺.