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$
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
    $\begingroup$ The graph case is also decidable in polynomial time if the graph has at least one self-loop. $\endgroup$ – David Richerby Nov 7 '18 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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