Question: 2 Core is NP - Complete Let G = ( V , E ) be an undirected graph. We say that CsubeV is a core

2

Core is NP

-

Complete

Let

G = (V, E)

be an undirected graph. We say that CsubeV is a core of

G

if for every vertex uinV

- C

there exists vinC such that

(u, v) i n E .

That is

,

every vertex in

G

is either already in the core,

C,

or is adjacent to some vertex in

C .

In this problem, you will show that it is NP

-

complete to determine whether a graph has a small core. Formally, we define CorE by:

Core

INPUT: an undirected graph

G = (V, E)

and natural number

k .

QUESTION: Does

G

have a core

C,

where

| C | k ?

I.e

,

does there exist CsubeV such that

| C | k

and for every uinV

- C

there exists vinC such that

(u, v) i n E ?

Recall that Vertex Cover was shown to be NP

-

complete in lecture:

INPUT: an undirected graph

G = (V, E)

and natural number

k .

QUESTION: Does

G

have a vertex Cover

V^{'},

where

| V^{'} | k ?

I.e

,

does there exist

V^{'}

subeV such that

| V^{'} | k

and for every edge

(u, v) i n E,

we have

u i n V^{'}

v i n V^{'} ?

Show that CORE is NP

-

complete by constructing a

?_{m}^{P} -

reduction

f

from VC to CorE.

Give an example of an undirected graph

G

and a number

k

such that

(G, k) i n

CorE but

(G, k)!

inVC. You can thus conclude that the identity function does not reduce VC to CorE.

Describe a polynomial

-

time function

f

that given input

(G_{1}, k_{1})

outputs

(G_{2}, k_{2})

where

G_{1}

and

G_{2}

are undirected graphs and

k_{1}

and

k_{2}

are natural numbers.

.

.

: the reduction function

f

has

(G_{1}, k_{1})

as its ONLY input. It has no other information. In particular, it does not know whether

G_{1}

has a vertex cover with

k_{1}

vertices.

Briefly argue that

f

runs in time polynomial in the size of

G .

Prove that if

(G_{1}, k_{1}) i n V C

then

(G_{2}, k_{2}) i n C O R E

where

(G_{2}, k_{2}) = f ((G_{1}, k_{1}))

for the function

f

you described in part

1 .

Prove that if

(G_{2}, k_{2}) i n C O R E

then

(G_{1}, k_{1}) i n V C

where

(G_{2}, k_{2}) = f ((G_{1}, k_{1}))

for the function

f

you described in part

1 .

.

.

: the proofs in parts

4

and

5

must be separate proofs. Also, these proofs must hold for all undirected graphs

G,

not just conveniently chosen examples.

(

That

'

s why a proof is required.

)

2 Core is NP - Complete Let G = ( V , E ) be an

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Accounting Questions!

Problem 6 [20 pts]: High School Cliques and Completeness Let G = (V, E) be a graph with |V | = n vertices. G is a complete graph of n vertices, if for every pair of vertices u, v V , u 6= v, (u, v)...

Let G (V, E) denote an weighted undirected graph, in which every edge has unit weight, and let T = (V, E') denote the minimum spanning tree of G. Prove formally that a) for all u, v E V, the path...

ANSI-SPARC6 Programming Language Compilation Write notes on each of the following topics: (a) the implementation of labels and jumps in a recursive, block structured programming language [7 marks]...

Let G = (V, E) be an undirected graph with no parallel edges. A 2-edge-colouring of G is an assignment of a colour 'red' or 'blue' (for short r and b) to each edge of G. Let c : E {r, E be a...

Let G = (V. E) be an undirected graph with all edge weights equal to I. Let d(i, j) denote the length of the shortest path between i and j. Now, suppose we wish to answer queries from the user of the...

Why is there a depletion layer in the immediate vicinity of the junction? 1 [TURN OVER CST.93.1.2 SECTION B 5 Give an ML definition of the function map3 which has the property that map3 f [x1, x2, ....

Let G = (V, E) be an undirected weighted graph with distinct weights we for every edge e E. Let T(V, E) denote the edge set of the unique MST of (V, E). Let W(T) = Eect We be the weight of the edge...

2. Let G (V, E) be an undirected graph with V-[1,2, .. ,n]. Given a vertex r, let A subset S S V is called independent if for every pair of distinct vertices x,y from S, the following holds: A set...

Deduce the type of map3iter and explain in words what the function does. Illustrate your answer by considering the call map3iter g [1, 1, 1, 1, 1, 1]; in an environment in which g is defined as...

Let G = (V, E) be an undirected graph. An independent set of G is a subset V' c V such that, for every edge e = {u, v} e E, at most one of u and v is in V'. We are interested in constructing an...

Go to the PCAOB Web site (www.pcaobus.org). Explain the PCAOB mission and its Rule making process

In your judgment, what are the motivations for two M&As currently in the news?

Bonds can be categorized three ways: domestic, foreign, and _ _ _ _ _ . a . closed b . Australia - bond c . syndicate d . Eurobond e . open

Can you elucidate the role of molecular chaperones and protein quality control systems in maintaining the integrity and homeostasis of the cytoplasm, particularly under conditions of cellular stress...