Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 8: Q19E (page 281)

Akiteis a graph on an even number of vertices, say 2n, in which of the vertices form a clique and the remaining vertices are connected in a “tail” that consists of a path joined to one of the vertices of the clique. Given a graph and a goal , the KITE problem asks for a subgraph which is a kite and which contains 2g nodes. Prove that KITE is NP-complete.

Short Answer

Expert verified

The kite problem is reduced to clique and is NP-complete.

Step by step solution

01

Define a Clique

A clique of a graph is the subgraph of the graph. The clique problem is an undirected graph with a goal .Then the clique problem is the subset of vertices that are adjacent to each other and which form a complete graph.

A clique is defined by the following equation Cx=∑i-0wGcixi.

02

Prove KITE is an NP-Complete

Consider the kite graph with 2n vertices, n vertices form a clique, and the other n vertices are connected by a tail path, and the tail ends are connected to a vertex in the clique. Given a graph G and target g , the kite subgraph with 2g vertices need to be calculated.

By adding Vvertices to the graph GV,E,then connecting the Vvertices with the original vertices in G has a one-to-one correspondence to obtain G'. Then the maximum clique problem can be reduced to the Kite problem.

If G has a kite subgraph with 2g vertices if and only if there is a clique of size g in G when the following conditions satisfy.

There is a clique of size g in G⇒G'forms a kite subgraph with 2g vertices.

If G' has 2g kite subgraph, then there must have a group of size g.

Thus, the kite is an NP-complete problem.

Therefore, the kite problem is reduced to clique and is NP-complete.

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 the following problem is NP-complete.

MAXIMUM COMMON SUBGRAPHInput: Two graphs G1=(V1,E1)and G2=(V2,E2); a budget b.Output: Two set of nodes V1'⊆V1and V2'⊆V2whose deletion leaves at leastb nodes in each graph, and makes the two graphs identical.

Search versus decision. Suppose you have a procedure which runs in polynomial time and tells you whether or not a graph has a Rudrata path. Show that you can use it to develop a polynomial-time algorithm for RUDRATA PATH (which returns the actual path, if it exists).

Sequencing by hybridization. One experimental procedure for identifying a new DNA sequence repeatedly probes it to determine which k-mers(substrings of length ) it contains. Based on these, the full sequence must then be reconstructed.Let’s now formulate this as a combinatorial problem. For any string x (the DNA sequence), let Γ(x)denote the multiset of all of its localid="1658905204605" k-mers. In particular, localid="1658904556515" Γ(x)contains exactly |x|-k+1elements.The reconstruction problem is now easy to state: given a multiset of strings, find a string x such that Γ(x)is exactly this multiset.

(a)Show that the reconstruction problem reduces to RUDRATA PATH. (Hint: Construct a directed graph with one node for each localid="1658904858295" k-mers, and with an edge from a to b if the last k-1characters of match the first localid="1658905395287" k-1characters of b.)

(b)But in fact, there is much better news. Show that the same problem also reduces to EULER PATH. (Hint: This time, use one directed edge for each k-mer.)

Optimization versus search.Recall the traveling salesman problem:

TSP

Input: A matrix of distances; a budget b

Output: A tour which passes through all the cities and has length≤b, if such a tour exists.

The optimization version of this problem asks directly for the shortest tour.

TSP-OPT

Input:A matrix of distances

Output:The shortest tour which passes through all the cities.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.

In task scheduling, it is common to use a graph representation with a node for each task and a directed edge from task i to j task if i is a precondition for j. This directed graph depicts the precedence constraints in the scheduling problem. Clearly, a schedule is possibe if and only if the graph is acyclic; if it isn’t, we’d like to identify the smallest number of constraints that must be dropped so as to make it acyclic.

Given a directed graph G=(V,E), a subset E'⊆Eis called a feedback arc set if the removal of edges E' renders G acyclic.

FEEDBACK ARC SET (FAS): Given a directed graph G=(V,E)and a budget , find a feedback arc set of role="math" localid="1658907144825" ≤bedges, if one exists.

(a)Show that FAS is in NP.

FAS can be shown to be NP-complete by a reduction from VERTEX COVER. Given an instance (G,b)of VERTEX COVER, where G is an undirected graph and we want a vertex cover of size ≤b, we construct a instance (G',b)of FAS as follows. If G=(V,E)has vertices v1,K,vnthen make G'=(V',E')a directed graph with 2n verticesw1,w1',k,wn,wn',andn+2|E|(directed) edges:

  • (wi,wi')foralli=1,2,k,n
  • (wi',wj)and(wj',wi)forevery(vi,vj)∈E.
  • Show that if G contains a vertex cover of size b, then G' contains a feedback arc set of size b .
  • Show that if G' contains a feedback arc set of size b, then G contains a vertex cover of size (at most) b. (Hint: Given a feedback arc set of size b in G', you may need to first modify it slightly to obtain another one which is of a more convenient form, but is of the same size or smaller. Then, argue that G must contain a vertex cover of the same size as the modified feedback arc set.)
See all solutions

Recommended explanations on Computer Science Textbooks

Cloud Services

Read Explanation

Computer Systems

Read Explanation

Issues in Computer Science

Read Explanation

Data Structures

Read Explanation

Computer Organisation and Architecture

Read Explanation

Game Design in Computer Science

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