Trudne problemy NP na ścieżkach

22

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 .

graph-theory np-hardness

— Benzoes
źródło

21

Jeśli zobaczysz to pytanie, powinieneś również uważnie przeczytać zaakceptowaną odpowiedź: „Weź jakikolwiek trudny NP problem związany z supersekwencjami, superstrunami, podciągami itp. Następnie ponownie zinterpretuj ciąg znaków jako wykres ścieżki z etykietą.”

— Saeed

2

Tylko uwaga: jeśli ścieżki nie są oznaczone, są one w oczywisty sposób wysoce ściśliwe, a zwarta reprezentacja jest rozsądnym wyborem (

bitów reprezentuje ścieżkę

węzłów) ... dzięki czemu można również „konwertować” trudne problemy, które nie powodują nie używaj kodowania jednoargumentowego; np suma podzbiór: podany

nieznakowane ścieżki o długości

, czy istnieje ich podzbiór, który można połączyć w celu utworzenia ścieżki o długości

?

\log n

$\log n$

n

$n$

n

$n$

a_{1}, . . ., a_{n}

$a_1,...,a_n$

b

$b$

— Marzio De Biasi

24

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ą , czy ma tęczę pasującą co najmniej 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 .

— Juho
źródło

8

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 .

— Super0
źródło

3

To w zasadzie komentarz @ Saeeda.

— RB

Racja, więc proszę głosować za moją odpowiedzią. Jeśli chodzi o problemy NP-trudne na drzewach, mogę wspomnieć o dobrze znanym problemie z przepustowością; okazało się, że jest to trudne dla hierarchii W w raporcie badawczym Bodlaendera, którego nie mogłem znaleźć w Internecie.

— Super0,

6

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.

— Olf
źródło

5

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

| lab (u) - lab (v) | = weight (u, v)

$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$

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

— Marzio De Biasi
źródło

3

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.

— David Richerby
źródło

3

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.

— Arindam Pal
źródło

3

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

— Olf
źródło

2

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 .

— Olf
źródło