Show that the following three problems are polynomial reducible to each other Determine, for a given...
Show that the following three problems are polynomial reducible to each other
- Determine, for a given graph G = <V, E> and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.)
- Determine, for a given graph G = <V, E> and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G = <V, E> is a subset V’ of V such that |V’| = k and, for each edge (u, v) in E, at least one of u and v belongs to V’.)
- Determine, for a given graph G = <V, E> and a positive integer m ≤ |V |, whether G contains an independent set of size m or more. (An independent set of size k for a graph G = <V, E> is a subset V’ of V such that |V’| = k and for all u, v in V’, vertices u and v are not adjacent in G.)
Homework Answers
Add Answer to:
Show that the following three problems are polynomial reducible
to each other
Determine, for a given...
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V},...
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V}, E)\) where \(E\) is the complement set of edges. That is \((\mathrm{v}, \mathrm{w})\) is in \(E\) if and only if \((\mathrm{v}, \mathrm{w}) \notin \mathrm{E}\) Theorem: Given \(\mathrm{G}\), the complement graph of \(\mathrm{G}, \bar{G}\) can be constructed in polynomial time. Proof: To construct \(G\), construct a copy of \(\mathrm{V}\) (linear time) and then construct \(E\) by a) constructing all possible edges of between vertices in...
4. Approximating Clique. The Maximum Clique problem is to compute a clique (i.e., a complete subgraph) of maximum size i...
4. Approximating Clique. The Maximum Clique problem is to compute a clique (i.e., a complete subgraph) of maximum size in a given undirected graph G. Let G = (V,E) be an undirected graph. For any integer k ≥ 1, define G(k) to be the undirected graph (V (k), E(k)), where V (k) is the set of all ordered k-tuples of vertices from V , and E(k) is defined so that (v1,v2,...,vk) is adjacent to (w1,w2,...,wk) if and only if, for...
Question 1: Given an undirected connected graph so that every edge belongs to at least one...
Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...
1) Consider the clique problem: given a graph G (V, E) and a positive integer k, determine whethe...
1) Consider the clique problem: given a graph G (V, E) and a positive integer k, determine whether the graph contains a clique of size k, i.e., a set of k vertices S of V such that each pair of vertices of S are neighbours to each other. Design an exhaustive-search algorithm for this problem. Compute also the time complexity of your algorithm.
2. For a given graph G, we say that H is a clique if H is a complete subgraph of Design an algori...
2. For a given graph G, we say that H is a clique if H is a complete subgraph of Design an algorithm such that if given a graph G and an integer k as input, determines whether or not G has a clique with k vertices in polynomial time. (Hint: Try to first find a polynomial time algorithm for a different problem and reduce the clique problem to that problem).
2. For a given graph G, we say that...
2. For a given graph G, we say that H is a clique if H is...
2. For a given graph G, we say that H is a clique if H is a complete subgraph of Design an algorithm such that if given a graph G and an integer k as input, determines whether or not G has a clique with k vertices in polynomial time. (Hint: Try to first find a polynomial time algorithm for a different problem and reduce the clique problem to that problem).
(a) Given a graph G = (V, E) and a number k (1 ≤ k ≤...
(a) Given a graph G = (V, E) and a number k (1 ≤ k ≤ n), the CLIQUE problem asks us whether there is a set of k vertices in G that are all connected to one another. That is, each vertex in the ”clique” is connected to the other k − 1 vertices in the clique; this set of vertices is referred to as a ”k-clique.” Show that this problem is in class NP (verifiable in polynomial time)...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as well as an independent set of size k, provided both exist.
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the...
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the above problems online. 5. The LONGEST PATH problem asks, given an undirected graph G (V, E), and a positive integer k , does G contain a simple path (a path visiting no vertex more than once) with k or more edges? Prove that LONGEST PATH is NP-complete.
Note:...
2. For a given graph G, we say that H is a clique if H is a complete subgraph of Design an algorithm such that if given a graph G and an integer k as input, determines whether or not G has a clique with k vertices in polynomial time. (Hint: Try to first find a polynomial time algorithm for a different problem and reduce the clique problem to that problem).
2. For a given graph G, we say that...
2. For a given graph G, we say that H is a clique if H is a complete subgraph of Design an algorithm such that if given a graph G and an integer k as input, determines whether or not G has a clique with k vertices in polynomial time. (Hint: Try to first find a polynomial time algorithm for a different problem and reduce the clique problem to that problem).
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the above problems online. 5. The LONGEST PATH problem asks, given an undirected graph G (V, E), and a positive integer k , does G contain a simple path (a path visiting no vertex more than once) with k or more edges? Prove that LONGEST PATH is NP-complete.
Note:...
Most questions answered within 3 hours.
-
The blues made its way into many kinds of music. Eric Clapton,
The Beatles, and Elvis...
asked 2 hours ago -
8. A wave in a string has a wave function given by: y (x, t) =...
asked 1 hour ago -
If you’re standing at the bottom of a hill and asked to evaluate
it while being...
asked 2 hours ago -
1. Which region has taken the lead in the world of
e-waste handling?
a) European Union...
asked 2 hours ago -
A 8.15- g bullet from a 9-mm pistol has a velocity of 366.0 m/s.
It strikes...
asked 4 hours ago -
The outstanding bonds of Alpha Extracts have a yield to maturity
of 7.4 percent and a...
asked 4 hours ago -
The Problem: The Case of the Harmonizing Vacations
Your CEO is exploring partnering with a European...
asked 5 hours ago -
A chemical equation is balanced by adding coefficients in front
of some formulas so that the...
asked 5 hours ago -
From the literature (reference your sources): What are the
lattice parameters of calcite and aragonite? Why...
asked 6 hours ago -
Your system is rejecting the question am asking which is
preceded by a case study. It...
asked 6 hours ago -
3. On January 2, 2000, Larry creates a trust with himself as
trustee. Larry as trustee...
asked 6 hours ago -
A member of the volleyball team spikes the ball. During this
process, she changes the velocity...
asked 6 hours ago