NP-сложные проблемы на пути

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

Я уже нашел связанный вопрос о NP-трудных проблемах на деревьях .

Согласования радуги в краевом цвете графа является соответствием, ребро которого имеет различные цвета. Задача: учитывая ребро цвета графа и целое число K , делает G имеет соответствие с радугой , по крайней мере K ребрами? Это известно как проблема согласования радуги , и ее NP- полнота даже для правильно окрашенных контуров. Авторы даже отмечают, что до этого результата не было известно, что ни одна проблема невзвешенного графа не является NP- трудной для простых путей в меру своих знаний.$G$$k$$G$$k$

См. Ле, Ван Банг и Флориан Пфендер. «Результаты сложности для радужных совпадений». Теоретическая информатика (2013) , или версия arXiv .

Вот несколько простых наблюдений.

• Неокрашенный граф путей в основном кодирует целое число, так что вы можете взять любую сложную задачу NP, включающую унарно-кодированные целые числа, и переосмыслить ее как проблему графа пути. Если вы разрешите несколько целых чисел, закодированных в унарном виде (= непересекающееся объединение графов путей), то вы можете использовать некоторые сильно NP-полные задачи, такие как 3-Partition.

• Цветной граф путей кодирует слово в фиксированном алфавите, поэтому вы снова можете решить сложную задачу со словами. Примером, который мне известен, является проблема Несвязных Факторов, представленная в Bodlaender, Thomassé и Yeo .

MinCC Graph Motif является NP-сложным, когда граф является путем (даже APX-сложным). Учитывая график с цветами на вершинах и набором цветов, найдите подграф, соответствующий набору цветов и минимизирующий количество подключенных комп. См. Проблемы сложности в сопоставлении с образцом вершинного графа, JDA 2011.

Для заданного пути с узлами и взвешенными ребрами 1 ≤ weight ( u , v ) < $n$$1 \leq \text{weight}(u,v) < n$ найдите, можно ли пометить узлы, используя числа в (избегая дублирующих меток) таким образом, чтобы абсолютная разница метки двух соседних узлов равны весу ребра:$[1..n]$

Это эквивалентно проблеме реконструкции перестановок из различий, которая является NPC (один из моих «неофициальных» результатов :-).

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

$f\colon\mathbb{N}^3\to\mathbb{N}$$\langle k,m,w\rangle$$f(k,m,w)$$m$$w$$n^{\log k}$$n$$\log k$$k$ в унарном.) Этот набор значений может быть представлен как набор путей.

Нерасщепляемая проблема потока (UFP) остается NP-трудной на пути. Действительно, UFP является NP-трудным даже на одном ребре, поскольку это эквивалентно проблеме ранца.

Набор Доминирования Радуги (RDS) остается NP-трудным на пути. Для заданного вершинного графа RDS - это DS, где каждый цвет графа появляется хотя бы один раз.

Тропические доминирующие множества в графах вершинного цвета , JDA'18

Доминирующий набор и независимый доминирующий набор являются NP-сложными на путях, если во входных данных также есть «граф конфликтов», где ребро в этом графе представляет собой пару вершин, которые не могут быть обе в решении.

Корнет, Алексис; Laforest, Christian , Доминирование без конфликтов , Discrete Appl. Математика 244, 78-88 (2018). ZBL1387.05181 .