Parameterized complexity results in symmetry breaking

DOI10.1007/978-3-642-17493-3_3zbMATH Open1309.68104arXiv1009.1174OpenAlexW3121966620MaRDI QIDQ3058684FDOQ3058684

Authors: Toby Walsh 

Publication date: 7 December 2010

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

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)