Konnektivität von Graphen durch Kanten- und Scheitelpunktentfernung

Nehmen wir an, ein Graph ist -verbunden, wenn die Entfernung von Eckpunkten und Kanten von immer einen zusammenhängenden Graphen hinterlässt. Zum Beispiel ist ein verbundener Graph gemäß der Standarddefinition -verbunden gemäß der neuen Definition. Gibt es einen Polynomialzeit-Algorithmus , um zu entscheiden , ob ist zu? Hier betrachte ich die Eingabe als , und $G$ $(a,b)$ $a$ $b$ $G$ $k$ $(k-1,0)$ $G$ $(a,b)$ $G$ $a$ . $b$

ds.algorithms graph-theory graph-algorithms jemand
quelle

Hausaufgaben Problem?

Chandra Chekuri

Ich bin auf diese Frage während eines Gesprächs von Janez Zerovnik über die Konnektivität von Netzwerken über 2/3 Jahre gekommen. Um ehrlich zu sein, erinnere ich mich nicht an die Details. Seitdem habe ich 4 Forscher befragt und niemand hat gesehen, wie man es auf Vertex-Konnektivität (oder Edge-Konnektivität) reduziert, was der naheliegende Ansatz wäre. Außerdem konnte niemand auf einen Satz vom Menger-Typ hinweisen. Also ja, ich denke, dass dies eine Frage auf Forschungsebene ist, möglicherweise mit einer einfachen Antwort oder nicht.

Jemand

Ich weiß nicht, warum die Leute manchmal annehmen, eine Frage sei eine Hausaufgabe, ohne vorher darüber nachzudenken. Ich denke, Sie sollten keine Hausaufgaben machen, es sei denn, Sie wissen, wie man es löst.

Domotorp

@domotorp: Die Leute fragen normalerweise, ob es sich um eine Hausaufgabe handelt, und erheben keinen Anspruch darauf. Es ist schwer zu beurteilen , ob eine Frage homework- ist Ebene oder nicht , wenn die Frage nicht , Hintergrund / Motivation enthält.

Kaveh

Ich verstehe, dass meine Frage aus mehreren Gründen als Hausaufgabe missverstanden werden könnte, aber jetzt sollten wir weitermachen. Eigentlich habe ich mit dem Kommentar von Chandra Chekuri einige Hoffnung bekommen, dass die Frage vielleicht eine einfache Antwort haben könnte ...

jemand

Dies ist eine bearbeitete Version einer früheren "Antwort", die fälschlicherweise einen Polynom-Zeit-Algorithmus für das Problem beanspruchte. Was ich unten schreibe, ist eine Verbindung zu einem bestehenden Problem, was darauf hindeutet, dass das Problem schwierig ist.

$s,t$ $G$ $(a,b)$ $a$ $b$ $s$ $t$ $s$ $t$ $b$ $c(e)$ $s$ $t$ $b$ $b$

Zwei Artikel, die in der kommenden SODA 2012 erscheinen werden, befassen sich mit Mehrwegeschnitten, die weitere Ergebnisse zu diesem Thema liefern. Die von Chuzhoy et al. Hat für einige Varianten Härteergebnisse.

Chandra Chekuri
quelle

Das Papier von Chuzhoy et al ist jetzt auf der ArXiv-Website verfügbar: arxiv.org/abs/1112.3611

Chandra Chekuri,

Konnektivität von Graphen durch Kanten- und Scheitelpunktentfernung

Antworten: