Enthalten Diagramme mit einer großen Anzahl von Pfaden eine große Nebenkette?

Definition: Eine " Kette" ist ein Multi-Graph, der aus einem Pfad der Länge durch Duplizieren jeder Kante erhalten wird. $k$ $k$

Beachten Sie, dass die Anzahl der Pfade zwischen zwei Endpunkten einer Kette beträgt $k$ $2^k.$

Frage: Sei ein einfacher Graph auf n Knoten und sei und zwei Knoten von Angenommen, die Anzahl der (einfachen) Pfade von s nach t in ist mindestensIst es dann möglich, eine -Kette aus mit ( und als Endpunkten) durch eine Folge von Löschung und Kontraktion von Kanten zu erhalten? $G$ $s$ $t$ $G.$ $G$ $n^k.$ $\Omega(k)$ $G$ $s$ $t$

Wenn die Antwort positiv ist, ist der zweite Teil der Frage, ob es einen effizienten Algorithmus gibt, um eine so große Kette zu erhalten.

Ich würde mich gleichermaßen über -chain oder für jedes freuen $\sqrt k$ $k^\alpha$ $\alpha >0.$

Ich würde mich über eine teilweise Antwort oder eine Intuition darüber freuen, ob eine solche Vermutung gelten sollte.

Ich hatte dies vor ein paar Tagen auf Mathe-Überlauf gepostet. Jemand schlug vor, es auch hier zu posten.

/mathpro/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor

graph-theory graph-algorithms graph-minor Raghav Kulkarni
quelle

Es kann sinnvoll sein, das rekursive Diamantdiagramm zu überprüfen, um festzustellen, ob es sich um ein Gegenbeispiel handelt. cstheory.stackexchange.com/questions/10169/…

Chandra Chekuri

Das ist eine interessante Grafik. Obwohl es mir scheint, dass dies kein Gegenbeispiel für die " Ketten-Vermutung" ist. Dies kann jedoch für die " -Ketten-Vermutung" sein. Noch nicht sicher.

k^{α}

$k^\alpha$

Ω (k)

$\Omega(k)$

Raghav Kulkarni

Es ist selbst für kein Gegenbeispiel , denn wenn es ein Gegenbeispiel für ist, ist der Grad von höchstens und die Länge des längsten Pfades ist , dann gibt es keine st Pfade, außer dass wir annehmen, dass , der letztere Fall ist wiederum unmöglich (tatsächlich ist n f (k) in diesen Graphen, aber es führt nicht zu Widersprüchen zum Satz, weil dann Exponentialfunktion ist).

Ω (k)

$\Omega(k)$

Ω (k)

$\Omega(k)$

s

$s$

O (k)

$O(k)$

s, t

$s,t$

O (k)

$O(k)$

n^{k}

$n^k$

n = f (k)

$n=f(k)$

f

$f$

Saeed

Ein Gegenbeispiel ist auf MathOverflow veröffentlicht: mathoverflow.net/questions/161451/… Ich bin immer noch der Meinung, dass die "richtige" Änderung der Frage zutreffen kann, zumindest für einige natürliche Diagrammklassen wie planare Diagramme.

Raghav Kulkarni

Eine mögliche Variation ist folgende: Jeder verknüpfte Graph enthält eine Kette, aber dies ist eine sehr offensichtliche Variation.

k

$k$

k

$k$

Saeed

Antworten:

Dies scheint ein FPT-Algorithmus für ein festes . Zunächst können wir nur einen Block betrachten, der enthält . Wenn wir ein Gittermoll haben, das enthält können wir die entsprechende Kette finden. Wie sonst, wie Chekuri et al. gezeigt hat der Graph eine Baumbreite von höchstens wobei $k$ $s,t$ $k\times k$ $s,t$ $O(k^{1/\delta})$ $\delta > 0$ ist eine Konstante. Wir können also die Baumzerlegung des Graphen berechnen und dann prüfen, ob diese Kette existiert oder nicht. Ich bin mir nicht sicher, ob mit der üblichen dynamischen Programmierung auf Graphen mit begrenzter Baumbreite die Kette gefunden werden kann. Auch wenn die Baumbreite nicht begrenzt ist, kann ihr Algorithmus das entsprechende Gitter in Polynomzeit finden.

PS: Beachten Sie, dass ich nicht die Tatsache verwendet habe, dass es st Pfade gibt, möglicherweise durch einen Trick innerhalb dieser Tatsache ist es möglich, einen besseren Algorithmus zu erhalten. $n^k$

Saeed
quelle

Sie sagen also, dass die "größte Kette, die durch Löschen-Kontraktion erhältlich ist", ein fester Parameter ist, der nachvollziehbar ist. Das ist interessant! Dies sagt jedoch nichts über die Existenz einer großen Kette als Folge einer großen Anzahl von Pfaden aus.

Raghav Kulkarni

@RaghavKulkarni, Ja, ich denke schon, ich bin mir jedoch nicht ganz sicher, hängt nur davon ab, ob es möglich ist, ein Problem als MSO_2 zu formulieren oder einen dynamischen Programmieransatz für den Fall einer begrenzten Baumbreite bereitzustellen. Tatsächlich scheint Ihr Problem in der Kategorie der bidimentionalen Probleme zu liegen.

Saeed

Außerdem brauchen wir kein sehr großes Gitter wie

weil wir nur nach einem kleinen Fall suchen, nur nach einem

Pfad, damit die Laufzeit verbessert werden kann (ich denke viel besser und kann sogar in

. Ich meine, wenn so etwas wie poly log k funktioniert, dann ist es sehr schön oder in einem subexponentiellen FPT-Algorithmus.

K \times K

$K\times K$

2^{k}

$2^k$

P

$P$

Saeed

Gegenbeispiele zu oben sind auf MathOverflow veröffentlicht:

/mathpro/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor

/mathpro/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1

Irgendeine "richtige" Änderung der Frage, die immer noch zutrifft?

Raghav Kulkarni
quelle