balanced k-coloring

We  have  shown  previously  that  independent  set,  vertex  cover,  and clique  are  all  equivalent.   

We  now  show  they  are  all  NP-complete  by showing  independent  set  is.

 

independent set이 NP-complete 임을 보임으로써 나머지 vertex cover, clique 또한 동일하게

NP-complete 임을 확인해보도록 하자.

Up to now, all reductions transformed one form of constraint into another. 

However, independent set is not a constraint satisfaction problem since the independent

set size k is part of the input.

 

지금까지, 모든 reduction은 한 형태의 제약을 다른 형태로 변형시켜왔으나, independent set의 크기 k는

입력의 일부이기 때문에 independent set은 제약 만족 문제가 아니다.

Recall,  [independent  set:   Input:   A  graph  G  and  an  integer  k, 

Question:   Does  G  have  an  independent  set  of  size  k  or  more?]

Need  to  design  a  reduction  from  a  constraint  satisfaction  problem to  a  threshold  problem.
Suppose  we  want  to  reduce  graph  coloring  to  independent  set.

 

제약 만족 문제에서 임계값 문제로의 감소를 설계해야 하기 때문에 graph coloring 을 independent set 으로

줄이는 것을 가정해보도록 한다.

 

Then,  we  need  to  show  how  to  take  an  arbitrary  graph  G  and produce  a  pair  (G′, k)  

such  that  G′ has  an  independent  set  of  size  k if  and  only  if  G  is,  say,  3-colorable.

 

만약 G가 3-colorable 일 경우 G' 이 independent set 의 k 크기를 갖을 때 쌍 (G', k)를 생성하는 방법과

arbitrary graph G 를 어떻게 만들 수 있는지를 보일 필요가 있다.

We can change G to G′ by replacing each vertex of v of G with a triangle (choice gadget), 

and connect the vertices of each triangle to the corresponding vertices of its neighbors. 

 

 

위 그래프 G를 G' 으로 변환하는 모습이다.

independent set 을 만들기 위해서 검은색, 흰색, 그리고 회색 점들에 대해서

(1) 검은색 점 일 경우 : 삼각형 상단에 검은색 점을 배치하도록 한다. 

(2) 흰색 점 일 경우 : 삼각형 하단에 검은색 점을 왼쪽에 배치하도록 한다.

(3) 회색 점 일 경우 : 삼각형 하단에 검은색 점을 오른쪽에 배치하도록 한다.

 

그리고 나머지 흰색 점들에 대해서 삼각형을 각각 형성한 후에 이어주면 위와 같은 independent set 이 형성된다.

5개의 정점을 가진 3-coloring 그래프 G에서 5개의 independent set을 보유한 그래프 G' 로 변환하였다.

즉, Question 에 대해서 해결할 수 있다.

 

To force each triangle to have a vertex in the independent set, we set  k  equal  to  the  number  

of  vertices  in  G.
So  if  G  has  n  vertices,  G′ has  3n  vertices  and  we  set  k  =  n.

graph-3-coloring  ≤  independent  set

 

n개의 정점 갯수를 가진 3-coloring 그래프 G에서 independent set을 가진 그래프 G'으로 변환하기

위해서 3n개의 정점 갯수가 필요하며 n개의 independent set을 보유할 수 있음을 확인하였다.

따라서 graph-3-coloring 은 independent set 으로 감축할 수 있다.

 

 

Example

A k-coloring is balanced if exactly 1 / k of the vertices have each color. 

Show that for any k ≥ 3, the problem of answering balanced graph k-coloring  is  NP-complete.

Then  show  that  it  is  in  P  for  k  =  2.

 

 

balanced graph k-coloring 에 대하여 k 개의 color 가 존재할 경우 각 color 의 갯수가 동일해야 한다.

즉, red, blud, green 이 존재할 경우 red_cnt = blue_cnt = green_cnt = n 을 만족하면 된다.

이 때 k가 3이상일 경우 NP-complete 이며 k = 2일 경우에 P에 속하는 것을 증명해보도록 하자.

 

Proof:           

For  k  ≥  3,  reduce  from  graph  k-coloring  of  G  to  balanced k-coloring  of  G′

where  G′ is  constructed  by  making  k  disjoint  copies of  G.

 

graph k-coloring 에 대한 그래프 G를 balanced k-coloring 에 대한 그래프 G' 으로 감축할 때

동일한 color 별로 k개 만큼 분리함으로써 G' 이 형성된다. (k가 3이상일 경우)

If  G  is  k-colorable,  then  by  permuting  the  colors,  we  can  make  the k-coloring  of  G′ balanced.
Conversely,  if  G′ has  a  balanced  k-coloring,  then  G  is  k-colorable.

 

G가 k-colorable 할 경우에 permutation 을 이용하여 G' balanced k-coloring 을 만들 수 있으며

역으로 G' 가 balanced k-coloring 일 경우 G 는 자연스럽게 k-colorable 임을 알 수 있다.

permutation 하는 경우를 대략적으로 생각해보면 다음과 같은 그림을 떠올릴 수 있을 것 같다.

 

 

For  k  =  2,  graph  k-coloring  ∈  P.  

So  suffices  to  show  that  proving  a graph  G  that  is  2-colorable  is  balanced  ∈  P.  

So  assume  G  is 2-colorable.

 

k = 2 인 graph 2-coloring 을 생각해보면 자연스럽게도 balanced 2-coloring 임을 알 수 있다.

따라서 balanced 2-coloring 은 P 에 속하는 것을 얻을 수 있다.

그렇다면 G가 2-colorable 함을 가정해보도록 하자. 

Each  connected  component  of  the  graph  has  two  2-colorings,  

and  in each  one  the  number  of  black  and  white  vertices  differ  by  some integer  xi.   

If  there  are  l  connected  components,  this  produces  the set  {x1, · · · , xl},  xi ≥  0,    ∀i.
This  turns  balanced  k-coloring  into  integer  partitioning. 

 

balanced k-coloring 에서 integer partitioning 문제로 변환되는 것을 볼 수 있다.

l개의 connected component 가 존재한다면 {x1, ..., xl} 에 대한 set를 만들 수 있으며 음수를 포함하지 않는다.

 

balanced  k-coloring  of  G  has  input  size  Ω(n log n)  where  n  is  the  number  of  vertices  in  G.
However  sigma(i = 1 to l){xi} ≤  n,  so  we  can  solve  this  instance  in polynomial-time  

using  dynamic  programming.

 

다이나믹 프로그래밍을 사용함으로써 polynomial-time 에 해결이 가능함을 알 수 있다.

 

 

Example

The chromatic number χ(G) of a graph G is the smallest k such that G is k-colorable. 

The clique number ω(G) is the size of the largest clique.
Note  that  χ(G)  ≥  ω(G)  since  each  vertex  of  a  clique  needs  a different  color.
Show  that  telling  whether  G  has  the  property  χ(G)  =  ω(G)  is  NP. 

 

χ(G) : k-colorable 인 그래프 G에서의 k 값을 의미한다. (즉, 정점의 color 갯수)

ω(G) : 가장 큰 clique 에 대한 크기를 의미한다.

clique 의 각 정점이 서로 다른 색깔을 보유해야 하기 때문에 χ(G)  ≥  ω(G) 임은 확실하다.

 

 

이때 그래프 G에 대해서 χ(G)  = ω(G) 인지 아닌지를 묻는 것은 NP 에 속함을 보이도록 한다.

 

Proof:           

To  show  it  is  in  NP,  a  witness  would  consist  of  a k-coloring  and  a  k-clique  for  some  k.
The k-coloring shows that χ(G) ≤ k, and the k-clique shows that ω(G) ≥ k. 

But since χ(G) ≥ ω(G), this shows that χ(G) = ω(G).

 

NP 임을 보이기 위해서 k-coloring , k-clique 에 대한 witness 가 필요하다.

확실한 것은 k-coloring 일 경우  χ(G) ≤ k 이며, k-clique 일 경우 ω(G) ≥ k 이다. 

그러나 위에서 확인한 것으로 χ(G)  ≥  ω(G) 임을 보장해야 하므로 결국 χ(G)  = ω(G) 임이 증명되었다.