Trudne problemy NP na ścieżkach

wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów?

Znalazłem już powiązane pytanie dotyczące trudnych NP problemów na drzewach .

Dopasowanie tęczowy na wykresie krawędzi kolorze jest dopasowanie, którego krawędzie mają różne kolory. Problemem jest: biorąc pod uwagę wykres kolorze krawędzi i liczbę całkowitą k , czy G ma tęczę pasującą co najmniej k krawędzi? Jest to znane jako problem z dopasowywaniem tęczy , a jego NP jest kompletny nawet dla ścieżek o odpowiednim kolorze krawędzi. Autorzy zauważają nawet, że przed tym wynikiem nie wiadomo, że żaden nieważony problem graficzny nie jest NP- twardy dla prostych ścieżek do najlepszej wiedzy.$G$$k$$G$$k$

Zobacz Le, Van Bang i Florian Pfender. „Wyniki złożoności dla dopasowań tęczy”. Theoretical Computer Science (2013) lub wersja arXiv .

Oto kilka prostych spostrzeżeń.

• Bezbarwny wykres ścieżki zasadniczo koduje liczbę całkowitą, więc możesz wziąć każdy trudny NP problem związany z niezakodowanymi liczbami całkowitymi i ponownie zinterpretować go jako problem wykresu ścieżki. Jeśli zezwolisz na wiele liczb całkowitych zakodowanych w unarnym (= rozłącznym związku grafów ścieżkowych), możesz użyć pewnych silnie uzupełniających NP problemów, takich jak 3-partycja.

• Kolorowy wykres ścieżki koduje słowo na stałym alfabecie, więc ponownie możesz podjąć trudny problem NP na słowach. Przykładem, który jestem świadomy, jest problem Disjoint Factors wprowadzony w Bodlaender, Thomassé i Yeo .

Motyw graficzny MinCC jest trudny NP, gdy wykres jest ścieżką (nawet trudny APX). Biorąc pod uwagę wykres z kolorami na wierzchołkach i zestawem kolorów, znajdź wykres podrzędny pasujący do zestawu kolorów i minimalizujący liczbę podłączonych komp. Zobacz Problemy ze złożonością w dopasowywaniu wzorca wykresu w kolorze wierzchołka, JDA 2011.

$n$$1 \leq \text{weight}(u,v) < n$$[1..n]$

Jest to równoważne z problemem Permutation Reconstruction from Differences, którym jest NPC (jeden z moich „nieoficjalnych” wyników :-).

Trywialna odpowiedź, która jest zbliżona do niektórych z powyższego, ale wydaje mi się, że jest wyraźna.

$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$ in unary.) Ten zestaw wartości można przedstawić jako zbiór ścieżek.

Problem braku przepływu (UFP) pozostaje trudny do pokonania na drodze. Rzeczywiście, UFP jest twardy NP nawet na pojedynczej krawędzi, ponieważ jest równoważny problemowi z plecakiem.

Rainbow Dominating Set (RDS) pozostaje trudny do pokonania na ścieżkach. Biorąc pod uwagę wykres w kolorze wierzchołka, RDS to DS, w którym każdy kolor wykresu pojawia się co najmniej raz.

Tropikalne zestawy dominujące na wykresach w kolorze wierzchołków , JDA'18

Zestaw dominujący i niezależny zestaw dominujący są NP-trudne na ścieżkach, jeśli na wejściu znajduje się również „wykres konfliktu”, w którym krawędź na tym wykresie jest parą wierzchołków, których nie może być jedno i drugie w rozwiązaniu.

Cornet, Alexis; Laforest, Christian , Problemy z dominacją bez konfliktów , dyskretna aplikacja. Matematyka 244,78–88 (2018). ZBL1387.05181 .