Maximizing and Minimizing

When Maximizing is Harder than Minimizing

We  showed  previously  that  min  cut  is  in  P.  How  about  max  cut? 

max  cut
Input:   A  weighted  graph  G  and  an  integer  k.
Question:   Does  there  exist  a  cut  in  G  of  weight  k  or  greater? 

 

몇주전에 min cut이 P에 속한 것을 확인하였다. (Duality, Reduction :: M - J - C (tistory.com))

max cut 은 P 에 속하는지 NP 에 속하는지에 대해서 알아보도록 한다.

 

We  will  reduce  nae-3-sat  to  unweighted  max  cut  where  every  edge  has  weight  1.  

 We  will  convert  an  nae-3-sat  formula  φ  to  a  pair (G, k)  such  that  G  has  a  cut  of  weight  k  

if  and  only  if  φ  is satisfiable.

If  the  unweighted  version  of  max  cut  is  NP-complete,  the  weighted version  is  

NP-complete  too,  since  it  is  at  least  as  hard.

 

nae-3-sat를 모든 edge의 가중치가 1인 unweighted max cut 으로 줄일 것이다.
nae-3-sat formula  φ를 쌍 (G, k) 으로 변환하여 φ 가 satisfiable 한 경우에만 그래프 G가 가중치 k의

cut 을 갖도록 할 것이다.
만약 max cut의 가중치가 없는 버전이 NP-complete 인 경우,  가중치 있는 버전도 최소한 그만큼 어렵기

때문에 NP-complete 일 것이다.

 

The  choice  gadgets  have  a  pair  of  vertices  for  each  variable  x  with an  edge  between  them.   

The  constraint  gadgets  are  triangles.   

Including  the  edges  connecting  them  to  the  choice  gadgets,  each  one  has  6  edges.

If its neighbors are not all on the same side of the cut, then we can choose sides for the gadget’s 

vertices so that 5 of these edges are in the cut.

We  achieve  a  cut  of  weight  n + 5m  if  and  only  if  every  clause  can be  satisfied,  

so  we  set  k  =  n + 5m.

Clearly,  this  reduction  can  be  carried  out  in  polynomial  time.

 

선택 가젯에는 각 변수 x에 대하여 정점들의 쌍이 있으며 그 사이에 간선이 있다.
구속조건 가젯은 삼각형이다.
선택 가젯에 연결하는 간선을 포함하여 각 가젯마다 6개의 간선이 있다.
만약 그것의 이웃들이 모두 cut 의 같은 면에 있지 않다면, 이러한 edge 들 중에 5개가 cut에 있도록

가젯의 꼭짓점에 대한 변을 선택할 수 있다.
모든 절이 충족될 수 있는 경우에만 n + 5m의 무게 절감을 달성하므로 k = n + 5m를 설정한다.
분명히 이러한 감축은 polynomial time 으로 수행될 수 있다.

 

 

When Good is Harder than Perfect 

 

max-k-sat

Input:   A  k-sat  formula  φ  and  an  integer  l
Question:   Is  there  a  truth  assignment  that  satisfies  l  or  more clauses  in  φ?

For  k  ≥  3,  max-k-sat  is  trivially  NP-complete  by  setting  l  equal  to the  total  number  of  clauses.
In  fact,  we  will  show  nae-3-sat  ≤  max-2-sat.

For  each  nae-3-sat  clause  (x, y, z),  include  in  φ  the  following  six 2-sat  clauses:

(x ∨ y), (y  ∨ z), (x ∨ z),  (x¯ ∨ y¯), (y¯  ∨ z¯), (x¯ ∨ z¯).

 

Any  truth  assignment  satisfies  3  or  5  of  these  6  clauses,  depending on  whether  or  not 

 it  satisfies  the  corresponding  nae-3-sat  clause.

 

6개의 항중에 3개 또는 5개가 만족하는 경우를 살펴보도록 한다.

(1) x = y = z : 6개의 항 중에 3개의 항을 만족한다.

(2) x = y, x ≠ z  : 6개의 항 중에 5개의 항을 만족한다.

따라서 전부 일치할 경우 3개의 항을 만족하며 전부 일치하지 않을 경우 5개의 항을 만족한다.

즉, 6개의 항중에 최대 5개 항만을 만족하는 것을 알 수 있다.

If  the  original  nae-3-sat  formula  has  m  clauses,  we  set  our  threshold to  l  =  5m.

 

위에서 봤듯이 6개 항중에 최대 5개 항만을 만족하므로 임계값을 l = 5m 으로 설정한다.

Even  if  a  constraint  satisfaction  problem  is  easy,  the  optimization problem  associated  

with  it  can  be  hard.
Rephrased, telling whether we can solve problems approximately can be harder than telling 

whether we can solve them perfectly.

 

제약 만족 문제가 쉬울지라도 이와 관련된 최적화 문제는 어려울 수 있다.
즉, 문제를 대략적으로 풀 수 있는지 말하는 것은 문제를 완벽하게 풀 수 있는지를 말하는 것보다 더 어려울 수 있다.

 

 

When Both Minimizing and Maximizing are Easy 

 

Suppose  we  have  a  problem  for  which  both  minimizing  and maximizing  are  easy.
Does  this  imply  we  can  tell  whether  there  is  a  solution  in  a  given interval?

The  strategy  of  the  greedy  algorithm  for  minimum  spanning  tree works  also  for  maximum

spanning  tree.   

So  both  “extremal”  versions of  the  spanning  tree  problem  are  in  P.

 

최소 스패닝 트리에 대한 그리디 알고리즘의 전략은 최대 스패닝 트리에도 적용된다.

따라서 두 스패닝 트리 문제의 "극단적" 버전은 모두 P에 속한다.

exact  spanning  tree
Input:   A  weighted  graph  G  and  two  integers  l  and  u. 

Question:   Is  there  a  spanning  tree  T   with  weight  w  such  that l  ≤  w  ≤  u?

 

최소 스패닝 트리의 가중치를 l, 최대 스피닝 트리의 가중치를 u라고 할 때,

스패팅 트리의 가중치가 l에서 u사이의 값이 되도록 하는 해당 트리가 존재하는지를 확인해 보도록 하자.

 

Not clear how to generalize the greedy algorithm to exact spanning tree.

We will show that subset sum ≤ exact spanning tree.

(Assume here that subset sum is NP-complete.)

 

subset sum 문제를 exact spanning tree로 감축이 가능한 것을 확인해 보도록 하자.

(subset sum 문제 : 2-sat, Balancing Numbers :: M - J - C (tistory.com))

Consider  the  ladder-shaped  graph.   

 

 

Suppose  we  have  an  instance  of  subset  sum  with  weights  S  =  {x1, · · · , xn}  and  target  t.   

We  construct  G  with  n + 1  rungs and  2(n + 1)  vertices.
Place  the  weights  x1, · · · , xn on  the  n  edges  along  one  beam  of  the ladder,  and 

give  the  other  edges  weight  0.

 

subset sum 에 대한 문제로 가중치 x1, ..., xn 가 존재하는 S와 그에 대한 target 값 t가 주어질 때

이를 n + 1개의 사다리(rung)과 2(n + 1)개의 정점들로 그래프 G를 형성한다.

위와 같이 하단부분에 n + 1개의 정점들로 연결된 간선의 길이를 x1, ..., xn 이라고 하며

상단 부분 n + 1개의 정점들로 연결된 간선과 상단 부분과 하단 부분의 사다리(rung) 부분을 연결한

간선의 길이를 전부 0으로 세팅한다.

Then each spanning tree T of G uses a subset of edges from the weighted beam, and 

T ’s total weight is the weight of this subset. 

Setting l = u = t completes the reduction.

 

G의 각 스패닝 트리 T는 결국 가중치가 존재하는 간선들의 부분 집합을 사용하여 만들 수 있다.

따라서 T의 총 가중치는 이러한 부분 집합의 가중치가 된다.

l = u = t 라고 설정함으로써 결국 감축이 가능하게 된다.

 

 

위와 같이 감축 하는 방법을 대부분 살펴봤다.