Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: 12 E (page 11)

The k−SPANNING TREE problem is the following.Input: An undirected graph G=(V,E) Output: A spanning tree of G in which each node has degree ≤k, if such a tree exists.Show that for any k≥2:

  1. k− SPANNING TREE is a search problem.
  2. k− SPANNING TREE is NP-complete. (Hint: Start with k=2 and consider the relation between this problem and RUDRATA PATH.)

Short Answer

Expert verified

1.k− SPANNING TREE is a search problem for any k≥2.

2.k−SPANNING TREE is NP-complete.

Step by step solution

01

Explain Spanning tree

Consider that the spanning tree is a subset of a Graph G that covers all of the vertices with the fewest number of edges feasible. It can be deduced from this definition that every linked and undirected Graph Gcontains at least one spanning tree

02

To prove that k−  SPANNING TREE is a search problem

Consider the given input and output with k≥2.

Here, it is important to demonstrate that given a solution S to the spanning tree problem that can be checked in polynomial time whether it is in fact a k-spanning tree. This comments to verifying that every node in the original graph is used in S such that S have no cycle because it is a tree.

Every node in the tree has a maximum degree k . All of these can be checked efficiently and therefore the k− spanning tree is a search problem.

Therefore, it can be concluded that for k≥2, the k−spanning tree is a search problem.

03

To prove that k -SPANNING TREE is NP-Complete problem

Any of a class of computer problems for which no efficient solution algorithm has been developed is known as an NP-complete issue.From part (a) it is known that the k−spanning tree is in NP.

In the Rudrata path algorithm, assume G is an unweighted undirected graph. Add weights equal to 1 on every edge of G while executing the Rudrata path algorithm with k=2 .It is observed that a tree that has each vertex with a degree at most 2 is a path. Hence, there is no path without loops that reaches all the vertices so there will be no Rudrata path.

Therefore, it can be concluded that the Rudrata path is reduced to a k−spanning tree along with the fact that the k−spanning tree is in NP.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that any array of integers x[1…n] can be sorted in O (n + M) time, where

role="math" localid="1659938331794" M=maxxi-minxiii

For small M, this is linear time: why doesn’t the Ω(nlogn) lower bound apply in this case?

Is there a faster way to compute the nth Fibonacci number than by fib2 (page 4)? One idea involves matrices.

We start by writing the equations F1=F1 and F2=F0+F1 in matrix notation:


role="math" localid="1659767046297" (F1F2)=(0111).(F0F1).

Similarly,

F2F3=(0111).(F1F2)=(0111)2.(F0F1)

And in general

(FnFn+1)=(0111)n.(F0F1)

So, in order to compute Fn, it suffices to raise this 2×2 matrix, call it X, to the nth power.

a. Show that two 2×2matrices can be multiplied using 4additions and 8multiplications.

But how many matrix multiplications does it take to compute Xn?

b. Show that O(logn) matrix multiplications suffice for computing Xn. (Hint: Think about computing X8.)

Thus, the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is just O(logn), as compared to O(n)for fib2. Have we broken another exponential barrier? The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time offib2becomes O(n).

c. Show that all intermediate results of fib3 are O(n) bits long.


d. Let M(n)be the running time of an algorithm for multiplying n-bit numbers, and assume that M(n)=O(n2) (the school method for multiplication, recalled in Chapter 1, achieves this). Prove that the running time of fib3 is O(M(n)logn).


e. Can you prove that the running time of fib3 is O(M(n))? Assume M(n)=Θ(na)for some 1≤a≤2. (Hint: The lengths of the numbers being multiplied get doubled with every squaring.)


In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit integers faster thanO(n2) . Do you think this is possible? (The answer is in Chapter 2.) Finally, there is a formula for the Fibonacci numbers:

role="math" localid="1659768125292" Fn=15(1+52)n−15(1−52)n.

So, it would appear that we only need to raise a couple of numbers to the nth power in order to computeFn . The problem is that these numbers are irrational, and computing them to sufficient accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of raising these irrational numbers to the nth power. If you know your linear algebra, you should see why. (Hint: What are the eigenvalues of the matrix X?)

The Fibonacci numbers F0,F1,F2,... are defined by the rule

F0=0,F1=1,Fn=Fn−1+Fn−2.

In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.

(a) Use induction to prove that Fn≥20.5nfor n≥6.

(b) Find a constant c<1such thatFn≥2cn for all n≥0. Show that your answer is correct.

(c) What is the largestc you can find for which Fn=Ω(2cn)?

The tramp steamer problem. You are the owner of a steamship that can apply between a group of port cities V . You make money at each port: a visit to city i earns you a profit of pi dollars. Meanwhile, the transportation cost from port i to port j is cij>0 .You want to find a cyclic route in which the ratio of profit to cost is maximized.

To this end, consider a directed graph G=(V,E) whose nodes are ports, and which has edges between each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is

role="math" localid="1658920675878" r(c)=∑i,jicPij∑i,jicCij

Let r' be the maximum ratio achievable by a simple cycle. One way to determine r' is by binary search: by first guessing some ratio r , and then testing whether it is too large or too small. Consider any positive r>0 . Give each edge (i,j) a weight of wij=rcij-pj .

  1. Show that if there is a cycle of negative weight, then .
  2. Show that if all cycles in the graph have strictly positive weight, then r<r*.
  3. Give an efficient algorithm that takes as input a desired accuracy ∈>0 and returns a simple cycle c for which r(C)3r*-∈ Justify the correctness of your algorithm and analyze its running time in terms of |V|,∈ and R=max(i,j)iE(PJCIJ) .

Question: 0.1. In each of the following situations, indicate whether f=O(g),orf=Ω(g),or both (in which case f=⊙(g))
See all solutions

Recommended explanations on Computer Science Textbooks

Big Data

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Network

Read Explanation

Data Representation in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Computer Programming

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free