  In this paper, we introduce a new class of parameterized problems, which we
call XALP: the class of all parameterized problems that can be solved in
$f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing
Machine with access to an auxiliary stack (with only top element lookup
allowed). Various natural problems on `tree-structured graphs' are complete for
this class: we show that List Colouring and All-or-Nothing Flow parameterized
by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set
parameterized by treewidth divided by $\log n$, and Max Cut parameterized by
cliquewidth are also XALP-complete.
  Besides finding a `natural home' for these problems, we also pave the road
for future reductions. We give a number of equivalent characterisations of the
class XALP, e.g., XALP is the class of problems solvable by an Alternating
Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use
$f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted
CNF-Satisfiability and Multicolour Clique that are XALP-complete.
