0
$\begingroup$

Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?

$\endgroup$
1
  • $\begingroup$ Can you give a simple example to further clarify your intention? $\endgroup$
    – John L.
    Sep 15 '18 at 11:07
2
$\begingroup$

It's unclear exactly what level you're asking the question at.

In principle, you could set up a graph where the vertices are prisoners, there's an edge between any two prisoners who need to be kept separate, and each prison corresponds to a colour. In practice, there are probably too many prisoners in any reasonably sized country for this to be a computationally tractable approach (though the conflict graph would probably be rather sparse), there are more constraints on the system that would be hard to model in this graph-colouring approach, and two prisoners getting into a fight could cause a re-colouring that might cause a large proportion of the prison population to be moved, which is neither feasible nor desirable.

$\endgroup$
0
$\begingroup$

Yes, in theory, assuming the prison has $n$ separated blocks.

Let each vertex be a prisoner, let each hostile relationship be a graph edge between their two respective vertices and color the graph.

The color of each vertex determines what block the prisoner ends up in, no two prisoners that have a hostile relationship will end up in the same block.

Note that this isn't very useful in practice without other requirements, as for example blocks have limited capacity.

$\endgroup$

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.