Name
Abstract | ||
|---|---|---|
Monotone monadic strict NP (MMSNP) is a class of computational problems that is closely related to the class of constraint satisfaction problems for constraint languages over finite domains. It is known that one of those classes has a complexity dichotomy if and only if the other class has. Whereas the dichotomy conjecture has been verified for several subclasses of constraint satisfaction problems, little is known about the the computational complexity for subclasses of MMSNP. In this paper we completely classify the complexity of MMSNP for the case where the obstructions are monochromatic and where loops in the input are forbidden. That is, we determine the computational complexity of natural partition problems of the following type. For fixed sets of finite structures ${\cal S}_1, \dots, {\cal S}_k$, decide whether a given loopless structure can be vertex-partitioned into $k$ parts such that for each $i \leq k$ none of the structures in ${\cal S}_i$ is homomorphic to the $i$th part. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/090778493 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
constraint satisfaction problems,computational complexity | Discrete mathematics,Combinatorics,Computational problem,Constraint satisfaction problem,Complexity of constraint satisfaction,Partition (number theory),Conjecture,Monotone polygon,Monad (functional programming),Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
26 | 1 | 0895-4801 |
Citations | PageRank | References |
6 | 0.42 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Hubie Chen | 2 | 418 | 40.82 |
| Tomás Feder | 3 | 1959 | 184.99 |