2ILC0 Algorithms — Exam Practice Set: Computational Complexity & NP-Hardness | TU Eindhoven Style

Computational Complexity: NP-hard or
polynomial-time?
Multiple-choice practice set — in the style of 2ILC0 Algorithms (TU/e)
Ten questions. Worked solutions begin on the last pages.

For each of the following problems, choose the answer that best explains its computational complexity.
A correct answer scores +0.5 points. An incorrect complexity classification (claiming an NP-hard
problem is polynomial-time solvable, or vice versa) scores −0.25 points. Not choosing any alternative,
or giving the right classification but for the wrong reason, yields 0 points.

Note. Recall that all of the following problems are known to be NP-hard (these are the NP-complete
problems treated in CLRS): Circuit-SAT, Formula-SAT, 3-SAT, Maximum Clique, Minimum
Vertex Cover, Maximum Independent Set, Hamiltonian Cycle, Traveling Salesman
Problem, 3-Colorability, and Subset Sum.


Q1. Longest Simple Cycle
Input: An undirected graph G = (V, E).
Output: A simple cycle in G that visits the maximum possible number of vertices, or NO if G
contains no cycle.
◦ (a) The problem can be solved in polynomial time via dynamic programming.
◦ (b) There is a simple reduction from Hamiltonian Cycle that shows the problem is NP-hard.
◦ (c) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (d) There is a simple reduction from Subset Sum that shows the problem is NP-hard.
◦ (e) The problem can be solved in polynomial time via a different method.
◦ (f) There is a simple reduction from Maximum Clique that shows the problem is NP-hard.


Q2. Balanced Cargo Split
Input: A list of n items with positive integer weights w1 , . . . , wn .
Output: A way to split the items into two groups whose total weights are exactly equal, or NO
if no such split exists.
◦ (a) The problem can be solved in polynomial time via dynamic programming.
◦ (b) The problem can be solved in polynomial time via a greedy algorithm.
◦ (c) There is a simple reduction from Subset Sum that shows the problem is NP-hard.
◦ (d) There is a simple reduction from Hamiltonian Cycle that shows the problem is NP-hard.
◦ (e) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (f) There is a simple reduction from Maximum Independent Set that shows the problem
is NP-hard.


Q3. Tight-Knit Group
Input: An undirected graph G = (V, E) (vertices are people, edges are acquaintances) and two
integers k and t.
Output: A set of k vertices that induces at least t edges (i.e. at least t acquaintance-pairs lie
inside the set), or NO if no such set exists.
◦ (a) There is a simple reduction from Maximum Clique that shows the problem is NP-hard.
◦ (b) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (c) There is a simple reduction from Subset Sum that shows the problem is NP-hard.


1

, ◦ (d) The problem can be solved in polynomial time via dynamic programming.
◦ (e) There is a simple reduction from Hamiltonian Cycle that shows the problem is NP-hard.
◦ (f) The problem can be solved in polynomial time via a different method.


Q4. Conflict-Free Guest List
Input: A set of people and a list of pairs who refuse to attend together.
Output: A guest list (subset of people) of maximum possible size containing no refusing pair.
◦ (a) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (b) The problem can be solved in polynomial time via a greedy algorithm.
◦ (c) There is a simple reduction from Maximum Independent Set that shows the problem
is NP-hard.
◦ (d) There is a simple reduction from Subset Sum that shows the problem is NP-hard.
◦ (e) The problem can be solved in polynomial time via a different method.
◦ (f) There is a simple reduction from 3-SAT that shows the problem is NP-hard.


Q5. Sensor Coverage
Input: An undirected graph G = (V, E) (vertices are locations, edges join nearby locations) and
an integer k.
Output: A set D of at most k locations to place sensors such that every location either has a
sensor or is adjacent to one, or NO if no such set of size ≤ k exists.
◦ (a) There is a simple reduction from Minimum Vertex Cover that shows the problem is
NP-hard.
◦ (b) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (c) The problem can be solved in polynomial time via a greedy algorithm.
◦ (d) There is a simple reduction from Hamiltonian Cycle that shows the problem is NP-hard.
◦ (e) The problem can be solved in polynomial time via dynamic programming.
◦ (f) There is a simple reduction from Maximum Clique that shows the problem is NP-hard.


Q6. Three-Channel Frequency Assignment
Input: An undirected graph G = (V, E) (vertices are transmitters, edges join transmitters that
interfere) and three available channels 1, 2, 3.
Output: An assignment of one channel to each transmitter such that interfering transmitters
get different channels, or NO if no such assignment exists.
◦ (a) The problem can be solved in polynomial time via a different method.
◦ (b) There is a simple reduction from 3-Colorability that shows the problem is NP-hard.
◦ (c) The problem can be solved in polynomial time by a reduction to maximum flow.
◦ (d) There is a simple reduction from Subset Sum that shows the problem is NP-hard.
◦ (e) The problem can be solved in polynomial time via a greedy algorithm.
◦ (f) There is a simple reduction from Minimum Vertex Cover that shows the problem is
NP-hard.


Q7. Assigning Reviewers to Papers
Input: A set of papers and a set of reviewers. Each reviewer r lists the papers they are willing to
review and a maximum number cr of papers they will accept; each paper p needs to be reviewed


2