Проблема разбиения ребер на кубических графах

Была ли изучена сложность следующей проблемы?

Вход : кубический (или регулярный) граф G = ( V , E ) , естественная верхняя граница $3$$G=(V,E)$$t$

Вопрос : есть ли раздел на | E | / 3 части размера 3 , так что сумма порядков (необязательно связанных) соответствующих подграфов не превосходит t ?$E$$|E|/3$$3$$t$

Связанная работа В литературе я нашел довольно много работ, в которых доказываются необходимые и / или достаточные условия существования разбиения на некоторые графы, содержащие три ребра, которые как-то связаны, а некоторые другие на вычислительную сложность - это вопросы, которые пересекаются с выше (например, разбиение должно давать подграфы, изоморфные или P 4 , и вес не связан с данным разбиением), но ни один из них не занимался точно вышеупомянутой проблемой.$K_{1,3}$$P_4$

Перечислять все эти статьи здесь было бы немного утомительно, но большинство из них либо цитируют, либо цитируют Дор и Тарси .

20101024: я нашел эту статью Goldschmidt et al. , которые доказывают, что задача разбиения ребра графа на части, содержащие AT МОСТ ребер, таким образом, что сумма порядков индуцированных подграфов не превосходит t , является NP-полной, даже когда k = 3 . Очевидно ли, что задача остается NP-полной на кубических графах, когда нам требуется строгое равенство относительно k ?$k$$t$$k=3$$k$

Дополнительная информация

Я попробовал несколько стратегий, которые потерпели неудачу. Точнее, я нашел несколько контрпримеров, которые доказывают, что:

• максимизация количества треугольников не приводит к оптимальному решению; что я нахожу как-то нелогичным, поскольку треугольники - это те подграфы с самым низким порядком среди всех возможных графов на трех ребрах;

• разбиение графа на связанные компоненты также не обязательно приводит к оптимальному решению. Причина, по которой она казалась многообещающей, может быть менее очевидной, но во многих случаях можно видеть, что замена ребер так, чтобы соединить данный подграф, приводит к решению с меньшим весом (пример: попробуйте это на треугольнике с одним дополнительным ребром, соединенным с каждым вершина; треугольник - это одна часть, остальная часть - вторая, с общим весом 3 + 6 = 9. Затем замена двух ребер дает путь и звезду с общим весом 4 + 4 = 8.)

Вот предложение, как показать, что это сложно. Я не знаю, работает ли это или нет. Сначала рассмотрим ту же проблему на мультиграфах. NP твердость может быть легче доказать там. Попробуйте уменьшить из кубического MAX CUT, который NP трудно даже приблизить (Берман и Карпински "О некоторых более жестких результатах неприемлемости"). Разделите каждое ребро на две части, и в каждой из новых вершин степени 2 прикрепите вершину с помощью самоконтроля. Ваш максимальный раздел соответствует максимальному сокращению?

-

Вот немного больше объяснений.

(1) Задача максимизации (количество источников + количество стоков) по всем ориентациям кубического графа связана с MAXCUT некоторой линейной функцией. Это требует показа некоторого соответствия между максимальными разрезами и максимальными ориентациями источников и приемников. В одном направлении, в максимальном разрезе (U, V), мы можем ориентировать все ребра от U до V. Внутренние ребра E (U) образуют совпадение, поэтому они могут быть ориентированы произвольно и аналогично для E (V), и Общее количество источников и поглотителей является некоторой линейной функцией размера разреза. В другом направлении, учитывая максимальную ориентацию источников и приемников, разбиение U = вершины степени 0 или 1, V = вершины степени 2 или 3 дает разрез.

(2) В описанном выше преобразовании деления на ребра в оптимальной конфигурации каждый цикл окрашивается так же, как и край рядом с ним, и записывается, что этот край окрашивается так же, как и какой-либо другой (не петельный) край рядом с что. Таким образом, каждый разделенный пополам край имеет один цвет из своей прикрепленной петли и один другой цвет. Это соответствует ориентации и (1) применяется.