2
$\begingroup$

I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.

$\endgroup$

1 Answer 1

2
$\begingroup$

If you want a graph, it needs to be bipartite. Hence the path of two edges or any subgraph thereof. (Here I am following the convention that graphs have no loops. As David Richerby points out in a comment, graphs with loops also have polynomial-time CSPs (by virtue of triviality).)

A more interesting example is linear algebra over the three-element field: The domain is the set of congruence classes $\bmod 3$ and the constraint relations are given by linear equations.

$\endgroup$
1
  • 1
    $\begingroup$ The graph case is also decidable in polynomial time if the graph has at least one self-loop. $\endgroup$ Commented Nov 7, 2018 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.