Chapter 0: Q23P (page 1)

Let $HALF - CLIQUE = {< G > | G$ s an undirected graph having a complete subgraph with at least $m / 2$ nodes, where m is the number of nodes in $G$ . Show that HALF-CLIQUE is NP-complete.

Short Answer

Expert verified

The clique is $k$ a clique of $g$ , and hence $⟨ G, k ⟩ \in C L I Q U E .$

Step by step solution

Step 1:Undirected graph of the nodes

$H A L F - C L I Q U E \in N P :$

Let N be the nondeterministic polynomial time (NTM) that decides $H A L F - C L I Q U E$ in polynomial time.

N can be described as follows:

$N ='' o n i n p u t g r a p h ⟨ G ⟩ :$

Non-deterministically choose at least $n / 2$ nodes

Verify whether $n / 2$ nodes form a clique

If they form a clique then accept.

Otherwise, reject".

Therefore, $H A L F - C L I Q U E \in N P$

$C L I Q U E ⩽_{p} H A L F - C L I Q U E :$

A reduction from $C L I Q U E$ to $H A L F-C L I Q U E$ as follows:

On input $⟨ G, k ⟩, w h e r e G$ is a graph on n verifies and k is an integer:

Step 2:Size of the Half-Clique

When $k < n / 2$ G has a $k$ -clique, then $G$ has a clique of size.

$k + (n - 2 k) = (2 n - 2 k) / 2$

width="197">k+n-2k=2n-2k/2

Therefore, the HALF-CLIQUE 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!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Let $HALF - CLIQUE = {< G > | G$ s an undirected graph having a complete subgraph with at least $m / 2$ nodes, where m is the number of nodes in $G$ . Show that HALF-CLIQUE is NP-complete.

Short Answer

Step by step solution

Step 1:Undirected graph of the nodes

Step 2:Size of the Half-Clique

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Data Representation in Computer Science

Computer Organisation and Architecture

Data Structures

Functional Programming

Game Design in Computer Science

Issues in Computer Science

Study anywhere. Anytime. Across all devices.

Let HALF-CLIQUE={<G>|Gs an undirected graph having a complete subgraph with at leastm/2 nodes, where m is the number of nodes inG. Show that HALF-CLIQUE is NP-complete.

Short Answer

Step by step solution

Step 1:Undirected graph of the nodes

Step 2:Size of the Half-Clique

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Data Representation in Computer Science

Computer Organisation and Architecture

Data Structures

Functional Programming

Game Design in Computer Science

Issues in Computer Science

Study anywhere. Anytime. Across all devices.

Let $HALF - CLIQUE = {< G > | G$ s an undirected graph having a complete subgraph with at least $m / 2$ nodes, where m is the number of nodes in $G$ . Show that HALF-CLIQUE is NP-complete.