Добавьте соответствие к гамильтонову пути, чтобы уменьшить максимальное расстояние между заданными парами вершин

14

Какова сложность следующей проблемы?

Вход :

Запрос : существует ли сопоставление M такое, что для каждого (v,U)р , dграмм(v,U)К ?
(где граммзнак равно([N],MЧАС) )

У меня была дискуссия с другом об этой проблеме. Мой друг считает, что проблема в полиномиальном времени. Я думаю, что это NP-полная.

PFIM
источник
11
Вы можете упростить это дальше, по крайней мере, с точки зрения представления. Вам дано , путь с n вершинами и набор R пар этих вершин. Вы хотите дополнить путь соответствием так, чтобы расстояние между любой парой в R было не больше k . knRRК
Сашо Николов
Я думаю, что эта формулировка может сбить с толку после моего последнего редактирования, чтобы убрать некоторую двусмысленность.
пфим
1
Моя интерпретация верна, не так ли?
Сашо Николов
Я сделал правку, чтобы сделать постановку задачи более строгой. Я думаю, что это можно еще больше упростить, поскольку вы можете просто предположить, что H - это гамильтонова траектория 1-2-3-4-5 ...- n без потери общности. Так что вам просто нужно . n
Каве

Ответы:

1

Этот ответ неверен .

Твой друг прав. Ваша проблема (как интерпретируется Sasho) не накладывает каких - либо ограничений по мощности согласующего . Таким образом, выбор C , чтобы быть соответствие между парами в R . Тогда для любого натурального числа k расстояние между каждой парой в R меньше, чем k .ССрКрК

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

Мухаммед Аль-Туркистани
источник
Что вы подразумеваете под «соответствием между парами в »? р
Эмиль Йержабек поддерживает Монику
@ EmilJeřábek Это означает соединение узлов каждой пары в ребром. Так что C - это просто R с ребром, соединяющим каждую пару. Это эквивалентно тому , пополняя путь Р с идеальной марширующих по парам R . RCRPR
Мухаммед Аль-Туркистани
1
Это не имеет большого смысла для меня. Что если не совпадает? Скажем, если R содержит пары ( 1 , 2 ) и ( 1 , 3 ) , как вы выбираете C ? RR(1,2)(1,3)C
Эмиль Йержабек поддерживает Монику
@ EmilJeřábek Да. Ваша точка зрения действительна. Я отредактирую свой ответ.
Мухаммед Аль-Туркистани
@pfim Можно ли сформировать кратчайший путь, используя только ребра из ? C
Мухаммед Аль-Туркистани
0

ОБНОВЛЕНИЕ: ответ ниже не является правильным, потому что я ошибочно предположил, что гамильтонов путь лежит в произвольном графе, а не в . Я оставляю его без изменений, возможно, я смогу это исправить или он даст некоторые подсказки для другого ответа.Kn

Я думаю, что это NP-полная. Это очень неформальная / быстрая идея сокращения от 3SAT

Для каждой переменной добавляю «гаджет переменной» с:xi

  • три узла Xi,+Xi,Xi
  • два переменных ребра и ( X i , - X i )(Xi,+Xi)(Xi,Xi)

Добавьте исходный узел и подключите его ко всем переменным X i .SXi

Для каждого предложения добавьте узел C j и соедините его с соответствующими переменными + X i или - X i, которые образуют предложение.CjCj+XiXi

На следующем рисунке изображено: (+x1x2x3)(x2x3x4)

enter image description here

Множество (узлы , которые должны быть связаны) содержит ( S , C 1 ) , ( S , С 2 ) , . , ,R(S,C1),(S,C2),...

Простой путь должен включать все «СИНИЕ» ребра, кроме переменных ребер ( X i , + X i ) и ( X i , - X i ) (на рисунке выше синие ребра представляют ребра, которые мы включаем в P ).P(Xi,+Xi)(Xi,Xi)P

На этом этапе исходная формула выполнима тогда и только тогда, когда кратчайший путь от к каждому узлу предложения C j не больше трех. В самом деле, чтобы достичь предложения из S за три шага, мы должны пройти хотя бы одну переменную X i : S X i± X iC j . Таким образом, мы должны пересечь одно из двух ребер: X i+ X i или X i- X i ) и включить его в CSCjSXiSXi±XiCjXi+XiXiXi)C(потому что по построению это не часть ). Но оба не могут быть включены, потому что они имеют общую вершину.P

Но мы не уверены, что сможем построить простой путь который включает все синие ребра, потому что некоторые узлы имеют более одного падающего синего ребра.P

Чтобы исправить это, мы заменим каждый узел множеством падающих синих ребер деревом, содержащим только пары падающих синих ребер, которые будут включены в и ребрами, которые их разделяют, и которые должны быть включены в C, чтобы достичь узлов предложения:PC

enter image description here

Исходный график становится:

enter image description here

KCjS

C

P

enter image description here

Марцио де Биаси
источник
Меня беспокоит попытка построить путь, содержащий все синие ребра: в некоторых вершинах более двух синих ребер, падающих на них, поэтому не может быть ни одного простого пути, включая все синие ребра.
Михаил Рудой
Хорошо, спасибо ... Я полностью забыл, что такое простой путь :-( ... теперь он должен быть исправлен.
Марцио Де
Этот пост по математике. Предполагается, что проблема не является NP-полной. Это может быть неразрешимым, но решаемым в квазиполиномиальном времени math.stackexchange.com/questions/2218929/…
Мохаммад Аль-Тюркистани
@ MohammadAl-Turkistany: вы видите недостаток в текущей версии ответа?
Марцио Де
Нет, я не вижу очевидного недостатка.
Мохаммед Аль-Туркистани