Maximale Anzahl intern vertex-disjunkter ungerader Pfade

18

Sei ein ungerichteter einfacher Graph und sei s , t V ( G ) verschiedene Eckpunkte. Die Länge eines einfachen Pfades sei die Anzahl der Kanten auf dem Pfad. Ich bin daran interessiert, die maximale Größe eines Satzes einfacher st-Pfade so zu berechnen, dass jeder Pfad eine ungerade Länge hat und sich die Scheitelpunktsätze jedes Paares von Pfaden paarweise nur in s und t schneiden. Mit anderen Worten, ich suche nach der maximalen Anzahl von intern vertex-disjunkten ungeraden st-Pfaden. Ich denke, dass dies eine Polynomzeit sein sollte, die durch Matching- oder Flow-basierte Techniken berechenbar ist, aber ich war nicht in der Lage, einen Algorithmus zu finden. Hier ist, was ich über das Problem weiß.Gs,tV(G)

  1. Wir können die Beschränkung auf ungerade Länge durch gerade Länge ersetzen; Dies hat keine wirkliche Auswirkung auf das Problem, da sich eine in die andere umwandelt, wenn wir alle auf s einfallenden Kanten unterteilen.

  2. Wenn die Parität der Pfade nicht eingeschränkt ist, gibt Mengers Theorem die Antwort, die durch Berechnung eines maximalen Flusses erhalten werden kann.

  3. Das Problem der Bestimmung der maximalen Anzahl von Zyklen mit ungerader Länge, die sich paarweise nur bei einem gegebenen Knoten v schneiden, ist in der Polynomzeit durch einen passenden Trick berechenbar: Bilde einen Graphen G 'als die disjunkte Vereinigung von und ( G - N G [ v ] ) , wobei Kanten zwischen zwei Kopien desselben Scheitelpunkts hinzugefügt werden; eine maximale Übereinstimmung in dieser graphischen Darstellung der Größe | V ( G ) | - | N G [ v ] | + k v ist k(Gv)(GNG[v])|V(G)||NG[v]|+k impliziert, dass die maximale Anzahl von ungeraden Zyklen durchvk ; Diese Konstruktion ist im Beweis von Lemma 11 in der ungeraden Variante von Hadwigers Vermutung beschrieben .

  4. Wenn der Graph gerichtet ist, ist das Testen auf das Vorhandensein eines einzelnen geraden st-Pfades bereits NP-vollständig.

  5. Das Papier Das Problem des geraden Weges für Grafiken und Digraphen von Lapaugh und Papadimitriou mag relevant sein, aber leider abonniert unsere Bibliothek das Online-Archiv nicht und wir haben keine Papierkopie.

Alle Einblicke werden sehr geschätzt!

Bart Jansen
quelle
1
Das Papier scheint sehr relevant zu sein. Ich kann es am Montag bekommen, wenn es bis dahin niemand anderes bekommt.
Domotorp
Andras Salamon hat mir bereits eine Kopie geschickt; danke für das Angebot!
Bart Jansen

Antworten:

5

Zunächst ist zu beachten, dass bei einem Graphen , zwei getrennten Eckpunkten s , t V und einer ganzen Zahl k das Problem der Entscheidung, ob es k intern vertex-disjunkte Pfade ungerader Länge zwischen s und t gibt, polynomial ist Entspricht der Entscheidung, ob zwischen s und t k Pfade mit gerader Länge existieren . Die Reduzierung ist einfach. Um von Fall zu Fall zu reduzieren, unterteilen Sie einfach jede Kante neben t . Sei G 'G=(V,E)s,tVkkstksttGsei der Graph erhalten. Dann hat k ungeradzahlige-Länge - Vertex-disjunkte Pfade zwischen s und t iff G ' hat k geradzahlig Länge Vertex-disjunkte Pfade zwischen s und t .GkstGkst

Wenn also eines dieser Probleme NP-vollständig ist, ist es auch das andere. Jetzt Itai, Perl und Shiloach zeigt , dass das Problem der Entscheidung , ob es existiert Vertex-disjunkte Wege mit einer Länge von fünf zwischen s und t NP-vollständig [ Die Komplexität mit Längenbeschränkungen maximal disjunkten Wege zu finden . Networks, Volume 12, Issue 3, pages 277–286, 1982.] Die Reduktion stammt von 3SAT, und in der aufgebauten Grafik haben die ungeraden Längenpfade zwischen s und t alle genau fünf Längen. Daher ist das Vertex-Disjoint Odd Length Paths-Problem in NP-complete ebenso wie die Vertex-Disjoint Even Length Paths.kstst

Hoffe das hilft.

Somnath
quelle
"Daraus ergibt sich die Vertex-disjunkte Odd Länge Paths Problem ist NP-vollständig."
Kris
Vielen Dank für Ihre Einsicht Somnath; Die Reduzierung des Papiers ist sehr relevant. Ich stimme jedoch Ihrer Behauptung nicht zu, dass "in dem erstellten Diagramm die ungeraden Längenpfade zwischen s und t alle genau fünf Längen haben"; Betrachtet man die Beispielgrafik in Abb. 5 auf Seite 282, so ist (s; w1,1; x1,1; c3; -x1,1; y1,1; z1,1; t) ein ungerader st-Pfad von Länge 7. Es scheint jedoch, als ob die Konstruktion verwendet werden kann, um die NP-Vollständigkeit meines Problems zu beweisen; Vielen Dank!
Bart Jansen
6

(Es ist keine Antwort, aber ich kann noch keinen Kommentar abgeben.) Ich denke, die obige Antwort funktioniert nicht, weil sie nicht garantiert, dass die Pfade vertex-disjunkt sind. Ein Pfad könnte u 'und der andere u "in G' verwenden; in G würden sie denselben Scheitelpunkt u verwenden.

Karolina Sołtys
quelle
Dies sollte ein Kommentar zu dieser Antwort sein.
Derrick Stolee
@Derrick: Du brauchst 15 Ruf, um Kommentare hinzuzufügen, die Karolina damals noch nicht hatte.
Charles Stewart
@ Charles: Nitpicking: Es ist 50, nicht 15.
Tsuyoshi Ito
Ach, schade. Fortfahren.
Derrick Stolee