b): Was bedeutet das "feste" k genau?

Question

Hey,

Ist mit dem festen k in Aufgabenteil b gemeint, dass wir nun einen Graphen untersuchen ob dieser genau k Cliquen hat und nicht wie ursprünglich mindestens k? Falls ja, so ist doch k in beiden Fällen fest, wird jedoch nur unterschiedlich interpretiert?

 

Answer 1

Zunächst: k ist die Anzahl der Knoten in der Clique, nicht die Anzahl Cliquen.

Beim Clique-Problem geht es darum, wenn ein Nutzer einen Graph und ein k vorgibt, zu entschieden, ob der Graph eine Clique der Größe k enthält.

In Teil b) ist das Problem vereinfacht, indem der Nutzer nur noch einen Graph eingeben kann, während das k festgelegt ist und vom Nutzer nicht verändert werden kann. Das heißt, ein Verfahren zur Lösung dieses Problems kann auf dieses k optimiert werden. Das ist beim ursprünglichen Clique-Problem nicht möglich.

Gruß,

Tobias (Tutor)

 

Comments

Danke für deine Antwort.

Beim vereinfachten Clique Problem schaut man sich laut Musterlösung alle k elementigen Teilmengen an und multiplizierte die Anzahl jener Teilmengen mit den jeweils k^2 Möglichkeiten der Knoten Kanten zu bilden.

Wenn jetzt nun das k nicht vorgegeben ist, dann muss der Algorithmus doch genau das gleiche leisten? Warum sollte jener Algorithmus NP vollständig sein und der andere in P liegen? Was ist beim orginalen Clique Algorithmus speziell anders im Vorgehen?

---

Wenn man dem Nutzer die Eingabe von k überlässt, kann es passieren, ist k in der Formel für den Aufwand keine Konstante mehr, sondern kann k beliebige Werte k <= n annehmen (k > n macht wenig Sinn...) Also auch z.B. k =  n/2. Setzt man das in die Formel ein, erhält man kein Polynom mehr...

Gruß,

Tobias (Tutor)

Answer 2

Hallo,

die Antwort von Tobias ist vollkommen richtig und zeigt die mathematische Seite, aber vielleicht kann ich noch ein bisschen zum intuitiven Verständnis beitragen.

Wenn wir uns vorstellen, dass konstant k=10 gilt, dann ist es vielleicht ein intuitiv "schwieriges" Problem, in einem Graphen mit vielleicht n=30 Knoten nach einer Clique mit 10 Knoten zu suchen - das ist nicht anders als wenn wir das normale Clique-Problem auf diesen Graphen anwenden und k=10 setzen. Der Unterschied ist aber in der relativen Schwierigkeit, wenn die Knotenzahl n steigt (denn wir betrachten ja normalerweise den ZeitZUWACHS bei steigender Eingabelänge). Wenn wir in einem Graphen mit n=1000 nach einer Clique mit 10 Knoten suchen, dann ist das k verhältnismäßig klein und führt insgesamt zu einem nur polynomiellen Zuwachs der Laufzeit: \( O(n^k \cdot k^2) \). Ist das k nicht konstant, dann kann es mit n wachsen und wir erhalten beispielsweise mit \( k=\frac{n}{2}: O(n^{\frac{n}{2}} \cdot (\frac{n}{2})^2)\), was nicht mehr polynomiell ist.

(Das ist übrigens kein Beweis dafür, dass Clique ein schwieriges Problem ist, sondern nur eine obere Schranke. Sonst würde man ja noch schlimmere Komplexität bekommen, wenn man \(k=n\) oder noch größer setzt, aber stattdessen wird es wieder leichter, wenn sich k der Knotenanzahl n annähert. Will man zeigen, dass Clique schwer ist, muss man eine Reduktion durchführen.)

Viele Grüße

Lukas König