Zeitkomplexität von Vertexabdeckung gegen Clique für Fixed K

Question

Ich habe zwei Möglichkeiten, ein unabhängiges Set-Problem der festen Größe zu lösen $ K $ für Graph $ g= (V,E) $ :
- Vertex-Abdeckungsalgorithmus, der in $ O ^ * (1.47 ^ {v-k}) $ (optimierter rekursiser Algorithmus) - Clique-Algorithmus, der in $ O ({v \ wähle k}) ausgeführt wirdSpan> und überprüfen Sie den Algorithmus)

Wie kann ich feststellen, welcher eine geringere Zeitkomplexität hat?Ich bin nicht sehr gut mit Algorithmen für NP-komplette Probleme und $ o ^ * $ Notation.Würde diese Funktionen plotten?Ich denke, dass der VC-Algorithmus einen beliebigen Polynom $ n ^ {o (1)} $ als Multiplikation aufgrund der $O ^ * $ Notation und dies könnte die Laufzeiten beeinträchtigen, aber ich bin mir nicht sicher.

Answer 1

für jeden festen $ k $ , $ o (\ binom {v} {k})= o (v^ k) $ ist Polynom, während $ o ^ * (1.47 ^ {vk ^)= o ^ * (1.47 ^ v) $ exponentiell ist.Exponentials wachsen viel schneller als Polynome.

Das Plotten der Kurven ist nicht so hilfreich, da dies asymptotische Aussagen sind.

das heißt, wenn Sie interessiert sind, wenn Sie an teilnehmen $ V $ und $ k$ , dann ist Ihre beste Option, um empirisch zu überprüfen, welcher dieser Algorithmen schneller ist.Asymptotische Notation ist hier nicht hilfreich, da es konstante Faktoren verbirgt, und diese könnten einen großen Unterschied für konkrete Werte von $ V $ und $ k $ .

Answer 2

Vertexabdeckung ist fixierbarer Parameter. Es gibt einen einfachen $ 2 ^ k n $ Algorithmus, um einen VC der Größe $ K $ zu finden. Dies sollte den naiven Algorithmus schlagen. Der aktuelle Stand der Technik ist so etwas wie $ 1.24 ^ k n $ .

Unter einigen Annahmen gibt es keinen Algorithmus für K Clip mit Laufzeit $ F (k) n ^ C $ .

Wenn Ihr Diagramm eine spezielle Struktur hat, können die Ergebnisse verbessert werden.