Złożoność sortowania topologicznego z ograniczonymi pozycjami

Ja jako dane wyjściowe DAG z n wierzchołków gdzie każdy wierzchołek x dodatkowo znakowane pewnym S ( x ) ⊆ { 1 , ... , N } .$G$$n$$x$$S(x) \subseteq \{1, \ldots, n\}$

Topologicznym rodzajem jest bijection f z wierzchołków G do { 1 , … , n } taki, że dla wszystkich x , y , jeśli istnieje ścieżka od x do y w G, to f ( x ) ≤ f ( y ) . Chciałbym zdecydować, czy istnieje topologiczny rodzaj G taki, że dla wszystkich x , f ( x ) ∈ S ( $G$$f$$G$$\{1, \ldots, n\}$$x$$y$$x$$y$$G$$f(x) \leq f(y)$$G$$x$ .$f(x) \in S(x)$

Jaka jest złożoność tego problemu decyzyjnego?

[Uwagi: Oczywiście jest to w NP. Jeśli spojrzysz na wykres dozwolonych par wierzchołków / pozycji, z nieukierunkowanymi krawędziami między parami, które kolidują ze sobą, ponieważ naruszają porządek, otrzymasz wykres rozłącznych klików, w których chcesz wybrać maksymalnie jedną parę na klikę, maksymalnie jedną parę na pozycja i co najwyżej jedna para na wierzchołek - wydaje się to związane z dopasowaniem trójwymiarowym, ale nie widzę, czy nadal jest to trudne z dodatkową strukturą tego konkretnego problemu.]

Myślę, że ten problem jest trudny NP. Próbuję naszkicować redukcję z MinSAT. W przypadku problemu MinSAT otrzymujemy CNF, a naszym celem jest zminimalizowanie liczby spełnionych klauzul. Ten problem jest trudny NP, patrz np. Http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Podziel wierzchołki na dwie grupy - niektóre będą reprezentować literały, inne klauzule, więc gdzie v jest liczbą zmiennych CNF (zwykle oznaczoną przez n ), a c jest liczbą klauzul. Kieruj krawędź z każdego dosłownego wierzchołka do klauzuli-wierzchołka, w której występuje. Zdefiniuj S dla dosłownego wierzchołka reprezentującego x i jako { i , i + v + k } (gdzie k jest dowolnym parametrem), więc albo f ( x i$n=2v+c$$v$$n$$c$$S$$x_i$$\{i,i+v+k\}$$k$ oraz f + k + 1 , $f(x_i)=i$ lub f ( ˉ x i ) = i oraz f ( x i ) = i + v + k . Dla każdego wierzchołka zdania niech S = { v + 1 , … , v + k , 2 v , n $f(\bar x_i)=i+v+k$$f(\bar x_i)=i$$f(x_i)=i+v+k$$S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$ , więc wierzchołków klauzul jest `` małe ''.$k$

Teraz CNF ma przypisanie, w którym co najmniej klauzul jest fałszywych wtedy i tylko wtedy, gdy problem można rozwiązać dla powyższej instancji. Problem MinSAT polega właśnie na sprawdzeniu, czy formuła CNF φ ma przypisanie, które powoduje, że co najmniej klauzule k są fałszywe, więc pokazuje to, że twój problem jest trudny NP.$k$$\varphi$$k$

Aby pomóc ci zrozumieć tę redukcję, oto intuicja: małe etykiety ( ) odpowiadają wartości prawdy Fałsz, a duże etykiety ( v + k + 1 , … , 2 v + k ) odpowiadają Prawdziwe. Ograniczenia dla dosłownych wierzchołków zapewniają, że każdy x i ma wartość Prawda lub Fałsz oraz że ¯ x $1,2,\dots,v+k$$v+k+1,\dots,2v+k$$x_i$$\overline{x_i}$ma przeciwną wartość prawdy. Krawędzie zapewniają, że jeśli dowolny literał ma wartość PRAWDA, wówczas wszystkie zawierające go wierzchołki klauzul mają również wartość PRAWDA. (W przeciwieństwie do tego, jeśli wszystkie literały w klauzuli mają wartość False, wówczas ta struktura graficzna pozwala na przypisanie wierzchołka klauzuli albo False, albo True.) Na koniec, wybór zapewnia, że k wierzchołków klauzuli ma False i c - k z nich ma przypisane True. Tak więc, jeśli istnieje ważny rodzaj topologiczną z tego wykresu, to nie jest zadanie dla zmiennych sprawia, że co najmniej k klauzul $k$$k$$c-k$$k$$\varphi$false (wszystkie z wierzchołków klauzul, którym przypisano wartość False, oraz ewentualnie niektóre z tych, którym przypisano wartość True). I odwrotnie, jeśli jest przypisanie do zmiennych sprawia, że co najmniej klauzul cp fałszywe, to nie jest ważny rodzaj topologiczna tego wykresu (wypełniamy etykiet dla dosłownych-wierzchołków w oczywisty sposób, a dla każda klauzula cp to prawda, dajemy jej odpowiednia klauzula-Vertex etykietę, która odpowiada true; pozostałe wierzchołki-klauzuli może otrzymać etykiety odpowiadające dowolnej wartości logicznej).$k$$\varphi$$\varphi$

Zauważ, że jeśli złagodzisz problem, pozwalając być arbitralnym (niekoniecznie dwuskładnikowym), wówczas staje się wielomianowy. Algorytm przebiega podobnie do sortowania topologicznego: numerujesz wierzchołki jeden po drugim, zachowując zbiór U nienumerowanych wierzchołków, których sąsiadów zostały ponumerowane. O ile to możliwe, wybierasz wierzchołek x ∈ U i numerujesz go najmniejszym elementem S ( x ) większym niż liczba jego sąsiadów. Nietrudno dostrzec, że instancja ( G , S ) ma rozwiązanie w stosunku do poprzedniego algorytmu uruchomionego na ( G $f$$U$$x \in U$$S(x)$$(G,S)$$(G,S)$

Trywialna obserwacja jest taka, że ​​jeśli $|S(x)| \le 2$ dla wszystkich $x$, then this problem is solvable in polynomial time, by reduction to 2SAT.

Oto jak. Wprowadź zmienną$v_{x,i}$ dla każdego wierzchołka $x$ i każdy $i$ takie, że $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, and $i>j$, then we get the constraint $\neg v_{x,i} \lor \neg v_{y,j}$. Bijectivity gives us another set of constraints: for each pair $x,y$ of vertices with $x\ne y$, if $i \in S(x)$ and $i \in S(y)$, we add $\neg v_{x,i} \lor \neg v_{y,i}$. Finally, the requirement that each vertex must be assigned a label gives us yet another set of constraints: for each $x$, if $S(x)=\{i,j\}$, we get the constraint $v_{x,i} \lor v_{x,j}$. (Note that only the last set of constraints exploit the promise that $|S(x)|\le 2$ for each $x$.)

I realize this observation won't help you in your particular situation. Sorry about that.