REVIEW 1 cited by
Reconfiguring Independent Sets in Cographs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Two independent sets of a graph are adjacent if they differ on exactly one vertex (i.e. we can transform one into the other by adding or deleting a vertex). Let $k$ be an integer. We consider the reconfiguration graph $TAR_k(G)$ on the set of independent sets of size at least $k$ in a graph $G$, with the above notion of adjacency. Here we provide a cubic-time algorithm to decide whether $TAR_k(G)$ is connected when $G$ is a cograph, thus solving an open question of~[Bonsma 2014]. As a by-product, we also describe a linear-time algorithm which decides whether two elements of $TAR_k(G)$ are in the same connected component.
Forward citations
Cited by 1 Pith paper
-
Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration
Maxmin q-CSP Reconfiguration is PSPACE-hard to approximate within 1/2^{q-1}+ε, while a (1/2^{q-1}-ε)-factor is in NP under perfect completeness, optimally under NP≠PSPACE.
Discussion (0). Continue with ORCID to comment.