Problemy „ukierunkowane”, które są łatwiejsze niż ich wariant „niekierowany”.

28

Prezentowałem wykład na temat sortowania naleśników i wspomniałem, że:

Co skłoniło mnie do myślenia. W pewnym sensie sortowanie „sygnowane” jest „ukierunkowane” - możesz postrzegać znak jako kierunek (i rzeczywiście jest to motywacja z biologii ewolucyjnej). Ale to łatwiejszy problem! Jest to niezwykłe, ponieważ ogólnie (przynajmniej na wykresach) problemy kierowane są trudniejsze (lub przynajmniej tak trudne) jak ich niekierowane odpowiedniki.

Zakładając hojną definicję „ukierunkowanego”, czy są jakieś przykłady ukierunkowanych problemów, które są łatwiejsze niż ich niekierowane odpowiedniki?

ds.algorithms Suresh Venkat
źródło

2

Możesz rozważyć Róg 3SAT (każda klauzula może być reprezentowana jako (A i B)

C) jako klauzule ukierunkowane, ponieważ mogą być postrzegane jako implikacje. Tak więc tutaj ukierunkowana sprawa jest łatwa, podczas gdy niedokierowana 3SAT jest trudna.

\to

$\to$

Mohammad Al-Turkistany,

1

Zastanawiałem się nad podobnym pytaniem dla klasy, której nauczałem (gdzie używaliśmy LP do przybliżenia rozwiązania IP): czy istnieje klasa problemów, w których znalezienie rozwiązania liczb całkowitych było łatwiejsze niż znalezienie racjonalnego rozwiązania

Gopi

17

Zliczanie obwodów Eulera dla grafów ukierunkowanych jest wykonalne w czasie wielomianowym przy użyciu twierdzenia BEST , podczas gdy najwyraźniej ten sam problem dla grafów niekierowanych jest # P-ukończony .

Timothy Sun
źródło

Wszystkie odpowiedzi są świetne, ale jeśli muszę je zaakceptować, dzieje się tak, ponieważ różnica jest duża, a problem bardzo czysty.

Suresh Venkat,

15

$G$ $r$ $G$ $k$ $r$ $k=1$ $k$ $k=2$ $2$

Chandra Chekuri
źródło

13

Być może nie jest to najlepszy przykład, ale rozważ (Directed) Cycle Cover, gdzie zadaniem jest objęcie wszystkich wierzchołków cyklami rozłącznymi (ukierunkowanymi) wierzchołków. W ukierunkowanym przypadku można to zredukować do dwustronnego dopasowania i rozwiązać w czasie wielomianowym. W przypadku nieukierunkowanym problem można sprowadzić do dopasowywania dwudzielnego (i odwrotnie), co jest trudniejszym problemem, ale nadal rozwiązanym w czasie wielomianowym.

Daniel Marks
źródło

10

G

$G$

G

$G$

G

$G$

To zdecydowanie dobry przykład i zgodny z tym, o czym myślałem, kiedy zadałem pytanie.

Suresh Venkat,

2

Zawsze miałem wrażenie, że „problemy z cyklami” są łatwiejsze na ukierunkowanych wykresach. Być może kryje się za tym jakaś zasada, na przykład, że 2 połączone komponenty mają „mniejszą strukturę” niż silnie połączone komponenty („problemy związane z cyklami” = te, które można rozwiązać, patrząc oddzielnie na każdy komponent).

Diego de Estrada,

3

Diego: jeśli skierowany zamknięty spacer przechodzi przez wierzchołek v, wówczas następuje cykl skierowany przez v. Analogiczne stwierdzenie nie jest prawdziwe dla grafów niekierowanych. Tak więc na wykresach ukierunkowanych często możemy myśleć o marszach zamiast cyklach. Spacery są bardziej wytrzymałe i mniej teoretyczne niż wykresy, co może być zaletą. Być może jest to formalne wyjaśnienie twojego wrażenia.

Daniel Marx,

9

Oto problem, który, jak niedawno uświadomiłem sobie, wygląda trudniej na niekierowanych grafach niż na kierowanych.

$m\sqrt{n}\log C$ $m$ $n$ $C$ $n^3, mn\log n$

$m\sqrt{n}\log C$ $n^3, mn\log n$

dziewice
źródło

ale tutaj „twarde” oznacza po prostu w odniesieniu do (wielomianowych) środowisk uruchomieniowych znanych nam algorytmów; może się zdarzyć, że brakuje nam jakiejś techniki

virgi

2

To kolejny interesujący przykład. I psi gratulujemy niesamowitego nowego wyniku.

Suresh Venkat,

1

Dzięki, Suresh! Z innej notatki, właśnie zauważyłem, że ilyaraz miał moją odpowiedź w komentarzu do odpowiedzi Daniela Marksa ... przepraszam za duplikat.

virgi,

Problemy „ukierunkowane”, które są łatwiejsze niż ich wariant „niekierowany”.

Odpowiedzi: