ПРИКЛАДНАЯ МАТЕМАТИКА

УДК 519.1

С. В. Баликян, Р. Р. Камалян

Об NP-полноте задачи существования локально-сбалансированного
2-разбиения двудольных графов G с D(G) = 3

(Представлено академиком Ю.Г. Шукуряном 17/VI 2004)

   В работе рассматриваются неориентированные графы без кратных ребер и петель. Множество вершин графа G обозначается через V(G), множество ребер - через E(G). Наибольшая из степеней вершин графа G обозначается через D(G).
   Для вершины v О V(G) определим множество l(v) = {w О V(G)/(w,v) О E(G)}. 2-разбиением графа G называется функция f : V(G) ® {0,1}. 2-разбиение f графа G называется локально-сбалансированным, если для любой вершины v О V(G)

||{ w О l(v)/f(w) = 1}| - |{w О l(v)/f(w) = 0}|| Ј 1.

Не определяемые понятия можно найти в [1-5].
   Пусть X = { x1,ј,xn} есть множество булевых переменных. Обозначим через = {x1,ј,xn,,ј,} множество литералов переменных множества X. Пусть D = { D1,D2,ј,Dr} есть множество дизъюнкций, состоящих из литералов множества . Через t(Dj) обозначим множество индексов тех переменных, литералы которых включены в дизъюнкцию Dj, j = 1, 2, ј, r. Пусть K(x1,x2,ј,xn) = D1& D2&ј& Dr - конъюнктивная нормальная форма [6]. Для i = 1, ј, n через M(i,K) обозначим множество {Dm(1,i), Dm(2,i), ј, Dm(s(i),i)} всех дизъюнкций из D, содержащих литерал переменной xi (будем считать, что для i = 1, ј, n имеет место неравенство m(1,i) < m(2,i) < ј < m(s(i),i)). Для i = 1, ј, n через M1(i,K) обозначим множество тех дизъюнкций из M(i,K), которые содержат литерал xi, а через M2(i,K) - множество тех дизъюнкций из M(i,K), которые содержат литерал . В [2] доказано, что NP-полной является
   Задача 1: "3 - ВЫПОЛНИМОСТЬ".
   Условие. Пусть X - множество булевых переменных, K(x1, x2, ј, xn) = D1& D2&ј& Dr - конъюнктивная нормальная форма, каждая дизъюнкция которой содержит в точности 3 литерала из .
   Вопрос. Существует ли последовательность (a1, a2,ј, an), где для i = 1, ј, n  ai О {0,1}, для которой K(a1, a2, ј, an) = 1?
   Задача 2:
   Условие. Дан граф G.
   Вопрос. Существует ли локально-сбалансированное 2-разбиение графа G?
   Теорема. Для двудольных графов G с D(G) = 3 задача 2 NP-полна.
   Доказательство. Принадлежность задачи 2 классу NP очевидна.
   Опишем полиномиальный алгоритм, сводящий задачу 1 к задаче 2 для двудольных графов G с D(G) = 3. Пусть в индивидуальной задаче I задачи 1 X = { x1, ј, xn} есть множество переменных, и K(x1, x2, ј, xn) = D1& D2&ј& Dr есть конъюнктивная нормальная форма. Определим граф G(I).
Для i = 1, ј, n, j = 1, ј, r положим:
Vij = м
п
н
п
о
Ж,
если Dj П M(i,K)
{ui,j,1},
если Dj О M1(i,K)
{ui,j,1, ui,j,2, ui,j,3},
если Dj О M2(i,K)
Для j = 1, ј, r положим:
Vj1 = n
И
i=1 
 Vij
Для j = 1, ј, r положим:
Vj2 = { tj,1, tj,2, tj,3, tj,4, tj,5, tj,6, tj,7, tj,8}.
Для j = 1, ј, r положим:
Vj = Vj1ИVj2.
Положим Zr = Ж.
Если r > 1, то для j = 1, ј, r - 1 положим:
Zj = { z1ў(j), z1ўў(j + 1), z2(j,j + 1)}.
  Для i = 1, ј, n при s(i) > 1 и k = 1,ј,s(i) - 1 положим:
W(i,k) = {w1ў(i,m(k,i)),w1ўў(i,m(k + 1,i)),w2(i,m(k,i),m(k + 1,i))}.
Для i = 1, ј, n положим:
Wi1 = м
п
н
п
о
Ж,
если s(i) = 1
s(i)-1
И
k=1 
 W(i,k),
если s(i) > 1.
Для i = 1, ј, n положим:
Wi2 = м
п
н
п
о
Ж,
если s(i) = 1
{w3,1(i)},
если s(i) = 2
{w3,1(i), w3,2(i)},
если s(i) > 2.
Для i = 1, ј, n положим:
Wi = Wi1ИWi2.
Положим:
V(G(I)) = ж
и 		r
И
j=1 
 (VjИZj) ц
ш 		И
 ж
и 		n
И
i=1 
 Wi ц
ш 		.
Для i = 1, ј, n, j = 1,ј, r положим:
Eij1 = м
н
о
Ж,
если Dj П M2(i,K)
{(ui,j,1, ui,j,2), (ui,j,2, ui,j,3)},
если Dj О M2(i,K).
  Для j = 1, ј, r положим:
Ej1 = n
И
i=1 
 Eij1.
Для i = 1, ј, n, j = 1, ј, r положим:
Eij2 = м
п
п
п
н
п
п
п
о
Ж,
если Dj П M(i,K)
{(ui,j,1, tj,1)},
если Dj О M1(i,K)  и i № max
 t(Dj)
{(ui,j,3, tj,1)},
если Dj О M2(i,K)  и i № max
 t(Dj)
{(ui,j,1, tj,5)},
если Dj О M1(i,K)  и i = max
 t(Dj)
{(ui,j,3, tj,5)},
если Dj О M2(i,K)  и i = max
 t(Dj).
  Для j = 1, ј, r положим:
Ej2 = n
И
i=1 
 Eij2.
Для j = 1, ј, r положим:
Ej3 = {(tj,1, tj,2), (tj,2, tj,3), (tj,3, tj,4), (tj,4, tj,5), (tj,5, tj,6), (tj,6, tj,7), (tj,7, tj,8)}.
Положим Er4 = Ж.
Если r > 1, то для j = 1, ј, r - 1 положим:
Ej4 = {(tj,8, z1ў(j)), (z1ў(j), z2(j,j + 1)), (z2(j,j + 1),z1ўў(j + 1)), (z1ўў(j + 1),tj+1,8) }.
  Для i = 1, ј, n при s(i) > 1 и k = 1,ј,s(i) - 1 положим:
Eik5 = {(ui,m(k,i),1, w1ў(i,m(k,i))), (w1ў(i,m(k,i)), w2(i,m(k,i), m(k + 1,i))),
       (w2(i,m(k,i), m(k + 1,i)), w1ўў(i,m(k + 1,i))), (w1ўў(i,m(k + 1,i)), ui,m(k+1,i),1)}.
Для i = 1, ј, n положим:
Ei5 = м
п
н
п
о
Ж,
если s(i) = 1
s(i)-1
И
k=1 
 Eik5,
если s(i) > 1.
Для i = 1, ј, n положим:
Ei6 = м
п
п
н
п
п
о
Ж,
если s(i) = 1
{(w2(i,m(1,i), m(2,i)), w3,1(i))},
если s(i) = 2
{(w2(i,m(1,i), m(2,i)), w3,1(i)),
      (w2(i,m(s(i) - 1,i), m(s(i),i)), w3,2(i))},
если s(i) > 2.
Положим:
E(G(I)) = ж
и 		r
И
j=1 
 ж
и 		4
И
p=1 
 Ejp ц
ш 		ц
ш 		И
 ж
и 		n
И
i=1 
 ( Ei5ИEi6) ц
ш 		.

   Граф G(I) определен. Ясно, что D(G(I)) = 3. С помощью лемм 1.1 и 1.2 работы [7] нетрудно показать, что G(I) является двудольным графом.
   Рассмотрим индивидуальную задачу I' задачи 2, в которой в качестве графа дан граф G(I). Покажем, что в индивидуальной задаче I ответ положительный тогда и только тогда, когда в индивидуальной задаче I' ответ положительный.
   Пусть для графа G(I) существует локально-сбалансированное 2-разбиение f. Очевидно, что f(t1,8) = f(t2,8) = ј  =  f(tr,8). Без потери общности можно считать, что f(t1,8) = 1.
   Легко видеть также, что для i = 1, ј, n
f(ui,m(1,i),1) = f(ui,m(2,i),1) = ј  = f(ui,m(s(i),i),1).
  Для i = 1, ј, n и j = 1, ј, r определим множество Vij3 Н V(G(I)) следующим образом:
V3ij = м
п
н
п
о
Ж,
если Dj П M(i,K)
{ui,j,1},
если Dj О M1(i,K)
{ui,j,3},
если Dj О M2(i,K).
Для j = 1, ј, r положим:
Vj3 = n
И
i=1 
 Vij3.
Легко видеть, что для j = 1, ј, r
Vj3 = (l(tj,1)\{tj,2}) И
 (l(tj,5)\{tj,4, tj,6}).

Убедимся, что если для некоторого j0, 1 Ј j0 Ј r, f(tj0,8) = 1, то существуют l0 О {1,3} и i0 О t(Dj0) такие, что ui0,j0,l0 О Vj03 и f(ui0,j0,l0) = 1. Действительно, из f(tj0,8) = 1 следует f(tj0,6) = 0, откуда: либо f(tj0,4) = 0 и существует l0 О {1,3} такое, что umaxt(Dj0),j0,l0 О l(tj0,5)\{tj0,4, tj0,6} и f(umaxt(Dj0),j0,l0) = 1, либо f(tj0,4) = 1, откуда f(tj0,2) = 0 и, следовательно, существуют l0 О {1,3} и i0 О t(Dj0), i0 № maxt(Dj0), для которых ui0,j0,l0 О l(tj0,1)\{tj0,2} и f(ui0,j0,l0) = 1. Следовательно, существуют функции g1:{1,ј,r}®{1,3} и g2:{1, ј, r}®{1, ј, n} такие, что для j = 1,ј,r g2(j) О t(Dj) и выполнены условия ug2(j),j,g1(j) О Vj3 и f(ug2(j),j,g1(j)) = 1. Определим набор m є (m1,m2,ј,mn) следующим образом. Для i = 1,ј,n положим mi = f(ui,m(1,i),1). Покажем, что K(m1,m2,ј,mn) = 1. Убедимся, что для любого j, 1 Ј j Ј r при xi = mi, i = 1, ј, n, дизъюнкция Dj конъюнктивной нормальной формы K(x1,x2,ј,xn) принимает значение 1. Если Dj О M1(g2(j),K), то g1(j) = 1 и mg2(j) = f(ug2(j), m(1,g2(j),1)) = f(ug2(j),j,1) = 1, и утверждение очевидно. Если Dj О M2(g2(j),K), то g1(j) = 3 и f(ug2(j),j,3) = 1, откуда f(ug2(j),j,1) = 0. Но f(ug2(j),j,1) = f(ug2(j), m(1,g2(j),1)) = mg2(j), и утверждение доказано.
   Теперь предположим, что существует набор v є (v1,v2,ј,vn), для которого  K(v1,v2,ј,vn) = 1.  Опишем  алгоритм  построения  функции Fn:V(G(I)) ® {0,1}, являющейся локально-сбалансированным 2-разбиением графа G(I).
   Алгоритм:
Этап 1:
Для i = 1, ј, n и j = m(1,i), m(2,i), ј, m(s(i),i) положим Fn (ui,j,1) = vi.
Для i = 1, ј, n и j = 1, ј, r при Dj О M2(i,K) положим
Fn (ui,j,3) = 1 - Fn (ui,j,1).
Для j = 1, ј, r положим Fn (tj,2) = 1 -Fn (V).

Для j = 1,ј, r положим Fn (tj,4) = 1 - Fn (tj,2).
Так как K(v1,v2,ј,vn) = 1, то для j = 1, ј, r, Fn (V) = 1.
Для j = 1, ј, r положим Fn (tj,6) = 1 -Fn (V)

Ясно, что Fn (t1,6) = Fn (t2,6) = ј  = Fn (tr,6) = 0.
Для j = 1, ј, r положим Fn (tj,8) = 1.
Для j = 1, ј, r - 1 положим Fn (z2(j,j + 1)) = 0.
Для i = 1, ј, n при s(i) > 1 и k = 1, ј, s(i) - 1 положим Fn (w2(i,m(k,i), m(k + 1,i))) = 1 - vi.
Этап 1 завершен.

Этап 2:
Для j = 1, ј, r - 1 положим Fn (z1ў(j)) = 0, Fn (z1ўў(j + 1)) = 1.
Для j = 1, ј, r - 1 положим Fn (tj,7) = 1, Fn (tj,5) = 0, Fn (tj,3) = 1, Fn (tj,1) = 0.
Положим Fn (tr,7) = 0, Fn (tr,5) = 1, Fn (tr,3) = 0, Fn (tr,1) = 1.
Для i = 1, ј, n и j = 1, ј, r при Dj О M2(i,K) положим Fn (ui,j,2) = 1 - Fn (tj,1).
Для i = 1, ј, n при s(i) > 2 и k = 2, ј, s(i) - 1 положим Fn (w1ўў(i,m(k,i))) = 1, Fn (w1ў(i,m(k,i))) = 0.
Для i = 1, ј, n при s(i) > 1 положим:
Fn (w1ў(i,m(1,i))) = м
н
о
1 - Fn (tm(1,i),1),
 если Dm(1,i) О M1(i,K)
1 - Fn (ui,m(1,i),2),
 если Dm(1,i) О M2(i,K)
Fn (w1ўў(i,m(s(i),i))) = м
н
о
1 - Fn (tm(s(i),i),1),
 если Dm(s(i),i) О M1(i,K)
1 - Fn (ui,m(s(i),i),2),
 если Dm(s(i),i) О M2(i,K)
Для i = 1, ј, n при s(i) > 2 положим Fn (w3,1(i)) = 0, Fn (w3,2(i)) = 1.
Для i = 1, ј, n при s(i) = 2 положим
Fn (w3,1(i)) = 1 - max  {Fn (w1ў(i,m(1,i))),  Fn (w1ўў(i,m(2,i)))}.
   Этап 2 завершен. Алгоритм завершен.
   Легко видеть, что функция Fn является локально-сбалансированным 2-разбиением графа G(I). Теорема доказана.
   Настоящее исследование поддержано целевой программой 04-10-31 РА.

   Ереванский государственный университет
   Институт проблем информатики и автоматизации НАН РА

Литература

     1. Harary F.  Graph Theory. Addison-Wesley. Reading. MA. 1969.
     2. Cook S.A.  - Proc. 3rd Ann. ACM Symp. On Theory of Computing. Association for Computing Machinery. New York. 1971. P.151-158.
     3. Garey M.R., Jonson D.S.  Computers and Intractability: A Guid to the Theory of NP-completeness. San Francisco: W.H.Freman & Company. Publishers. 1979.
     4. Papadimitriou C.H., Steiglitz K.  Combinatorial optimization: Algorithms and Complexity. PRENTICE-HALL. INC Englewood Cliffs. New Jersey. 1982.
     5. Karp R.M.  In: Complexity of Computer Computations. Eds. R.E. Miller and J.W. Thatcher. Plenum Press. New York. 1972. P. 85-103.
     6. Яблонский С. В.  Введение в дискретную математику. М. Наука. 1986. 384 с.
     7. Мкртчян В. В.  О сложности задач построения в графе максимальных паросочетаний специального типа. Диссертация на соискание степени магистра. ЕГУ. Факультет информатики и прикладной математики. Кафедра мат. методов и моделирования. Ереван. 2003. 20 с.