Parameterized complexity results in symmetry breaking

DOI10.1007/978-3-642-17493-3_3zbMATH1309.68104OpenAlexW3121966620MaRDI QIDQ3058684FDOQ3058684

Authors Toby Walsh

Publication date 7 December 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Abstract: Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is often computationally intractable. This paper argues that recent parameterized complexity results provide insight into that intractability and help identify special cases in which symmetry can be dealt with more tractably

Recommendations

• scientific article; zbMATH DE number 2084699
• Dynamic structural symmetry breaking for constraint satisfaction problems
• Optimal symmetry breaking for graph problems
• On the effectiveness of symmetry breaking
• Symmetry and Satisfiability: An Update

Cites work

• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• Breaking All Value Symmetries in Surjection Problems
• Breaking Symmetry of Interchangeable Variables and Values
• Characterising tractable constraints
• Combining Symmetry Breaking and Global Constraints
• Filtering Algorithms for the NValue Constraint
• Filtering algorithms for the NValue constraint
• General Symmetry Breaking Constraints
• Generating effective symmetry-breaking predicates for search problems
• Handbook of constraint programming.
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Propagation algorithms for lexicographic ordering constraints
• Symmetries of symmetry breaking constraints
• The complexity of resolution with generalized symmetry rules
• Tractable cases of the extended global cardinality constraint
• Tree clustering for constraint networks

Cited in

(4)

• Variable symmetry breaking in numerical constraint problems
• Constraint-directed search for all-interval series
• Bit complexity of breaking and achieving symmetry in chains and rings
• On the effectiveness of symmetry breaking

Describes a project that uses

Uses Software

• CSPLib

This page was built for publication: Parameterized complexity results in symmetry breaking

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