Difference between revisions of "HardnessTADM2E"
(Recovering wiki) 
m (Protected "HardnessTADM2E" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite))) 
(No difference)

Latest revision as of 18:43, 11 September 2014
Intractable Problems and Approximation Algorithms
Transformations and Satisfiability
91.
Give the 3SAT formula that results from applying the reduction of SAT to 3SAT
for the formula:
$ (x+y+\overline z +w+u+\overline v) \cdot (\overline x+\overline y+z+\overline w+u+v) \cdot (x+\overline y+\overline z+w+u+\overline v)\cdot (x+\overline y) $
92.
Draw the graph that results from the reduction of 3SAT to vertex cover
for the expression
$ (x+ \overline y +z) \cdot (\overline x+y+\overline z) \cdot(\overline x+y+z) \cdot (x+\overline y + \overline x) $
93.
Suppose we are given a subroutine which can solve the
traveling salesman decision problem of
page (see book)
in, say, linear time.
Give an efficient algorithm to find the actual TSP tour by
making a polynomial number of calls to this subroutine.
94.
Implement a translator that translates satisfiability instances
into equivalent 3SAT instances.
95.
Design and implement a backtracking algorithm to test whether
a set of formulae are satisfiable.
What criteria can you use to prune this search?
96.
Implement the vertex cover to satisfiability reduction, and run
the resulting clauses through a satisfiability testing code.
Does this seem like a practical way to compute things?
Basic Reductions
97.
An instance of the set cover problem consists of a set $ X $ of $ n $
elements, a family $ F $ of subsets of $ X $, and an integer $ k $.
The question is, does there exist $ k $ subsets from $ F $ whose union is $ X $?
For example, if $ X = \{1,2,3,4\} $ and
$ F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \} $, there does not exist a solution
for $ k=2 $, but there does for $ k=3 $ (for example, $ \{1,2\}, \{2,3\}, \{4\} $).
Prove that set cover is NPcomplete with a reduction from vertex cover.
98.
The baseball card collector problem is as follows.
Given packets $ P_1, \ldots, P_m $, each of which contains a subset of this
year's baseball cards, is it possible to collect all the year's cards by buying $ \leq k $ packets?
For example, if the players are $ \{Aaron, Mays, Ruth, Steven \} $ and the packets are $ \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, $
there does not exist a solution for $ k=2 $, but there does for $ k=3 $, such as $ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} $
Prove that the baseball card collector problem is NPhard using a reduction
from vertex cover.
99.
The lowdegree spanning tree problem is as follows.
Given a graph $ G $ and an integer $ k $, does $ G $ contain a spanning
tree such that all vertices in the tree have degree at most $ k $
(obviously, only tree edges count towards the degree)?
For example, in the following graph, there is no spanning tree such that all
vertices have a degree less than three.
\fixedfigsize{pictures/lowdegree.eps}{1.0in}
 Prove that the lowdegree spanning tree problem is NPhard with a reduction from Hamiltonian path.
 Now consider the highdegree spanning tree problem, which is as follows. Given a graph $ G $ and an integer $ k $, does $ G $ contain a spanning tree whose highest degree vertex is at least $ k $? In the previous example, there exists a spanning tree with a highest degree of 8. Give an efficient algorithm to solve the highdegree spanning tree problem, and an analysis of its time complexity.
910.
Show that the following problem is NPcomplete:
 Problem: Dense subgraph
 Input: A graph $ G $, and integers $ k $ and $ y $.
 Output: Does $ G $ contain a subgraph with exactly $ k $ vertices and at least $ y $ edges?
911.
Show that the following problem is NPcomplete:
 Problem: Clique, noclique
 Input: An undirected graph $ G=(V,E) $ and an integer $ k $.
 Output: Does $ G $ contain both a clique of size $ k $ and an independent set of size $ k $.
912.
An Eulerian cycle is a tour that visits every edge in
a graph exactly once.
An Eulerian subgraph is a subset of the edges and vertices of a graph
that has an Eulerian cycle.
Prove that the problem of finding the number of edges in
the largest Eulerian subgraph of a graph is NPhard.
(Hint: the Hamiltonian circuit problem is NPhard even if each vertex
in the graph is incident upon exactly three edges.)
Creative Reductions
913.
Prove that the following problem is NPcomplete:
 Problem: Hitting Set
 Input: A collection $ C $ of subsets of a set $ S $, positive integer $ k $.
 Output: Does $ S $ contain a subset $ S' $ such that $ S' \leq k $ and each subset in $ C $ contains at least one element from $ S' $?
914.
Prove that the following problem is NPcomplete:
 Problem: Knapsack
 Input: A set $ S $ of $ n $ items, such that the $ i $th item has value $ v_i $ and weight $ w_i $. Two positive integers: weight limit $ W $ and value requirement $ V $.
 Output: Does there exist a subset $ S' \in S $ such that $ \sum_{i \in S'} w_i \leq W $ and $ \sum_{i \in S'} v_i \geq V $?
(Hint: start from integer partition.)
915.
Prove that the following problem is NPcomplete:
 Problem: Hamiltonian Path
 Input: A graph $ G $, and vertices $ s $ and $ t $.
 Output: Does $ G $ contain a path which starts from $ s $, ends at $ t $, and visits all vertices without visiting any vertex more than once?
(Hint: start from Hamiltonian cycle.)
916.
Prove that the following problem is NPcomplete:
 Problem: Longest Path
 Input: A graph $ G $ and positive integer $ k $.
 Output: Does $ G $ contain a path that visits at least $ k $ different vertices without visiting any vertex more than once?
917.
Prove that the following problem is NPcomplete:
 Problem: Dominating Set
 Input: A graph $ G=(V,E) $ and positive integer $ k $.
 Output: Is there a subset $ V' \in V $ such that $ V'\leq k $ where for each vertex $ x \in V $ either $ x \in V' $ or there exists an edge $ (x,y) $, where $ y \in V' $.
918.
Prove that the vertex cover problem (does there exist a subset $ S $ of $ k $
vertices in a graph $ G $ such that every edge in $ G $ is incident upon
at least one vertex in $ S $?) remains NPcomplete even when all the vertices in
the graph are restricted to have even degrees.
919.
Prove that the following problem is NPcomplete:
 Problem: Set Packing
 Input: A collection $ C $ of subsets of a set $ S $, positive integer $ k $.
 Output: Does $ S $ contain at least $ k $ disjoint subsets (i.e., such that none of these subsets have any elements in common?)
920.
Prove that the following problem is NPcomplete:
 Problem: Feedback Vertex Set
 Input: A directed graph $ G=(V,A) $ and positive integer $ k $.
 Output: Is there a subset $ V' \in V $ such that $ V'\leq k $, such that deleting the vertices of $ V' $ from $ G $ leaves a DAG?
Algorithms for Special Cases
921.
A Hamiltonian path $ P $ is a path
that visits each vertex exactly once.
The problem of testing whether a graph $ G $ contains a
Hamiltonian path is NPcomplete.
There does not have to be an
edge in $ G $ from the ending vertex to the starting vertex of $ P $, unlike
in the Hamiltonian cycle problem.
Give an $ O(n+m) $time
algorithm to test whether a directed acyclic graph $ G $ (a DAG)
contains a Hamiltonian path.
(Hint: think about topological sorting and DFS.)
922.
The $ 2 $SAT problem is, given a Boolean formula in 2conjunctive normal form
(CNF), to decide whether the formula is satisfiable.
$ 2 $SAT is like $ 3 $SAT, except that each clause can have only two literals.
For example, the following formula is in $ 2 $CNF:
$ (x_1 \vee x_2) \wedge (\bar{x}_2 \vee x_3) \wedge (x_1 \vee \bar{x}_3) $
Give a polynomialtime algorithm to solve $ 2 $SAT.
P=NP?
923.
Show that the following problems are in NP:
 Does graph $ G $ have a simple path (i.e., with no vertex repeated) of length $ k $?
 Is integer $ n $ composite (i.e., not prime)?
 Does graph $ G $ have a vertex cover of size $ k $?
924.
It was a long open question whether the decision problem Is integer $ n $ a composite number, in other words, not prime? can be computed in
time polynomial in the size of its input.
Why doesn't the following algorithm suffice to prove it is in P,
since it runs in $ O(n) $ time?
PrimalityTesting($ n $) composite := $ false $ for i := 2 to $ n1 $ do if $ (n\,\bmod\,i) = 0 $ then composite := $ true $
Approximation Algorithms
925.
In the maximumsatisfiability problem, we seek a truth assignment that
satisfies as many clauses as possible.
Give an heuristic that always satisfies at least half as many clauses
as the optimal solution.
926.
Consider the following heuristic for vertex cover.
Construct a DFS tree of the graph, and delete all the leaves from this tree.
What remains must be a vertex cover of the graph.
Prove that the size of this cover is at most twice as large as optimal.
927.
The maximum cut problem for a graph $ G=(V,E) $ seeks to partition
the vertices $ V $ into disjoint sets $ A $ and $ B $ so as to maximize the
number of edges $ (a,b) \in E $ such that $ a \in A $ and $ b \in B $.
Consider the following heuristic for max cut.
First assign $ v_1 $ to $ A $ and $ v_2 $ to $ B $.
For each remaining vertex, assign it to the side that adds the most edges
to the cut.
Prove that this cut is at least half as large as the optimal cut.
928.
In the binpacking problem, we are given $ n $ items
with weights $ w_1,w_2,...,w_n $, respectively.
Our goal is to find the smallest
number of bins that will hold the $ n $ objects,
where each bin has capacity of at most one kilogram.
The firstfit heuristic
considers the objects in the order in which they are given.
For each object,
place it into first bin that has room for it.
If no such bin exists, start a new bin.
Prove that this heuristic uses at most twice as many bins as the optimal
solution.
929.
For the firstfit heuristic described just above, give an example where the packing
it fits uses at least $ 5/3 $ times as many bins as optimal.
930.
A vertex coloring of graph $ G=(V,E) $ is an assignment of colors to vertices
of $ V $ such that each edge $ (x,y) $ implies that vertices $ x $ and
$ y $ are assigned different colors.
Give an algorithm for vertex coloring $ G $ using at most $ \Delta+1 $
colors, where $ \Delta $ is the maximum vertex degree of $ G $.