Incremental optimization of independent sets under the reconfiguration framework

Nehmen wir an, wir erhalten einen unabhängigen Satz eines Graphen G und eine ganze Zahl. Dann werden wir gebeten, einen unabhängigen Satz G zu finden, der die maximale Größe zwischen unabhängigen Sets aufweist, die entweder durch Addition oder Entfernung eines einzelnen Scheitelpunktes gleichzeitig erreicht werden können, so dass alle unabhängigen Zwischenmengen mindestens von der Größe sind. Wir zeigen, dass dieses Problem selbst für Diagramme mit begrenzter Pfadbreite PSPACE-hart ist und für planare Diagramme NP-hart bleibt. Auf der anderen Seite geben wir einen linearen Zeitalgorithmus zur Lösung des Problems für Akkordgraphen an. Wir untersuchen auch die parametrisierte Komplexität des Problems in Bezug auf die folgenden drei Parameter: die Entartung eines Eingabegraphen, eine niedrigere Grenze auf die Größe unabhängiger Sets und eine niedrigere Grenze auf die Größe einer Lösung, von der aus erreicht werden kann. Wir zeigen, dass das Problem fest parametrisierbar ist, wenn nur einer von, oder als Parameter angenommen wird. Auf der anderen Seite geben wir einen festen Parameteralgorithmus an, wenn dieses Problem anhand von Parametern fixiert wird.