Parameterized Complexity of MinCSP over the Point Algebra

The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form x < y, x = y, x ≤ y and x neq y, and a budget k. The goal is to check whether it is possible to assign rational values to the variables while breaking constraints of total cost at most k. This problem generalizes several prominent graph separation and transversal problems: MinCSP(<) is equivalent to Directed Feedback Arc Set, MinCSP(<,≤) is equivalent to Directed Subset Feedback Arc Set, MinCSP(=,neq) is equivalent to Edge Multicut, and MinCSP(≤,neq) is equivalent to Directed Symmetric Multicut. Apart from trivial cases, MinCSP(Gamma) for Gamma subseteq <,=,≤,neq is NP-hard even to approximate within any constant factor under the Unique Games Conjecture. Hence, we study parameterized complexity of this problem under a natural parameterization by the solution cost k. We obtain a complete classification: if Gamma subseteq <,=,≤,neq contains both ≤ and neq, then MinCSP(Gamma) is W[1]-hard, otherwise it is fixed-parameter tractable. For the positive cases, we solve MinCSP(<,=,neq), generalizing the FPT results for Directed Feedback Arc Set and Edge Multicut as well as their weighted versions. Our algorithm works by reducing the problem into a Boolean MinCSP, which is in turn solved by flow augmentation. For the lower bounds, we prove that Directed Symmetric Multicut is W[1]-hard, solving an open problem.