Annäherung an den nicht-trivialen Graph-Automorphismus?

Der Graphautomorphismus ist eine Permutation von Graphknoten, die eine Bijektion auf der Kantenmenge induziert . Formal ist es eine Permutation von Knoten wie iff $E$ $f$ $(u,v)\in E$ $(f(u),f(v))\in E$

Definieren Sie eine verletzte Kante für eine Permutation als eine Kante, die einer Nichtkante zugeordnet ist, oder eine Kante, deren Vorbild keine Kante ist.

Eingabe : Ein nicht starrer Graph $G(V, E)$

Problem : Suchen Sie eine (Nichtidentitäts-) Permutation, die die Anzahl der verletzten Kanten minimiert.

Wie komplex ist es, eine (Nichtidentitäts-) Permutation mit einer minimalen Anzahl von verletzten Kanten zu finden? Ist das Problem für Graphen mit begrenztem Maximalgrad schwierig (unter einer gewissen Komplexitätsannahme)? Ist es zum Beispiel schwierig für kubische Graphen? $k$

Motivation: Das Problem ist eine Lockerung des Graph Automorphism Problems (GA). Das Eingabediagramm kann einen nicht trivialen Automorphismus aufweisen (z. B. ein nicht starres Diagramm). Wie schwierig ist es, einen ungefähren Automorphismus (Schrankpermutation) zu finden?

Bearbeiten 22. April

Ein starrer (asymmetrischer) Graph hat nur einen trivialen Automorphismus. Ein nicht starrer Graph hat eine gewisse (begrenzte) Symmetrie, und ich möchte die Komplexität der Approximation seiner Symmetrie verstehen.

cc.complexity-theory graph-theory automorphism symmetry Mohammad Al-Turkistany
quelle

Das Problem ist trivial, die Identitätspermutation ist immer optimal.

Jukka Suomela

@Jukka, Im Graph Automorphism Problem suchen wir nach nicht trivialem Automorphism. Ebenso interessiert mich hier die Identitätspermutation nicht.

Mohammad Al-Turkistany

Ich schlage tatsächlich vor, dass Sie möglicherweise die falsche Frage stellen ... Vielleicht würde es helfen, wenn Sie Ihre Motivation oder Bewerbung mitteilen.

Jukka Suomela

Das Problem ist eine Lockerung des Graph Automorphism Problems (GA). Der Eingabediagramm kann einen nicht trivialen Automorphismus aufweisen. Wie schwierig ist es, einen ungefähren Automorphismus (Schrankpermutation) zu finden?

Mohammad Al-Turkistany

Ich verstehe nicht, warum Sie sich auf nicht starre Diagramme beschränken, bei denen der tatsächliche optimale Wert Null ist. In starren Graphen kann der Approximationsfaktor interessanter sein.

Derrick Stolee

Antworten:

Ich verstehe die Motivation nicht sehr gut. Lassen Sie mich jedoch eine Antwort auf eine verwandte Frage geben. In der Eigenschaft Test - Framework, erhalten Sie zwei Graphen gegeben ad und Wunsch zwei Fälle zu unterscheiden , basierend auf Parameter : $G$ $H$ $\epsilon$

$G$ und sind isomorph $H$
Jede Bijektion von nach verursacht Fehler an mindestens Kanten. $G$ $H$ $\epsilon \binom{n}{2}$

Die Komplexitätsmetrik ist die Anzahl der Sonden zu den Adjazenzmatrizen, und das Ziel besteht darin, die beiden Fälle mit hoher Wahrscheinlichkeit unter Verwendung einer sublinearen Anzahl von Sonden zu unterscheiden.

Eldar Fischer und Arie Matsliah ( danke, Arnab ) haben in SODA 2006 ein Papier zu genau diesem Problem. Es stellt zwar keine direkte Verbindung zu Ihrem Problem her, kann jedoch ein Weg zu einer möglichen Problemformulierung sein und sogar nützliche Techniken für Sie bereitstellen.

Suresh Venkat
quelle

In der Tat ist dieses Problem auch interessant.

Mohammad Al-Turkistany

Nur eine Korrektur: Dieses Papier ist mit Arie Matsliah verbunden.

Arnab

Wenn wir und als denselben Graphen betrachten, können wir garantieren, dass bei einer nicht trivialen Permutation weniger als Kollisionen auftreten, indem ein beliebiges Paar von Eckpunkten ausgetauscht wird. Dies ist viel weniger als .

G

$G$

H

$H$

2 n

$2n$

ϵ (\binom{n}{2})

$\epsilon{n\choose 2}$

Derrick Stolee

Ein Ergebnis von Eugene Luks ("Der Isomorphismus von Graphen mit begrenzter Valenz kann in Polynomzeit getestet werden ") zeigt, dass der Graphisomorphismus (oder Automorphismus) für Graphen mit begrenztem Grad in Polynomzeit liegt. Wenn Sie also nach einem (nicht identitätsbezogenen, wie Jukka betonte) Fast-Automorphismus für nicht starre kubische Graphen suchen, können wir den Luks-Algorithmus verwenden und jeden nicht trivialen Automorphismus in den Graphen übernehmen.

Ramprasad
quelle

Ich habe das Papier überflogen und mein Verständnis ist, dass es das GA-Entscheidungsproblem mit begrenztem Grad in der Polynomzeit löst. Meine Frage ist ein Optimierungsproblem. Außerdem können Sie starre Diagramme nicht ausschließen.

Mohammad Al-Turkistany