Пограничное разбиение кубических графов на когти и пути

Опять проблема с разделением ребер, сложность которой мне интересна, мотивированная предыдущим моим вопросом .

Вход: кубический граф $G=(V,E)$

Вопрос: есть ли разбиение на , так что подграф, индуцированный каждым является либо когтем (то есть , часто называемым звездой), либо путём ( т.е. )? $E$ $E_1, E_2, \ldots, E_s$ $E_i$ $K_{1,3}$ $3$ $P_4$

Мне кажется, я однажды видел статью, в которой эта проблема оказалась NP-полной, но я больше не могу ее найти, и я не помню, применялся ли этот результат к кубическим графам. По смежному вопросу я знаю, что разбиение ребер двудольного графа на когти является NP-полным (см. Дайер и Фриз ). У кого-нибудь есть ссылка на проблему, которую я описываю, или что-то связанное (то есть та же самая проблема на другом классе графов, которую я мог бы затем попытаться свести к кубическим графам)?

cc.complexity-theory graph-theory np-hardness co.combinatorics Энтони Лабарре
источник

Это может помочь вам: разделить края на а - Complete.

K_{3}

$K_3$

K_{1, 3}

$K_{1,3}$

N P

$NP$

Мухаммед Аль-Туркистани

turkistany, не могли бы вы добавить ссылку на это в свой комментарий?

Энтони Лабарре

Энтони, вот ссылка ( andrew.cmu.edu/user/jblocki/K-Anonymity.pdf )

Мухаммед Аль-Туркистани

О верно. Это бумага, которую я запомнил, и я ошибочно подумал, что она решает именно мою проблему. Ну, в любом случае, спасибо за напоминание, может быть, я действительно могу что-то с этим сделать ...

Энтони Лабарре

У вас есть пример кубического графа, который не может быть разделен таким образом?

Дэвид Эппштейн

Ответы:

Это не ответ на сложность проблемы, но, по крайней мере, показывает, что сложность может быть нетривиальной: это пример кубического графа, который нельзя разбить на пути и когти.

_{(источник: uci.edu )}

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

ETA : приведенный выше график более известен как пример кубического графа без идеального соответствия. Но каждый кубический граф с идеальным соответствием имеет разложение на пути (даже без использования когтей). По теореме Кёнига это включает в себя все кубические двудольные графы, а по теореме Петерсена это включает все кубические графы без мостов, отвечая на вопрос Иосифа Малкевича в комментариях.

Доказательство очень простое: если M - идеальное совпадение в кубическом графе, удаление M оставляет 2-регулярный граф, то есть несвязное объединение циклов. Ориентируйте каждый цикл произвольно и прикрепите каждое ребро uv из M к ребрам цикла, которые следуют за u и v в ориентациях их циклов.

В другом направлении, если существует разложение на пути, то существует идеальное соответствие: средние ребра каждого пути должны совпадать, поскольку никакие два средних ребра не могут иметь общую вершину степени три.

(Отказ от ответственности: эта идея, возможно, уже присутствовала в приглашенном выступлении Карстена Томассена на GD 2010, посвященном проблеме разложения графов такого типа.)

(дополнение к заявлению об отказе от ответственности (от Энтони Лабарре): «идея ориентации» перехода от идеального соответствия к разбиению по путям появляется в этой статье Юнгера, Рейнельта и Пуллибланка , которые приписывают это WH Каннингему.)

Дэвид Эппштейн
источник

Это хороший пример, пока самолет не 2-х связанный. Следующим шагом может быть просмотр плоских 2-связанных графов.

Иосиф Малкевич

Спасибо за ваши ценные комментарии и этот контрпример, я могу перестать искать один ;-)

Энтони Лабарр

Может оказаться полезным, что эти лепестки (уникальный граф с последовательностью степеней 1,3,3,3,3,3) можно (я думаю) использовать вместо петли на ребре в мультиграфном обобщении твоя проблема.

Колин Маккуиллан

~~$k$ $k\geq 3$ $k=3$ $2$ $3$~~

На самом деле это был не конец истории: если кубический граф является двудольным, то легко разделить его набор ребер, используя только когти, выбрав один набор двудольных и сделав его набором «центров когтя». Общая проблема действительно трудна, что может быть доказано с помощью снижения УДОВОЛЬСТВИЯ CUBIC PLANAR MONOTONE 1-IN-3. Все детали в свободном доступе на arxiv .

Энтони Лабарре
источник

Возможно, эта статья может представлять интерес:

Кляйншмидт, Питер. Регулярные разбиения регулярных графов. Канадский Математика Bull. 21 (1978), нет. 2, 177–181.

Он имеет дело с графами, которые можно записать как объединение "Z-путей" длины 3. (В частности, плоские, 3-валентные, 3-связные графы-кубические 3-многогранники.)

Иосиф Малкевич
источник