Résumé en anglais

In the Permutation Constraint Satisfaction Problem (Permutation CSP) we are given a set of variables V and a set of constraints C, in which constraint s are tuples of elem ent s of V . The goal is to find a total ordering of the variables, π : V → [1, . . . , |V |], which satisfies as m any constraints as possible. A constraint ( v1, v2, . . . , vk) is satisfied by an ordering π when π ( v1) < π ( v2) < . . . < π ( vk) . An instance has arity k if all the constraint s involve at most k elements. This problem expresses a variety of permut at ion problem s including Feedback Arc Set an d Betweenness problems. A naïve algorithm , listing all then! permutation s, requires 2O(n log n) time. Interestingly, Permutation CSP for arity 2 or 3 can be solved by Held - Karptype algorithms in time O ∗ ( 2n) , but no algorithm is known for arity at least 4 with running time significantly better than 2O(n log n). In this paper we resolve the gap by showing that Arity 4 Permutation CSP can not be solved in time 2o(n log n) unless ETH fails.