LP релаксация независимого множества

13

Я пробовал следующее расслабление LP максимального независимого набора

maxixi

s.t. xi+xj1 (i,j)E
xi0

Я получаю 1/2 для каждой переменной для каждого кубического недвудольного графа Я попытался.

  1. Верно ли для всех связных кубических недвойственных графов?
  2. Есть ли релаксация LP, которая работает лучше для таких графиков?

Обновление 03/05 :

Вот результат клик-релаксации ЛП, предложенной Натаном.

Я суммировал эксперименты здесь. Интересно, что, кажется, существует довольно много не двудольных графов, для которых простейшая релаксация ЛП является интегральной.

Ярослав Булатов
источник
Решение , конечно , не уникальна. В кубическом двудольном графе вы можете иметь оптимальное решение с x i = 1 в одной части и x i = 0 в другой части. xi=1/2xi=1xi=0
Юкка Суомела
1
Извините, я пропустил важную часть, я рассматриваю только не двудольные кубические графы. Каждый двудольный кубический граф, который я пробовал, имел интегральное решение
Ярослав Булатов
Вам также нужно добавить «подключен», если вы хотите избежать неуникальных решений.
Юкка Суомела
2
(1) Вы забыли написать ограничения неотрицательности. (2) Для двудольных графов оптимальное значение этой релаксации ЛП всегда равно максимальному размеру независимого множества. Это является непосредственным следствием теоремы Кенига .
Цуёси Ито
2
@ Ярослав: Дополнительный вопрос: как вы рисуете эти графики?
Тим

Ответы:

16

Недвудольный подключен кубического граф имеет единственное оптимальное решение ; в двудольном кубическом графе у вас есть интегральное оптимальное решение.xi=1/2


Доказательство: В кубическом графе, если сумма по всем ограничения х я + х J1 , то есть Σ я 3 х я3n/2xi+xj1 , иследовательнооптимальное самое большее п / 2 .i3xi3n/2n/2

Решение для всех я тривиально осуществимо, иследовательнотакжеоптимальным.xi=1/2i

В двудольном кубическом графе каждая часть имеет половину узлов, и, следовательно, решение в одной части также является оптимальным.xi=1

Любое оптимальное решение должно быть плотным, то есть мы должны иметь и, следовательно, x i + x j = 1 для каждого ребра { i , j } . Таким образом , если вы имеете нечетный цикл, вы должны выбрать й я = 1 / 2 для каждого узла в цикле. И тогда, если граф связан, этот выбор распространяется повсеместно.i3xi=3n/2xi+xj=1{i,j}xi=1/2

Юкка Суомела
источник
2
Как я написал в комментарии к вопросу, вам нужно только двудольное, чтобы доказать существование интегрального оптимального решения (но это требует другого доказательства от вашего).
Цуёси Ито
@ Цуйоши: Да, теорема Кенига хороша, чтобы иметь в виду. Например, вместе с вышеприведенным наблюдением будет показано, что любой двудольный кубический граф имеет 1-факторизацию (т. Е. Он может быть разбит на три идеальных соответствия). Конечно, это «неправильный» способ доказать этот результат, но я думаю, что он наглядно демонстрирует силу теоремы Кенига - если вы просто помните теорему Кенига, существует множество классических результатов в теории графов, которые вы можете легко изобрести заново. ,
Юкка Суомела
12

Этот LP является половинным интегралом для всех графов, т. Е. Существует оптимальное решение, такое, что каждая переменная находится в {0,1 / 2,1}. Это просто следует из теоремы Немхаузера и Троттера. Конечно, такой же вывод о полуцелости следует для LP задачи о дополнении (покрытие вершин). Когда граф двудольный, решение является интегральным. Это просто следует из теоремы о минимальном сечении максимального потока или работы с экстремальными точечными решениями этого LP. Кроме того, ребра 1/2 образуют нечетный цикл.

Конечно, этот LP не годится для решения проблемы IS. Добавление ограничений Clique или SDPs - намного лучший подход.

Упаковки вершин: структурные свойства и алгоритмы Г. Л. Немхаузер и Троттер-Матем. Программа., 1975

Мохит Сингх
источник
Справа см. Также теорему 5.6 этой статьи для очень простого алгоритма, который эффективно находит полуцелое решение.
Юкка Суомела
LP с ограничениями Clique решил примерно на 50% больше графиков из приведенного выше .... где я могу найти формулировку SDP?
Ярослав Булатов
6

K4

Это называется дробным независимым числом набора. Там вы найдете некоторую информацию: http://en.wikipedia.org/wiki/Fractional_coloring или в книге «Теория дробных графов» Даниэля Уллмана и Эдварда Шейнермана ( http://www.ams.jhu.edu/~ers / фгт / ).

Kk

Nathann

(*) это, как говорится, теоретически вы имеете сколь угодно большую разницу между оптимальным результатом в LP, где представлены все клики, и оптимальным независимым множеством

Натанн Коэн
источник
1
Одна из проблем этого подхода заключается в том, что если у вас есть недвойственный кубический граф без треугольников (а их много ...), формулировка точно совпадает с формулировкой в ​​вопросе, и мы имеем точно такой же плохие новости. В целом, я думаю, мы всегда можем построить графы, в которых все узлы находятся вККлика и нет (К+1)-клик, и покажи, что Иксязнак равно1/К для всех яявляется уникальным оптимальным решением ЛП.
Юкка Суомела
интересно, это, кажется, связано с легкостью IndependentSet в хордовых графах
Ярослав Булатов
Я провел несколько экспериментов, и решение этой релаксации ЛП всегда было интегральным в хордовых графах
Ярослав Булатов
1
@YaroslavBulatov Есть причина для вашего наблюдения. Неравенства клики и границы неотрицательности обеспечивают выпуклую оболочку независимых множеств тогда и только тогда, когда граф идеален. Аккордовые графики идеальны.
Остин Бьюкенен