Finding a tree structure in a resolution proof is NP-complete

The resolution tree problem consists of deciding whether a given sequence-like resolution refutation admits a tree structure. This paper shows the NP-completeness of both the resolution tree problem and a natural generalization of the resolution tree problem that does not involve resolution.