Preprint
Aug 2026
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
It is shown that Pattern Avoidance is $\Sigma_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$.
Thomas Depian, S. D. Fink, Alexander Firbas et al.
· 0 citations