Question

In: Advanced Math

Given the following definitions: 1) A subgraph G' of a graph G consists of a subset...

Given the following definitions:

1) A subgraph G' of a graph G consists of a subset of vertices and edges of G. A subgraph G' is complete if there is an edge between any pair of vertices of G'.

2) An independent set of vertices of a graph G is defined as a set S of vertices of G such that there is no edge between any two vertices of S.

Show that finding a complete subgraph of G with k vertices is NP-complete by reducing from the q-Indepedent Set problem (i.e., finding an independent set with q vertices).

Note: you should first present the problem in its decision version and then prove the NP-completeness.

Expert Solution

First show that the Clique problem is NP. Given a Graph G(V,E), If we provide the set of vertices as a certificate of a clique in G, then we can check if V' induces a clique in polynomial time. We can check whether each pair of vertices also belongs in E(G). This can be done in time.

To show Clique problem is NP-Complete, we reduce it from Independent set problem, i.e., . We assume that Finding independent set in a graph is NP-hard.

Take an instance of Independent Set Problem, Graph G(V,E) and q. Decision problem is - does there exists a Independent Set of size q in G? We see that G has an Independent Set of Size q iff has a clique of size q. Construct the Graph as follows. Let . For each vertex and if , then draw edge . If , then we do not draw any edge in . We look at such pairs . Hence we can construct in polynomial time.

Instance of the Clique problem - and q. Does there exists a clique of size q?

We have reduced the Independent Set Problem to Clique Problem in Polynomial time. If we can find answer to clique problem in polynomial time, then essentially we would have found answer to Independent Set Problem in polynomial time, but Independent Set Problem is NP-hard. Hence Clique Problem must also NP-hard.

We have shown that Clique problem is NP and NP hard , hence it is NP-Complete.

Colby Messinger answered 5 months ago

Discuss the following terms giving their definitions and clarifying the definitions by giving suitable examples. 1-subset...

Discuss the following terms giving their definitions and clarifying the definitions by giving suitable examples. 1-subset 2-proper subset 3-improper subset 4-emtpy set 5-power set can you please write the question using the keypoard to be able to copy and paste the answer not picture . Thanks

1. Use the given graph off and g to evaluate the following functions and limits, if...

Use the given graph off and g to evaluate the following functions and limits, if it exists. If the limit does not exist, write DNE and explain why. (a) \(\lim _{x \rightarrow 0^{+}} f(x)=\)(b) \(\lim _{x \rightarrow-1} f(x)=\)(c) \(\lim _{x \rightarrow 1} g(x)=\)(d) \(\lim _{x \rightarrow-2}\left(\frac{f(x)}{g(x)}\right)=\)(e) \(\lim _{x \rightarrow 1}(f(x) \cdot g(x))=\)(f) \(g(-1)=\)(e) \(\lim _{x \rightarrow 3} f(x)=\)(h) \(f(0)=\)Explanation for non existent limits: Explanation is required for credit (i.e., a correct DNE response above is worth no points).

Given a graph G, we obtain the subdivision graph of G, denoted by S(G), by subdividing...

Given a graph G, we obtain the subdivision graph of G, denoted by S(G), by subdividing each edge of G exactly once. Remember to subdivide an edge is to add vertex of degree 2. So if you have an edge (u, v) in G it becomes two edges in S(G). Show that S(G) is bipartite.

Instructions: Question 1: A directed graph G consists of • vertices (V ) (also called nodes)...

Instructions: Question 1: A directed graph G consists of • vertices (V ) (also called nodes) • edges (E) (also called links). An edge can have extra data. The number of nodes |V | and the number of edges |E| are denoted by n and m respectively. An undirected graph is like a directed graph except the edges do not have direction. Some more definitions: • An undirected graph is connected if there exists a path between all u, v...

Given a connected graph G with n vertices. We say an edge of G is a...

Given a connected graph G with n vertices. We say an edge of G is a bridge if the graph becomes a disconnected graph after removing the edge. Give an O(m + n) time algorithm that finds all the bridges. (Partial credits will be given for a polynomial time algorithm.) (Hint: Use DFS)

Let G be an abelian group and K is a subset of G. if K is...

Let G be an abelian group and K is a subset of G. if K is a subgroup of G , show that G is finitely generated if and only if both K and G/K are finitely generated.

You are given an undirected graph G = ( V, E ) in which the edge...

You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.

1. Consider the following reaction: 3CH4(g)→C3H8(g)+2H2(g) Calculate ΔG at 298 K if the reaction mixture consists...

1. Consider the following reaction: 3CH4(g)→C3H8(g)+2H2(g) Calculate ΔG at 298 K if the reaction mixture consists of 41 atm of CH4, 0.011 atm of C3H8, and 2.1×10−2 atm of H2. Express the Gibbs free energy in kilojoules to two significant digits. 2. The element gallium (Ga) freezes at 29.8 ∘C, and its molar enthalpy of fusion is ΔHfus = 5.59 kJ/mol. Calculate the value of ΔS when 61.0 g of Ga(l) solidifies at 29.8 ∘C. in J/K

1.) Use the definitions given in the text to find both the odds for and the...

1.) Use the definitions given in the text to find both the odds for and the odds against the following event. -Flipping 4 fair coins and getting 0 heads. The odds for getting 0 heads are what to what.(Type a whole number.) The odds against getting 0 heads are what to what. (Type a whole number) 2.) Determine whether the following individual events are overlapping or non-overlapping. Then find the probability of the combined event. Getting a sum of either...

2.2.6. Let S be a subset of a group G, and let S^-1 denote {s^-1: s...

2.2.6. Let S be a subset of a group G, and let S^-1 denote {s^-1: s ∈ S}. Show that 〈S^-1〉 = 〈S 〉. In particular, for a ∈ G, 〈a〉 = 〈a^-1〉, so also o(a) =o(a^-1)