Dies zeigt, dass eine unabhängige Menge der Größe $k$ unter Verwendung des logarithmischen Raums bestimmt werden kann

Question

Eine unabhängige Menge $I$ ist eine Teilmenge der Knoten eines Graphen $G$, wobei:Keine 2 Knoten in $I$ sind in $G$ benachbart.Für die natürliche Zahl $k$ fragt das Problem $k- ext{IND}$, ob es eine unabhängige Menge der Größe $k$ gibt.

Ich würde mich sehr über Ihre Hilfe beim Zeigen freuen, dass $k- ext{IND} \in {\sf L}$, d. h., unter Verwendung des deterministischen logarithmischen Raums entschieden werden kann.

Answer 1

Sie können den folgenden Algorithmus verwenden.

Ich gehe davon aus, dass die Eckpunkte mit $1,\ldots,m$ beschriftet sind.Sie zählen alle $k$-Tuple $\{1,\ldots , m\}^k$ auf.Dies kann durch die Reservierung von $k$-Zählern auf dem TM-Band erfolgen.Da $k$ nicht Teil Ihrer Eingabe ist, benötigt dies nur $O(\log m )\subseteq O(\log n)$ Platz.Sie können jedoch für jedes $k$-Tupel testen, ob es eine unabhängige Menge ist.Testen Sie einfach alle Paare ausgewählter Scheitelpunkte, wenn diese nicht durch eine Kante verbunden sind.Da $k$ wiederum fest ist, sind die Kanten, die Sie testen müssen (abhängig vom aktuellen Tupel), bekannt.Somit kann dieser Test fest in das TM-Programm integriert werden und benötigt daher keinen zusätzlichen Platz.