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

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

Вход :

• гамильтонов путьв К п$H$$K_n$
• $R \subseteq [n]^2$ подмножество пар вершин
• положительное целое число $k$

Запрос : существует ли сопоставление $M$ такое, что для каждого $(v,u) \in R$ , $d_G(v,u) \leq k$ ?
(где $G = ([n], M\cup H)$ )

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

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

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

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

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

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

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

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

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

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

На следующем рисунке изображено: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

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

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

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

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

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

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

$K$$C_j$$S$

$C$

$P$