Given graph πΊ = (π, πΈ) it is said that it is a `star`

if there is a vertex $π£_0 β π$ so that all the other vertices are connected exclusively to it (and not to each other.)

That is, $πΈ = ${ $(π£_π, π£_0) | π£_π β π $ }. Also, given graph πΊ = (π,πΈ) we will also look for its sub-graphs, which are a `star`

. Which is the center of the star.) For example, the following graph:

Is not a star, but it contains an induced sub-graph (above the vertices π, π, π, π, π) which is a star of size 5:

In the optimized version of the problem, we will be interested in finding the largest induced sub-graph that is a star. In the decision version, we also receive as input a natural number π, and are asked “Is there an induced sub-graph of πΊ which is a star β€ k.”?

Formally:

STAR = { $left langle G,k right rangle | $There is a $ Usubseteq V $subgroup so the induced sub-graph $ G_U = (U, E_U) $ which is a star β€ k in size. }

We want to show that the problem is NP-complete. We will see this in parts.

section A

Show that πππ΄π
(πΊ, π) β ππ. You must explain the correctness of the validation algorithm and analyze its runtime.

section B

Show that πππ΄π
is NP-complete. You must:

- Build a reduction that you will see,
- prove its correctness,
- and analyze its running time.

(Instruction: You can show a reduction πππ΄π
β€π πΌπ and assume that πΌπ is NP-complete)

`The direction I was thinking of is to first show that STAR belongs to NP, to say that there is a graph G and a natural number k. The witness will give us an example of the graph and then it will be possible to verify or reject if the graph is STAR.`

`After this, show a reduction from IS to STAR, say that there is a graph `

$G_{IS}$`, which belongs to IS, and from it make a reduction to STAR, what can be done is to add one more vertex to IS, and then it will be STAR. `

`In terms of correctness, it should be seen that if you add a vertex to IS it becomes STAR, and if you remove a vertex that is connected to all the other vertices in STAR, it is IS. `

`It is a polynomial run time that is passed over each edge once, and the number of edges can be, as the number of vertices squared.`

This is the solution I’m thinking of, but I do not know if it is a

correct solution, there are a number of things that need to be done

and proven, and I do not know if I do it right and list it properly.

For the first part I think I did it right, for the second part is not

complicated, but I do not know if I explained enough

section A:

Given a graph πΊ = (π, πΈ) and a natural number π β β our witness will be a subset of vertices π β π. We initialize an array C by the size of the number of vertices V β 0.

We will go through each pair of different π’1, π’2 β π vertices and check whether (π’1, π’2 β πΈ)?

If so, we will increase the content in the position of the vertices in the array by 1. If there is a vertex whose counter is equal to | V | -1 and all the other vertices of their counter are 1, we will return true, otherwise we will return false.

correctness:

(πΊ, π) β STAR β There is a group π β π almost independent in size π β₯ | π | β There is one vertex with a degree of | V | -1 and the other vertices with a degree of 1 β have π β π in size π β₯ | π | For which the verification algorithm returns truth β there is a witness for whom the verification algorithm will return truth β the verification algorithm gets the (πΊ, π).

section B

We will reduce $IS leq _p STAR$, given the instance $(G, k)$ of the IS problem. We will create a new vertex x. We will define $widetilde{V} = π cup {π₯, π¦}$. Also, $widetilde{E} = E cup begin{Bmatrix}

(x,e_1),cdots,(x,e_{|v|}) end{Bmatrix}$. That is, the vertex is connected to the other vertices finally $widetilde{G} = (widetilde{V}, widetilde{E})$. We will define our reduction function: $f(G,k) = (widetilde{G},k+1)$.

The reduction performs a fixed amount of operations, and is therefore polynomial.

We will see its correctness:

$(G,k) in IS Leftrightarrow (widetilde{G},k+1) in STAR$

$Rightarrow $

Suppose that $(G,k) in IS$

We can add vertex x, to subgroup U of vertices V. and | U | Greater than or equal to k. Because we add one vertex, we will turn a set of vertices that have no edge between them, into a set of vertices that are all connected only to vertex x.

That is $(widetilde{G},k+1) in STAR$

$Leftarrow $

Suppose that $(widetilde{G},k + 1) in STAR$. There is a subset $widetilde{U}$ of the vertices $widetilde{V}$. and | $widetilde{U}$ | Greater than or equal to k + 1.

We know that there is an x vertex to which all the other vertices are connected, we will delete that vertex. We get a set of vertices in size | V | Of IS, and with vertices not connected to each other

That is $(G,k) in IS $

`Not sure if I answered the question properly, I also have a hard time showing the correctness of section 2, I do not know if my correctness covers all cases. I'm not sure if I answered it correctly.`