Przybliżanie nietrywialnego automorfizmu grafów?

Wykres automorfizmem jest permutacją węzłów wykres indukuje bijection na zestawie krawędź $E$ . Formalnie jest to permutacja $f$ węzłów takich jak $(u,v)\in E$ iff $(f(u),f(v))\in E$

Zdefiniuj naruszoną krawędź dla pewnej permutacji jako krawędź odwzorowana na inną niż krawędź lub krawędź, której preimage nie jest krawędzią.

Dane wejściowe : niesztywny wykres $G(V, E)$

Problem : Znajdź permutację (brak tożsamości), która minimalizuje liczbę naruszonych krawędzi.

Jaka jest złożoność znalezienia permutacji (braku tożsamości) przy minimalnej liczbie naruszonych krawędzi? Czy problem jest trudny w przypadku wykresów z ograniczonym maksymalnym stopniem $k$ (przy założeniu pewnej złożoności)? Na przykład, czy jest to trudne dla grafów sześciennych?

Motywacja: Problem polega na złagodzeniu problemu automorfizmu grafów (GA). Wykres wejściowy może mieć nietrywialny automorfizm (np. Wykres sztywny). Jak trudno jest znaleźć przybliżony automorfizm (permutacja w szafie)?

Edytuj 22 kwietnia

Sztywny (asymetryczny) wykres ma jedynie trywialny automorfizm. Niesztywny wykres ma pewną (ograniczoną) symetrię i chciałbym zrozumieć złożoność przybliżenia jego symetrii.

— Mohammad Al-Turkistany
źródło

Problem jest trywialny, permutacja tożsamości jest zawsze optymalna.

— Jukka Suomela,

@Jukka, Na wykresie Problem automorfizmu poszukujemy nietrywialnego automorfizmu. Podobnie tutaj nie jestem zainteresowany permutacją tożsamości.

— Mohammad Al-Turkistany

Właściwie sugeruję, że możesz zadawać złe pytanie ... Być może pomogłoby to, gdybyś powiedział swoją motywację lub podanie.

— Jukka Suomela,

Problem polega na złagodzeniu problemu automorfizmu grafów (GA). Wykres wejściowy może mieć nietrywialny automorfizm. Jak trudno jest znaleźć przybliżony automorfizm (permutacja w szafie)?

— Mohammad Al-Turkistany

Nie rozumiem, dlaczego ograniczacie się do niesztywnych wykresów, gdzie rzeczywista optymalna wartość wynosi zero. Na sztywnych wykresach współczynnik aproksymacji może być bardziej interesujący.

— Derrick Stolee

Odpowiedzi:

$G$ $H$ $\epsilon$

$G$ $H$
$G$ $H$ $\epsilon \binom{n}{2}$

Metryka złożoności to liczba sond do macierzy przylegania, a celem jest rozróżnienie dwóch przypadków z dużym prawdopodobieństwem przy użyciu sublinearnej liczby sond.

Eldar Fischer i Arie Matsliah ( dzięki, arnab ) mają artykuł na temat tego problemu w SODA 2006 . Chociaż nie łączy się bezpośrednio z twoim problemem, może być sposobem na sformułowanie potencjalnego problemu, a nawet może zapewnić przydatne techniki.

— Suresh Venkat
źródło

Rzeczywiście, ten problem jest również interesujący.

— Mohammad Al-Turkistany

Tylko korekta: ten papier jest wspólny z Arie Matsliah.

— arnab

Jeśli uznamy i za ten sam wykres, możemy zagwarantować, że będziemy mieli mniej niż kolizji w nietrywialnej permutacji poprzez zamianę dowolnej pary wierzchołków. To o wiele mniej niż .

G

$G$

H

$H$

2 n

$2n$

ϵ (\binom{n}{2})

$\epsilon{n\choose 2}$

— Derrick Stolee

Wynik Eugene'a Luksa („ Izomorfizm wykresów ograniczonej wartościowości można przetestować w czasie wielomianowym ”) pokazuje, że izomorfizm grafu (lub automorfizm) dla wykresów stopnia ograniczonego jest w czasie wielomianowym. Dlatego jeśli szukasz jakiegoś (nie-tożsamość, jak zauważył Jukka) prawie automorfizmu dla grafów sześciennych, które są niesztywne, możemy użyć algorytmu Luksa i wziąć dowolny nietrywialny automorfizm na wykresie.

— Ramprasad
źródło

Przejrzałem artykuł i rozumiem, że rozwiązuje on problem decyzyjny ograniczonego stopnia GA w czasie wielomianowym. Moje pytanie dotyczy problemu z optymalizacją. Nie można również wykluczyć sztywnych wykresów.

— Mohammad Al-Turkistany