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.

cc.complexity-theory graph-theory automorphism symmetry 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