Когда график допускает ориентацию, в которой не более одного шага?

9

Рассмотрим следующую проблему:

Вход: простой (неориентированный) графG=(V,E) .

Вопрос: существует ли ориентация удовлетворяющая свойству того, что для каждого существует не более одного (направленного) - шага?Gs,tVst

Это может быть эквивалентно сформулировано как:

Вход: простой (неориентированный) граф .G=(V,E)

Вопрос: существует ли ациклическая ориентация удовлетворяющая свойству того, что для каждого существует не более одного (направленного) - пути?Gs,tVst

Для какого класса графиков ответ «да»? Можно ли решить эту проблему за полиномиальное время?


Некоторые наблюдения:

  1. Если график является двудольным, то ответ «да».
  2. Если график имеет треугольник, то ответ «нет».

Первое наблюдение следует, ориентируя края от одного раздела к другому. Второе наблюдение легко проверить. Это привело меня к двум неверным догадкам:

  1. Ответ «да», если и только если график является двудольным. (контрпример: 5-тактный)
  2. Ответ «да» тогда и только тогда, когда граф не содержит треугольников (контрпример: декартово произведение ребра с 5-циклом)
Остин Бьюкенен
источник

Ответы:

10

Он NP-завершен за счет сокращения не от всех равных 3SAT. Чтобы увидеть это, обратите внимание, что

  • Единственная действительная ориентация 4-циклом является тот, в котором ребра чередуются ориентации.
  • Позволять P быть ненаправленным путем с тремя ребрами и добавить вершину степени два, смежную с конечными точками P сформировать 5-цикл. Тогда единственные ориентацииP которые могут быть распространены на действительные ориентации всего 5-циклы те, в которых P не всегда ориентирован как направленный путь.

Формируем переменную гаджет для переменной v что принадлежит k различные пункты экземпляра NAE-3SAT путем склеивания k общий 4-циклы на общем краю. Тогда в каждом из4-циклы, противоположный край к общему краю должен быть ориентирован согласованно со всеми остальными 4-циклов. Мы свяжем истинное значение переменной с этой последовательной ориентацией этих ребер. Кроме того, в любой действительной ориентации каждого из этих4-циклы, нет пути от одного 4-цикл в другой 4- цикл, поэтому эти гаджеты могут взаимодействовать друг с другом только в направлении их краев, а не благодаря наличию более длинных путей.

Мы формируем гаджет предложения для предложения с 3 переменными экземпляра NAE-3SAT, склеив три 4-циклы ребер, напротив общих ребер соответствующих трех переменных гаджетов, в 3-реберный путь P а затем добавление вершины второй степени для завершения P в 5-цикл. Как обсуждалось выше, это5-цикл может быть последовательно ориентирован, если и только если его три ребра не все ориентированы как направленный путь, что (при правильном склеивании) истинно тогда и только тогда, когда значения истинности, связанные с этими ориентациями, не равны.

Кстати, DAGS с максимум одним s-t ходить для каждого s-tпара была изучена ранее, как «мультидерево», «сильно однозначные графы» или «мангровые заросли»; см. https://en.wikipedia.org/wiki/Multitree

Дэвид Эппштейн
источник
Спасибо! Я сталкивался с мультидревесной вики раньше. Кажется, они почти то, что я хочу. Единственное отличие состоит в том, что я не хочу ациклическую ориентацию треугольника, но это мультитрех.
Остин Бьюкенен
Я хотел бы привести это. Вы бы предпочли, чтобы я цитировал ответ Суреша здесь или каким-либо другим способом?
Остин Бьюкенен
Метод в ответе Суреша хорош. Кстати, многовариантность: ациклический порядок треугольника в порядке, если вы думаете о нем как о бинарном отношении без N-частичного порядка, но не для версии определения DAG, поскольку предполагается, что DAG транзитивно уменьшается, а ациклический треугольник нет. Поэтому я думаю, что мультидерево (как DAG) - это то же самое, что и в вашем вопросе.
Дэвид Эппштейн