- Series
- Graph Theory Seminar
- Time
- Wednesday, December 3, 2014 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Zdenek Dvorak – Charles University
- Organizer
- Robin Thomas
For relations {R_1,..., R_k} on a finite set D, the {R_1,...,R_k}-CSP
is a computational problem specified as follows:
Input: a set of constraints C_1, ..., C_m on variables x_1, ..., x_n, where
each constraint C_t is of form R_{i_t}(x_{j_{t,1}}, x_{j_{t,2}}, ...) for some
i_t in {1, ..., k}
Output: decide whether it is possible to assign values from D to all the variables
so that all the constraints are satisfied.
The CSP problem is boolean when |D|=2. Schaefer gave a sufficient condition
on the relations in a boolean CSP problem guaranteeing its polynomial-time
solvability, and proved that all other boolean CSP problems are NP-complete.
In the planar variant of the problem, we additionally restrict the inputs only
to those whose incidence graph (with vertices C_1, ..., C_m, x_1, ..., x_m
and edges joining the constraints with their variables) is planar. It is known
that the complexities of the planar and general variants of CSP do not always
coincide. For example, let NAE={(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)}).
Then {NAE}-CSP is NP-complete, while planar {NAE}-CSP is polynomial-time solvable.
We give some partial progress towards showing a characterization of the complexity
of planar boolean CSP similar to Schaefer's dichotomy theorem.Joint work with Martin Kupec.