Difference between revisions of "HardnessTADM2E"
(Recovering wiki) 
(No difference)

Revision as of 18:13, 11 September 2014
Intractable Problems and Approximation Algorithms
Transformations and Satisfiability
<br>91. Give the 3SAT formula that results from applying the reduction of SAT to 3SAT for the formula: <math> (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) </math>
<br>92. Draw the graph that results from the reduction of 3SAT to vertex cover for the expression <math>(x+ \overline y +z) \cdot (\overline x+y+\overline z) \cdot(\overline x+y+z) \cdot (x+\overline y + \overline x) </math>
<br>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.
<br>94. Implement a translator that translates satisfiability instances into equivalent 3SAT instances.
<br>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?
<br>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
<br>97. An instance of the set cover problem consists of a set <math>X</math> of <math>n</math> elements, a family <math>F</math> of subsets of <math>X</math>, and an integer <math>k</math>. The question is, does there exist <math>k</math> subsets from <math>F</math> whose union is <math>X</math>? For example, if <math>X = \{1,2,3,4\}</math> and <math>F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \}</math>, there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math> (for example, <math> \{1,2\}, \{2,3\}, \{4\}</math>). Prove that set cover is NPcomplete with a reduction from vertex cover.
<br>98. The baseball card collector problem is as follows. Given packets <math>P_1, \ldots, P_m</math>, each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying <math>\leq k</math> packets? For example, if the players are <math> \{Aaron, Mays, Ruth, Steven \} </math> and the packets are <math> \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, </math> there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math>, such as <math> \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} </math> Prove that the baseball card collector problem is NPhard using a reduction from vertex cover.
<br>99. The lowdegree spanning tree problem is as follows. Given a graph <math>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree such that all vertices in the tree have degree at most <math>k</math> (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 <math>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree whose highest degree vertex is at least <math>k</math>? 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.
<br>910. Show that the following problem is NPcomplete:
 Problem: Dense subgraph
 Input: A graph <math>G</math>, and integers <math>k</math> and <math>y</math>.
 Output: Does <math>G</math> contain a subgraph with exactly <math>k</math> vertices and at least <math>y</math> edges?
<br>911. Show that the following problem is NPcomplete:
 Problem: Clique, noclique
 Input: An undirected graph <math>G=(V,E)</math> and an integer <math>k</math>.
 Output: Does <math>G</math> contain both a clique of size <math>k</math> and an independent set of size <math>k</math>.
<br>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
<br>913. Prove that the following problem is NPcomplete:
 Problem: Hitting Set
 Input: A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
 Output: Does <math>S</math> contain a subset <math>S'</math> such that <math>S' \leq k</math> and each subset in <math>C</math> contains at least one element from <math>S'</math>?
<br>914. Prove that the following problem is NPcomplete:
 Problem: Knapsack
 Input: A set <math>S</math> of <math>n</math> items, such that the <math>i</math>th item has value <math>v_i</math> and weight <math>w_i</math>. Two positive integers: weight limit <math>W</math> and value requirement <math>V</math>.
 Output: Does there exist a subset <math>S' \in S</math> such that <math>\sum_{i \in S'} w_i \leq W</math> and <math>\sum_{i \in S'} v_i \geq V</math>?
(Hint: start from integer partition.)
<br>915. Prove that the following problem is NPcomplete:
 Problem: Hamiltonian Path
 Input: A graph <math>G</math>, and vertices <math>s</math> and <math>t</math>.
 Output: Does <math>G</math> contain a path which starts from <math>s</math>, ends at <math>t</math>, and visits all vertices without visiting any vertex more than once?
(Hint: start from Hamiltonian cycle.)
<br>916. Prove that the following problem is NPcomplete:
 Problem: Longest Path
 Input: A graph <math>G</math> and positive integer <math>k</math>.
 Output: Does <math>G</math> contain a path that visits at least <math>k</math> different vertices without visiting any vertex more than once?
<br>917. Prove that the following problem is NPcomplete:
 Problem: Dominating Set
 Input: A graph <math>G=(V,E)</math> and positive integer <math>k</math>.
 Output: Is there a subset <math>V' \in V</math> such that <math>V'\leq k</math> where for each vertex <math>x \in V</math> either <math>x \in V'</math> or there exists an edge <math>(x,y)</math>, where <math>y \in V'</math>.
<br>918. Prove that the vertex cover problem (does there exist a subset <math>S</math> of <math>k</math> vertices in a graph <math>G</math> such that every edge in <math>G</math> is incident upon at least one vertex in <math>S</math>?) remains NPcomplete even when all the vertices in the graph are restricted to have even degrees.
<br>919. Prove that the following problem is NPcomplete:
 Problem: Set Packing
 Input: A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
 Output: Does <math>S</math> contain at least <math>k</math> disjoint subsets (i.e., such that none of these subsets have any elements in common?)
<br>920. Prove that the following problem is NPcomplete:
 Problem: Feedback Vertex Set
 Input: A directed graph <math>G=(V,A)</math> and positive integer <math>k</math>.
 Output: Is there a subset <math>V' \in V</math> such that <math>V'\leq k</math>, such that deleting the vertices of <math>V'</math> from <math>G</math> leaves a DAG?
Algorithms for Special Cases
<br>921. A Hamiltonian path <math>P</math> is a path that visits each vertex exactly once. The problem of testing whether a graph <math>G</math> contains a Hamiltonian path is NPcomplete. There does not have to be an edge in <math>G</math> from the ending vertex to the starting vertex of <math>P</math>, unlike in the Hamiltonian cycle problem. Give an <math>O(n+m)</math>time algorithm to test whether a directed acyclic graph <math>G</math> (a DAG) contains a Hamiltonian path. (Hint: think about topological sorting and DFS.)
<br>922. The <math>2</math>SAT problem is, given a Boolean formula in 2conjunctive normal form (CNF), to decide whether the formula is satisfiable. <math>2</math>SAT is like <math>3</math>SAT, except that each clause can have only two literals. For example, the following formula is in <math>2</math>CNF: <math> (x_1 \vee x_2) \wedge (\bar{x}_2 \vee x_3) \wedge (x_1 \vee \bar{x}_3) </math> Give a polynomialtime algorithm to solve <math>2</math>SAT.
P=NP?
<br>923. Show that the following problems are in NP:
 Does graph <math>G</math> have a simple path (i.e., with no vertex repeated) of length <math>k</math>?
 Is integer <math>n</math> composite (i.e., not prime)?
 Does graph <math>G</math> have a vertex cover of size <math>k</math>?
<br>924. It was a long open question whether the decision problem Is integer <math>n</math> 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 <math>O(n)</math> time?
PrimalityTesting(<math>n</math>) composite := <math>false</math> for i := 2 to <math>n1</math> do if <math>(n\,\bmod\,i) = 0</math> then composite := <math>true</math>
Approximation Algorithms
<br>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.
<br>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.
<br>927. The maximum cut problem for a graph <math>G=(V,E)</math> seeks to partition the vertices <math>V</math> into disjoint sets <math>A</math> and <math>B</math> so as to maximize the number of edges <math>(a,b) \in E</math> such that <math>a \in A</math> and <math>b \in B</math>. Consider the following heuristic for max cut. First assign <math>v_1</math> to <math>A</math> and <math>v_2</math> to <math>B</math>. 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.
<br>928. In the binpacking problem, we are given <math>n</math> items with weights <math>w_1,w_2,...,w_n</math>, respectively. Our goal is to find the smallest number of bins that will hold the <math>n</math> 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.
<br>929. For the firstfit heuristic described just above, give an example where the packing it fits uses at least <math>5/3</math> times as many bins as optimal.
<br>930. A vertex coloring of graph <math>G=(V,E)</math> is an assignment of colors to vertices of <math>V</math> such that each edge <math>(x,y)</math> implies that vertices <math>x</math> and <math>y</math> are assigned different colors. Give an algorithm for vertex coloring <math>G</math> using at most <math>\Delta+1</math> colors, where <math>\Delta</math> is the maximum vertex degree of <math>G</math>.