Symmetry Breaking in Subgraph Pattern Matching
(2006) Sixth International Workshop on Symmetry in Constraint Satisfaction Problems (SymCon′06) — Location: Nantes, France (25.September.2002)
Files
hermes2007_symmetry.pdf
Open Access - Adobe PDF
- 121.99 KB
Details
- Authors
- Abstract
- A symmetry in a Constraint Satisfaction Problem (CSP) is a bijective function that preserves CSP structure and solutions. Symmetries are important because they induce symmetric subtrees in the search tree. If the instance has no solution, failure has to be proved for equivalent subtrees regarding symmetries. If the instance has solutions, many symmetric solutions will have to be enumerated in symmetric subtrees. The detection and breaking of symmetries can thus speed up the solving of a CSP. Sym- metries arise naturally in graphs as automorphisms. However, although a lot of graph problems have been tackled [BEL 05] [CAM 04] [SEL 03] and a computation domain for graphs has been defined [DOO 05], and despite the fact that symmetries and graphs are related, little has been done to investigate the use of symmetry breaking for graph problems in constraint programming. This work aims at applying and extending symmetry techniques for subgraph matching. We show how to detect and handle global variable and value symmetries as well as local value symmetries
- Affiliations
Citations
Zampelli, S., Deville, Y., & Dupont, P. (2006). Symmetry Breaking in Subgraph Pattern Matching. In Frédéric Benhamou,Narendra Jussien, Barry O’Sullivan (ed.), Trends in Constraint Programming (p. p. 203-218). Wiley. https://hdl.handle.net/2078.5/254159