We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have natural parameters which make them fixed-parameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation.

C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, C.-G. Quimper, T. Walsh (2008). The Parameterized Complexity of Global Constraints. MENLO PARK : AAAI Press.

The Parameterized Complexity of Global Constraints

KIZILTAN, ZEYNEP;
2008

Abstract

We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have natural parameters which make them fixed-parameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation.
2008
Proc. of the 23rd AAAI Conference on Artificial Intelligence
235
240
C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, C.-G. Quimper, T. Walsh (2008). The Parameterized Complexity of Global Constraints. MENLO PARK : AAAI Press.
C. Bessiere; E. Hebrard; B. Hnich; Z. Kiziltan; C.-G. Quimper; T. Walsh
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/63081
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? ND
social impact