# On the Algebraic Structure of Combinatorial Problems

@article{Jeavons1998OnTA, title={On the Algebraic Structure of Combinatorial Problems}, author={Peter Jeavons}, journal={Theor. Comput. Sci.}, year={1998}, volume={200}, pages={185-204} }

Abstract We describe a general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of… Expand

#### Topics from this paper

#### 375 Citations

Constraints and universal algebra

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2004

It is shown that a constraint satisfaction problem instance can be viewed as a pair of relational structures, and the solutions to the problem are then the structure preserving mappings between these two relational structures. Expand

Constraint Satisfaction Problems and Finite Algebras

- Mathematics, Computer Science
- ICALP
- 2000

It is shown that any restricted set of constraint types can be associated with a finite universal algebra and the result is a dichotomy theorem which significantly generalises Schaefer's dichotomy for the Generalised Satisfiability problem. Expand

An Algebraic Theory of Complexity for Discrete Optimization

- Mathematics, Computer Science
- SIAM J. Comput.
- 2013

It is shown that the complexity of a finite-domain discrete optimization problem is determined by certain algebraic properties of the objective function, which are called weighted polymorphisms, and this approach is used to derive a complete classification of complexity for the Boolean case. Expand

An Algebraic Approach to Multi-sorted Constraints

- Computer Science
- CP
- 2003

A new algebraic framework is described which allows us to deal more precisely with problems where different variables may have different domains, and is able to identify new tractable classes of constraints by combining algorithms devised for the simplified, single domain, problem. Expand

Bounded Tree-Width and CSP-Related Problems

- Mathematics, Computer Science
- ISAAC
- 2007

It is proved, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. Expand

Classifying the Complexity of Constraints Using Finite Algebras

- Mathematics, Computer Science
- SIAM J. Comput.
- 2005

It is shown that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra is explored. Expand

On the Computational Complexity of Monotone Constraint Satisfaction Problems

- Mathematics, Computer Science
- WALCOM
- 2009

A dichotomy theorem is shown for every finite domain of csp, allowing us to classify monotone csp s as tractable or NP-complete, and it is proved that the meta-problem, verifying the tractability condition for monot one constraint satisfaction problems, is fixed-parameter tractable. Expand

A Proof of CSP Dichotomy Conjecture

- Computer Science, Mathematics
- 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
- 2017

An algorithm is presented that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. Expand

The Complexity of Constraint Satisfaction Problems ∗

- 2001

The tractability conjecture for constraint satisfaction problems (CSPs) describes the constraint languages over a finite domain whose CSP can be solved in polynomial-time. The precise formulation of… Expand

Gap theorems for robust satisfiability: Boolean CSPs and beyond

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2017

A Gap Trichotomy Theorem is established for a family of constraint problem variants, completely classifying the complexity of possible NP -hard gaps in the case of Boolean domains and develops aspects of the algebraic approach in the context of a number of variants of the constraint satisfaction problem. Expand

#### References

SHOWING 1-10 OF 29 REFERENCES

On binary constraint problems

- Computer Science, Mathematics
- JACM
- 1994

The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski, and a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time is given. Expand

A Unifying Framework for Tractable Constraints

- Computer Science
- CP
- 1995

All known classes with this property may be characterized by a simple algebraic closure condition, and this condition provides a uniform test to establish whether a given set of constraints falls into any of the known tractable classes, and may therefore be solved efficiently. Expand

An Algebraic Characterization of Tractable Constraints

- Mathematics, Computer Science
- COCOON
- 1995

A simple algebraic closure condition is described, and it is shown that this is both necessary and sufficient to ensure tractability in Boolean valued problems. Expand

Characterising Tractable Constraints

- Mathematics, Computer Science
- Artif. Intell.
- 1994

A set of constraints is identified which gives rise to a class of tractable problems and given polynomial time algorithms for solving such problems, and it is proved that the class of problems generated by any set of constraint not contained in this restricted set is NP-complete. Expand

The complexity of satisfiability problems

- Computer Science, Mathematics
- STOC
- 1978

An infinite class of satisfiability problems is considered which contains these two particular problems as special cases, and it is shown that every member of this class is either polynomial-time decidable or NP-complete. Expand

Fast Parallel Constraint Satisfaction

- Mathematics, Computer Science
- ICALP
- 1993

It is shown here that a CSP with this type of constraint relations (and no restrictions on its graph) can be solved by an efficient (i.e., with polynomial time complexity) sequential algorithm. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

Networks of constraints: Fundamental properties and applications to picture processing

- Computer Science
- Inf. Sci.
- 1974

Constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network, and this solution is proved exact in special cases, e.g., for tree-like and series-parallel networks and for classes of relations for which a distributive property holds. Expand

MINIMAL CLONES I: THE FIVE TYPES

- Mathematics
- 1986

Publisher Summary A composition closed set of finitary operations on a fixed universe A containing all projections is a clone. The clones, ordered by inclusion, form an algebraic lattice L . This… Expand

On the complexity of colouring by superdigraphs of bipartite graphs

- Computer Science, Mathematics
- Discret. Math.
- 1992

The study of the H-colouring problem, that is, the decision problem ‘Is there an H -colouring of a given digraph G ?’, is continued and it is established that this problem is NP-complete whenever H contains a symmetric odd cycle. Expand