Qualitative reasoning is an important subfeld ofartifcial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., ALLEN’SINTERVAL ALGEBRA, can be solved in 2^{O(n·log n)} time, but single-exponential running times 2^O(n) are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter n (e.g., the number of variables) and a coarsegrained parameter k expected to be relatively small.We introduce the classes FPE and XE of problems solvable in f(k) · 2^O(n), respectively f(k)ⁿ,time, and prove several fundamental properties ofthese classes. We proceed by studying temporal reasoning problems and (1) show that the PARTIALLYORDERED TIME problem of effective width k is solvable in 16^kn time and is thus included in XE, and (2) that the network consistency problem for ALLEN’S INTERVAL ALGEBRA with no intervaloverlapping with more than k others is solvable in (2nk)^2k· 2ⁿ time and is included in FPE. Our multivariate approach is in no way limited to these tospecifc problems and may be a generally useful approach for obtaining single-exponential algorithms.