Pytanie o liniowe rozszerzenia zamówień częściowych

Jeśli otrzymujesz zbiór zamówień częściowych, sortowanie topologiczne powie ci, czy istnieje rozszerzenie zbioru do zamówienia całkowitego (w tym przypadku rozszerzenie jest zamówieniem całkowitym zgodnym z każdym z zamówień częściowych).

Natknąłem się na odmianę:

Naprawić zestaw . Dostajesz sekwencje elementów narysowanych z bez powtórzeń (sekwencje mają długość od 1 do ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

Czy istnieje sposób na ustalenie orientacji dla każdej sekwencji (do przodu lub do tyłu), aby wynikowy zbiór łańcuchów (postrzegany jako częściowa kolejność) dopuścił rozszerzenie?

Czy ten problem jest dobrze znany?

Uwaga: Orientacja jest wybierana dla całej sekwencji. Więc jeśli sekwencja wynosi , możesz ją zachować lub odwrócić do , ale nie możesz zrobić nic innego. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
źródło

Jeśli każda z sekwencji ma długość

wówczas można pomyśleć o każdej sekwencji jako o nieukierunkowanej krawędzi i pytamy, czy niekierowany wykres może być zorientowany tak, aby był DAG - iff, jeśli nie ma cyklu. Ale działa także chciwy algorytm. Zacznij od krawędzi i ustaw ją dowolnie, idź tak długo, jak to możliwe, a jeśli utkniesz, wiesz, że nie jest to możliwe. Próbowałeś tego dla swojej odmiany? Wygląda na to, że może działać.

2

$2$

Chandra Chekuri

Er, każdy niekierowany wykres może być zorientowany na DAG. Wystarczy wybrać kolejność wierzchołków i użyć tej kolejności, aby zorientować krawędzie.

David Eppstein

Oczywiście masz rację, nie myślę prosto.

Chandra Chekuri

W moim wariancie każda podsekwencja ma długość dokładnie 4, więc odpowiedź Yury się zaczyna. Mam tylko nadzieję, że podsekwencje mają bardzo specjalną strukturę i są ze sobą powiązane, więc może coś konkretnego pomogłoby. Ale nie ma ogólnego młota.

Suresh Venkat

Odpowiedzi:

Jeśli każda sekwencja ma długość 3, problem jest znany jako Pomiędzy . Nawet problem międzypaństwowości jest trudny NP. W tym zadaniu otrzymujemy zestaw wierzchołków i zestaw ograniczeń formy leży między i . Naszym celem jest uporządkowanie wszystkich wierzchołków, aby zmaksymalizować liczbę spełnionych ograniczeń. Opantry [1] udowodnił, że wersja decyzyjna tego problemu jest trudna do NP. Chor i Sudan [2] udowodnili, że jest trudny do SNP. $u$ $v$ $w$

Najbardziej znany algorytm aproksymacji dla problemu Chor i Sudan spełnia 1/2 wszystkich ograniczeń, jeśli instancja jest całkowicie zadowalająca.

[1] J. Opantry. Total Order Order Problem, SIAM Journal on Computing , 8 (1): 111-114, luty 1979.

[2] B. Chor i M. Sudan. Geometryczne podejście do zależności , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, listopad 1998.

Edycje: wyjaśniono, że wersja decyzyjna problemu jest trudna NP.

Yury
źródło

Yury, czy to oznacza, że problem decyzyjny, czy wszystkie ograniczenia mogą być spełnione, jest również trudny?

Chandra Chekuri

Tak, problem decyzyjny jest trudny NP. Co więcej, dla niektórych

NP jest trudne do spełnienia nawet ułamek

wszystkich ograniczeń (tj. Odpowiadający problem obietnicy to NP-trudny).

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

Yury

Jeśli instancja jest nie całkowicie spełnialna , problem jest bardzo trudne: oczywiście można zaspokoić

wszystkich ograniczeń w drodze losowej kolejności; ale UGC-trudno zaspokoić

wszystkich ograniczeń jeśli

każdej stałej

[Charikar, Guruswami, Manokaran - CCC 2009].

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

Yury

moje pytanie może być głupie. ale czy twardość 3-regularna (

dla wszystkich

) naturalnie sięga 4-regularnej?

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

Yixin Cao

Tak, tutaj jest obniżka. Rozważmy 3-regularny instancji

. Wprowadź nową zmienną

dla każdej sekwencji

. Niech

będzie sekwencją uzyskaną przez dodanie

na końcu

. Otrzymujemy 4-regularną instancję

na wierzchołkach

z sekwencjami

. Łatwo jest zauważyć, że

jest spe jeśli

był spełnialna - przyjąć rozwiązanie

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

, umieścić każdy

zarówno wobec wszystkich wierzchołków

lub po wszystkich wierzchołków

, w zależności od orientacji

(względna rzędu

ma znaczenia).

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$

Yury