  Constraint satisfaction problems form a nicely behaved class of problems that
lends itself to complexity classification results. From the point of view of
parameterized complexity, a natural task is to classify the parameterized
complexity of MinCSP problems parameterized by the number of unsatisfied
constraints. In other words, we ask whether we can delete at most $k$
constraints, where $k$ is the parameter, to get a satisfiable instance. In this
work, we take a step towards classifying the parameterized complexity for an
important infinite-domain CSP: Allen's interval algebra (IA). This CSP has
closed intervals with rational endpoints as domain values and employs a set $A$
of 13 basic comparison relations such as ``precedes'' or ``during'' for
relating intervals. IA is a highly influential and well-studied formalism
within AI and qualitative reasoning that has numerous applications in, for
instance, planning, natural language processing and molecular biology. We
provide an FPT vs. W[1]-hard dichotomy for MinCSP$(\Gamma)$ for all $\Gamma
\subseteq A$. IA is sometimes extended with unions of the relations in $A$ or
first-order definable relations over $A$, but extending our results to these
cases would require first solving the parameterized complexity of Directed
Symmetric Multicut, which is a notorious open problem. Already in this limited
setting, we uncover connections to new variants of graph cut and separation
problems. This includes hardness proofs for simultaneous cuts or feedback arc
set problems in directed graphs, as well as new tractable cases with algorithms
based on the recently introduced flow augmentation technique. Given the
intractability of MinCSP$(A)$ in general, we then consider (parameterized)
approximation algorithms and present a factor-$2$ fpt-approximation algorithm.
