@online{Dabrowski2305.13889,
TITLE = {Parameterized Complexity Classification for Interval Constraints},
AUTHOR = {Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Pilipczuk, Marcin and Sharma, Roohani},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2305.13889},
EPRINT = {2305.13889},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Constraint satisfaction problems form a nicely behaved class of problems that<br>lends itself to complexity classification results. From the point of view of<br>parameterized complexity, a natural task is to classify the parameterized<br>complexity of MinCSP problems parameterized by the number of unsatisfied<br>constraints. In other words, we ask whether we can delete at most $k$<br>constraints, where $k$ is the parameter, to get a satisfiable instance. In this<br>work, we take a step towards classifying the parameterized complexity for an<br>important infinite-domain CSP: Allen's interval algebra (IA). This CSP has<br>closed intervals with rational endpoints as domain values and employs a set $A$<br>of 13 basic comparison relations such as ``precedes'' or ``during'' for<br>relating intervals. IA is a highly influential and well-studied formalism<br>within AI and qualitative reasoning that has numerous applications in, for<br>instance, planning, natural language processing and molecular biology. We<br>provide an FPT vs. W[1]-hard dichotomy for MinCSP$(\Gamma)$ for all $\Gamma<br>\subseteq A$. IA is sometimes extended with unions of the relations in $A$ or<br>first-order definable relations over $A$, but extending our results to these<br>cases would require first solving the parameterized complexity of Directed<br>Symmetric Multicut, which is a notorious open problem. Already in this limited<br>setting, we uncover connections to new variants of graph cut and separation<br>problems. This includes hardness proofs for simultaneous cuts or feedback arc<br>set problems in directed graphs, as well as new tractable cases with algorithms<br>based on the recently introduced flow augmentation technique. Given the<br>intractability of MinCSP$(A)$ in general, we then consider (parameterized)<br>approximation algorithms and present a factor-$2$ fpt-approximation algorithm.<br>},
}