What Makes the Arc-Preserving Subsequence Problem Hard?