A Note on Directed Clique Token Sliding
TL;DR
It is shown that the problem is PSPACE -complete on oriented graphs, NP -complete on directed acyclic graphs (DAGs), and W -hard on DAGs when parameterized by k, and the NP -completeness of the bounded-length variant on DAGs is proved.
Abstract
A directed clique token sliding (TS) step in an oriented graph D replaces a vertex u of a k -clique of the underlying graph U ( D ) by an out-neighbor v of u , while requiring the new set to remain a k -clique of U ( D ) . The reachability problem generated by this directed move is studied. As far as the author knows, the combination of clique feasibility with direction-constrained TS moves has not been studied before. It is shown that the problem is PSPACE -complete on oriented graphs, NP -complete on directed acyclic graphs (DAGs), and W [1] -hard on DAGs when parameterized by k . The NP -completeness of the bounded-length variant on DAGs is also proved. On the positive side, an explicit polynomial-time reachability criterion for tournaments is derived by specializing known structural results on token digraphs, and polynomial-time algorithms are given for transitive oriented graphs, DAGs of any fixed depth, and oriented graphs D for which ω ( U ( D )) is bounded by a fixed constant.