Edge-contraction problems (Q794164)

Der Artikel stellt einen Beitrag zur Systematisierung der Beweise auf NP- Vollständigkeit dar. Das folgende Kantenkontraktionsproblem für Graphen ohne Schlingen und Mehrfachkanten wird untersucht: \(P_{EC}(\pi):\) Gegeben sei ein einfacher Graph sowie eine ganze Zahl k. Gibt es eine Kantenteilmenge S mit \(| S| =k\), so daß der durch Kontraktion aller Kanten von S entstehende Graph G/S die Eigenschaft \(\pi\) hat? Die Autoren geben einen Beweis für die NP-Vollständigkeit dieses Problems an, der sich auf verschiedene Klassen von Eigenschaften \(\pi\) anwenden läßt. Explizit werden zwei Fälle behandelt: (1) \(\pi\) nichttrivial für zusammenhängende Graphen, hereditär auf Kontraktionen, durch den assoziierten einfachen Graphen bestimmt, ebenso durch die 2-Komponenten des Graphen bestimmt; (2) \(\pi\) nichttrivial für zusammenhängende Graphen, hereditär auf Kontraktionen, für alle Graphen mit höchstens drei Knoten erfüllt, durch die 3- Komponenten des Graphen bestimmt.