6
$\begingroup$

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of certain coloring configurations. The color configurations take forms like: there exists a vertex with color $a$ so that all vertices in the row of that vertex have colors in the set $\{a,b,c\}$ and all vertices in the column have colors in the set $\{c,d\}$; or they could be something like: there does not exist a column of vertices all with color $b$.

The number of dimensions in my problems is always fixed (e.g., 2-dimensional grid, 3-dimensional cube, and so forth) and the number of colors is fixed, but the constraints can change and I can vary the size of "graphs" I use. Given a problem, I need to determine whether there exists a colored graph (which will look like a hypercube in general) so that the existence and nonexistence constraints (coloring configurations) are satisfied.

I need to make general claims about problems of this kind (e.g., a graph always exists to solve problems with coloring configurations of a specific form; or, such a graph never exists for coloring configurations of a certain form, etc...). It would also be nice to know some properties about the graphs I need (e.g., the maximum size of the smallest graph that solves a particular class of such problems; or properties about the color patterns in such a graph, etc...).

Are problems of this type studied anywhere? Best I can tell right now, they are just complicated constraint satisfaction problems, but I can't find what I need out there. I need to read more about the mathematics behind these problems. I am most interested in understanding the general properties of such problems, and not so much in algorithms (though I don't mind learning about algorithms). Any references would help. References to subjects I need to read about, theorems, articles, and so forth would be great.

Improve this question
$\endgroup$
2
  • $\begingroup$ one angle is empirical study via SAT. it appears all your cases/ examples can be reduced to SAT. 2d grids of constraints show up in physics Ising model which is known to connect to NP complete problems but there the constraints are generally local. also though maybe your formulation is a bit too broad to fit into specific problems. $\endgroup$
    – vzn
    Oct 4, 2014 at 14:14
  • $\begingroup$ Do you have more explicit restrictions on the kinds of constraints you seek? Depending on the form of these constraints, this might be just an ordinary CSP (existential conjunctive sentences over a first order logic with relation symbols), a list-colouring problem, or something requiring a larger fragment of FOL or MSO. $\endgroup$
    – András Salamon
    Oct 6, 2014 at 14:10

0

Reset to default

Your Answer

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