Crossing Number is NP-hard for Constant Path-width (and Tree-width).

Petr Hlinený Liana Khazaliya

Published in: CoRR (2024)

Keyphrases

np hard
computational complexity

special case
tree width

video sequences
lower bound

worst case
structural properties