unabhängige Sätze zählen

8

Welche Algorithmen / mathematischen Techniken stehen zur Verfügung, um die Anzahl unabhängiger Mengen genau / ungefähr zu zählen?

Gibt / gibt es eine gute Referenz / gute Referenzen zu diesem Thema?

Ich interessiere mich für regelmäßige Grafiken.

ds.algorithms reference-request graph-theory approximation-algorithms counting-complexity vs.
quelle

1

Das Googeln "Zählen unabhängiger Sätze regulärer Graphen" ergibt dieses kürzlich erschienene Papier als drittes Ergebnis, das eine Obergrenze ergibt.

Anthony Labarre

7

Das Problem kann als # 2SAT angepasst werden. Sehen

http://en.wikipedia.org/wiki/2-satisfiability

Im Abschnitt "Zählen der Anzahl zufriedenstellender Zuweisungen" finden Sie einige Verweise auf die derzeit besten exakten Zählalgorithmen.

Andreas Björklund
quelle

Ich sehe die direkte Verbindung zu unabhängigen Mengen in diesem Abschnitt nicht, obwohl sie in einem späteren Abschnitt einen Verweis auf bisplit-Diagramme enthalten (Diagramme, die in ein unabhängiges Set und ein vollständiges Diagramm unterteilt werden können). Ich glaube nicht, dass ich das suche !! Vermisse ich eine Verbindung?

gegen

5

@vs wie wäre es: für haben Sie für jedes die Variable und für jedes

haben Sie die Klausel

. Alle auf true gesetzten Variablen entsprechen einer unabhängigen Menge.

G = (V, E)

$G = (V, E)$

u \in V

$u \in V$

x_{u}

$x_u$

(u, v) \in E

$(u, v) \in E$

\neg x_{u} \lor \neg x_{v}

$\neg x_u \vee \neg x_v$

Sasho Nikolov

Gibt es eine ähnliche Technik zum Färben?

gegen

@vs Ja, gleiche Konstruktion mit einer größeren Domain.

Tyson Williams

5

Für die ungefähre Zählung das folgende Papier (auch in CA.-RANDOM 2011)

http://arxiv.org/abs/1105.5131

beschreibt den Stand der Technik.

Wie Anthony Labarre in einem Kommentar oben erwähnt, gab es kürzlich einen unerwarteten Durchbruch von Yufei Zhao, der eine enge Obergrenze für die Anzahl unabhängiger Mengen in einem Vertex- regulären Diagramm zeigte. Sein Beweis verwendete eine sehr kluge Bijektion. Das extreme Beispiel, das von Alon und Kahn vermutet wird und aus dem Jahr 1991 stammt, ist einfach eine disjunkte Vereinigung vieler Kopien eines regulären vollständigen zweigeteilten Graphen. $n$ $d$ $d$

Dieses Forschungsgebiet stützt sich auf viele mathematische und algorithmische Methoden und ist nicht nur für theoretische Informatiker von Interesse, sondern auch für Zahlentheoretiker, Probabilisten, Kombinatoriker, statistische Physiker und mehr. Diese beiden jüngsten Veröffentlichungen geben Ihnen vielleicht einen guten Anfang, obwohl es eine reiche Sammlung von tiefen und interessanten Veröffentlichungen zu diesem Thema gibt, die Jahrzehnte zurückreichen.

RJK
quelle

4

Als Ergänzung zur Antwort von @RJK gibt es seit gestern einen neuen "Stand der Technik".

Sly und Sun Show

Satz 1. Für und $d \ge 3$ $\lambda > \lambda_c(d) = \frac{(d−1)^{d-1}}{(d-2)^d}$ $\lambda$ $d$

$\lambda < \lambda_c(d)$

$\lambda = \lambda_c(d)$

Tyson Williams
quelle

Wissen Sie, ob diese Ergebnisse für Diagramme mit einer bestimmten Struktur gelten, z. B. für starke, schwache (usw.) Produkte, deren zugrunde liegendes Diagramm weniger als 3 beträgt und deren Lambda-Wert unter dem oben genannten Wert liegt?

gegen

@v Diese Grafiken sind regelmäßig?

Tyson Williams

Ja. Aber implizieren die Ergebnisse für alle regulären Diagramme ohne Einschränkung? (Ich denke etwas Analoges dazu - wir wissen, dass es NP schwierig ist, einen linearen Code mit ML zu decodieren. Es ist jedoch sehr schwierig, bestimmte nicht triviale Codes wie RS-Codes anzuzeigen, und es ist auch bekannt, dass es Codes gibt, bei denen ML decodiert wird ist einfach) Natürlich sieht es so aus, als ob das Ergebnis hier für alle regulären Diagramme gilt. Aber es gibt Fälle, in denen die Symmetrie des Diagramms ebenfalls hilfreich sein kann und ich sehe nicht, dass diese Diagramme (im Papier) eine Symmetrie haben überhaupt!!

gegen

1

d

$d$

unabhängige Sätze zählen

Antworten: