Near Unanimity Constraints Have Bounded Pathwidth Duality

被引：16
作者：
Barto, Libor [1 ]
Kozik, Marcin [2 ]
Willard, Ross [3 ]
机构：
[1] McMaster Univ, Dept Math & Stat, Hamilton, ON L8S 4L8, Canada
[2] Jagiellonian Univ, Theoret Comp Sci Dept, Fac Math & Comp Sci, PL-31007 Krakow, Poland
[3] Univ Waterloo, Pure Math Dept, Waterloo, ON N2L 3G1, Canada
来源：
2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS) | 2012年
基金：
加拿大自然科学与工程研究理事会;
关键词：
constraint satisfaction; polymorphism; near unanimity; pathwidth duality; linear datalog; absorption; SATISFACTION PROBLEMS; COMPLEXITY; WIDTH; GRAPH;
D O I：
10.1109/LICS.2012.24
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that if a finite relational structure has a near unanimity polymorphism, then the constraint satisfaction problem with that structure as its fixed template has bounded pathwidth duality, putting the problem in nondeterministic logspace. This generalizes the analogous result of Dalmau and Krokhin for majority polymorphisms and lends further support to a conjecture suggested by Larose and Tesson.
引用
收藏
页码：125 / 134
页数：10
相关论文
共 33 条
  • [1] Abiteboul S., 1995, Foundations of databases, V8
  • [2] Allender E, 2005, LECT NOTES COMPUT SC, V3618, P71
  • [3] [Anonymous], 1988, PRINCIPLES DATABASE
  • [4] POLYNOMIAL INTERPOLATION AND CHINESE REMAINDER THEOREM FOR ALGEBRAIC SYSTEMS
    BAKER, KA
    PIXLEY, AF
    [J]. MATHEMATISCHE ZEITSCHRIFT, 1975, 143 (02) : 165 - 174
  • [5] Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms
    Barto, Libor
    [J]. CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2013, 65 (01): : 3 - 21
  • [6] ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM
    Barto, Libor
    Kozik, Marcin
    [J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2012, 8 (01)
  • [7] Constraint Satisfaction Problems of Bounded Width
    Barto, Libor
    Kozik, Marcin
    [J]. 2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, : 595 - 603
  • [8] CONGRUENCE DISTRIBUTIVITY IMPLIES BOUNDED WIDTH
    Barto, Libor
    Kozik, Marcin
    [J]. SIAM JOURNAL ON COMPUTING, 2009, 39 (04) : 1531 - 1542
  • [9] Bergman C., 2012, Universal Algebra
  • [10] Bodnarchuk V. G., 1969, Cybernetics, V5, P243, DOI 10.1007/BF01070906
1234