On exact algorithms for the permutation CSP

DOI10.1016/J.TCS.2012.10.035MaRDI QIDQ392031zbMATHOpenAlexFDO

Authors Eun Jung Kim, Daniel Gonçalves

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.2801

zbMATH Keywords

exact algorithmalgorithmic lower boundpermutation constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: In the Permutation Constraint Satisfaction Problem (Permutation CSP) we are given a set of variables $V$ and a set of constraints C, in which constraints are tuples of elements of V. The goal is to find a total ordering of the variables, $pi:Vightarrow[1,\mathrm{...},|V|]$, which satisfies as many constraints as possible. A constraint $(v_1,v_2,\mathrm{...},v_k)$ is satisfied by an ordering $pi$ when $pi(v_1)<pi(v_2)<\mathrm{...}<pi(v_k)$. An instance has arity $k$ if all the constraints involve at most $k$ elements. This problem expresses a variety of permutation problems including {sc Feedback Arc Set} and {sc Betweenness} problems. A naive algorithm, listing all the $n!$ permutations, requires $2^{O(nlogn)}$ time. Interestingly, {sc Permutation CSP} for arity 2 or 3 can be solved by Held-Karp type algorithms in time $O^{\ast }(2^n)$, but no algorithm is known for arity at least 4 with running time significantly better than $2^{O(nlogn)}$. In this paper we resolve the gap by showing that {sc Arity 4 Permutation CSP} cannot be solved in time $2^{o(nlogn)}$ unless ETH fails.

Recommendations

• Finding and counting permutations via CSPs
• Finding and Counting Permutations via CSPs
• A space-time tradeoff for permutation problems
• Time complexity of constraint satisfaction via universal algebra
• Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra

Cites work

• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A note on exact algorithms for vertex ordering problems on graphs
• A space-time tradeoff for permutation problems
• On problems as hard as CNF-SAT
• On the complexity of \(k\)-SAT
• Scheduling partially ordered jobs faster than \(2^{n }\)
• Set partitioning via inclusion-exclusion
• Which problems have strongly exponential complexity?

Cited in

(9)

• Certifying algorithms and relevant properties of reversible primitive permutations with \textsf{Lean}
• Finding and counting permutations via CSPs
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• scientific article; zbMATH DE number 177149 (Why is no real title available?)
• Solving static permutation mastermind using \(O(n \log n)\) queries
• Solving a permutation problem by a fully polynomial-time approximation scheme
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Inclusion relationships among permutation problems
• A space-time tradeoff for permutation problems

This page was built for publication: On exact algorithms for the permutation CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392031)