= 4. (Independence number) Let G (V,E) be an undirected graph with n vertices. A subset...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
= 4. (Independence number) Let G (V,E) be an undirected graph with n vertices. A subset SCV is independent if no pair of vertices in S is adjacent. In other words, S is independent in G exactly if S is a clique (complete subgraph) in the complement of G. The size of the largest independent set is denoted a (G); this is called the independence number of G. So for instance a (Kn) = 1 and a(Cn) = [n/2] where Cn denotes the cycle of length n. (a) (6 points) Finding the value of a(G) is an optimization problem. State the corresponding decision problem (input, question). Let IND denote this decision problem. (b) (8 points) Prove that IND is NP-complete, using the NP-completeness of CLIQUE, the decision version of the maximum clique problem. (c) (20 points) Prove that a (G) can be computed in time O(F) where F is the n-th Fibonacci number. Hint: build the independent set S recursively. Pick a vertex v V; consider the two cases: v S and v S. (d) (6 points) Suppose every vertex in G has degree 2. Find a(G) in linear time. Describe your algorithm in unambiguous English, no pseudocode needed. Give sufficient detail to justify the linear time claim. (e) (XC 15 points) Prove that a(G) can be computed in time (on) where 1.381 is the positive root of the equation t = t + 1. (Comment: recall that Fn = (") where y1.618 so this is an improvement over part (c).) ("). = 4. (Independence number) Let G (V,E) be an undirected graph with n vertices. A subset SCV is independent if no pair of vertices in S is adjacent. In other words, S is independent in G exactly if S is a clique (complete subgraph) in the complement of G. The size of the largest independent set is denoted a (G); this is called the independence number of G. So for instance a (Kn) = 1 and a(Cn) = [n/2] where Cn denotes the cycle of length n. (a) (6 points) Finding the value of a(G) is an optimization problem. State the corresponding decision problem (input, question). Let IND denote this decision problem. (b) (8 points) Prove that IND is NP-complete, using the NP-completeness of CLIQUE, the decision version of the maximum clique problem. (c) (20 points) Prove that a (G) can be computed in time O(F) where F is the n-th Fibonacci number. Hint: build the independent set S recursively. Pick a vertex v V; consider the two cases: v S and v S. (d) (6 points) Suppose every vertex in G has degree 2. Find a(G) in linear time. Describe your algorithm in unambiguous English, no pseudocode needed. Give sufficient detail to justify the linear time claim. (e) (XC 15 points) Prove that a(G) can be computed in time (on) where 1.381 is the positive root of the equation t = t + 1. (Comment: recall that Fn = (") where y1.618 so this is an improvement over part (c).) (").
Expert Answer:
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date:
Students also viewed these computer network questions
-
Let r and s be solutions to the quadratic equation x 2 b x + c = 0. For n N, define d0 = 0 d1 = r s dn = b dn1 c dn2 (n 2) Prove that dn = r n s n for all n N. [4 marks] (b) Recall that a commutative...
-
Predictive text entry systems are familiar on touch screens and mobile phones. This question asks you to consider how the same principles might be used in a programming editor for creating Java code....
-
At the beginning of the current season, the ledger of Highland Tennis Shop showed Cash $2,500; Inventory $1,700; and Common Stock $4,200. The following transactions were completed during April. Apr....
-
Find the radius and volume of the 10743Tc nucleus.
-
While sitting at your desk during lunch break, slumped over as usual, staring at your computer screen, you see an online article about the dangers of sitting at your desk all day. Yikes. The article...
-
In the organizational chart for the consumer-packaged goods firm in Figure 22 5, where do product line, functional, and geographical groupings occur? Figure 22-5 Chief Marketing Officer or Vice...
-
Thakin Industries Inc. manufactures dorm furniture in separate processes. In each process, materials are entered at the beginning, and conversion costs are incurred uniformly. Production and cost...
-
Transform the E-R model of project2 into a relational model. TransactionNo Date Hired Education Employee Address NumberOfItems Email 100 MemberD Name Transaction D Member TypeName Member Classify...
-
For the current tax year, Morgan had $25,000 of ordinary income. In addition, he had an $1,900 long-term capital loss and a $1,600 short-term capital loss. What will be the amount of Morgan's capital...
-
Case Study - Managing Multicultural Teams The reading is taken from Harvard Business Review, 2006. Please access the reading from the reading list under "Session 10: Working in multicultural teams."...
-
Consider the following data collected in the lab. Fill in the calculated values. Be sure to record the mass and density of the liquid to the correct number of significant figures. Mass Of Graduated...
-
Your bond portfolio has a probability of default of 3%/year, loss given default of 60%, and a weighted average contractual rate of 5.5%/year. A) What is the expected loss per year? B) What is the...
-
Each summary should include a descriptive and evaluative paragraph on the following attributes: Include the origins of the model (who developed it, when was it developed, and the context under which...
-
Option trading 1 Mike buys 6 call options (contracts) on Boeing. Mike does not hold Boeing stock or other option positions. The options expire in five months. The premium is c=$19.97. How much cash...
-
A chemical company spent $530,000 to produce 150,000 gallons of a chemical, which can be sold for $5.20 per gallon. The chemical can be further processed into a weed killer which can be sold for...
-
Explain the circumstances that could result in a long-term bank loan being shown in a statement of financial position as a current liability.
-
Crane l uses 10 kJ of energy to lift a 50 kg box to the roof of a building. Crane 2 uses 20 kl to lift a 100 kg box the same distance. Which crane is more efficient? A. Crane 1 B. Crane 2 C. Both...
-
Christina throws a javelin into the air. As she propels it forward from rest, she does 270 J of work on it. At its highest point, its gravitational potential energy has increased by 70 J. What is the...
-
Two samples of ideal gas, sample 1 and sample 2, have the same thermal energy. Sample l has twice as many atoms as sample 2. What can we say about the temperatures of the two samples? A. T>T B. T = T...
Study smarter with the SolutionInn App