![](/files/happy5.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ v \in V(G) $](/files/tex/1466419f1101030390df1795c6f6a568ac18776b.png)
![$ \ell(v) $](/files/tex/fa7556a65d20c6dbe9ae8911f5247691d913dca7.png)
![$ \{1,2,3,4\} $](/files/tex/de0625f2e589e27a7b57cc4b66560e0e0d0e5daf.png)
![$ V(G) $](/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png)
![$ \{A_1,A_2,A_3,A_4\} $](/files/tex/332fca63ad23d0f750116b00770cf8b73f25bf0b.png)
![$ v \in A_i $](/files/tex/526a8824e06e79af8564522aa70897d4c46c6fdc.png)
![$ i \in \ell(v) $](/files/tex/aa7e74539033b93194f38cd4ef8273a0543143b5.png)
![$ A_1,A_2 $](/files/tex/abb6004b066dae60842422a05109dd268e25b013.png)
![$ A_4 $](/files/tex/50c3d5221f6420416edde366fd2b081acada5bfe.png)
![$ A_1 $](/files/tex/cad9bfcb5f598c9f3e6780be0cf006515579b1fb.png)
![$ A_3 $](/files/tex/1979729d0d75e585787ae2a135d16b37f3e434f2.png)
List partition problems form a very general framework for graph partitioning algorithms. Let be a symmetric
matrix over the alphabet
. An
-partition of a graph
is a collection of pairwise disjoint sets
with union
with the following properties. For every
, there are no edges between
and
if
, and all possible edges between
and
if
. Similarly, for every
, the set
is independent if
and a clique if
. This framework captures a number of interesting problems. For instance, 3-colorability and skew-partitions are represented by the following matrices.
So, a graph has an
-partition for the first matrix above if and only if it is 3-colorable, and it has a skew partition if and only if it has an
-partition for the second matrix above with the added constraint that
are all nonempty.
An even more general framework than -partitions is list
-partitions. Here, in addition to a
matrix
, each vertex
of the input graph comes with a list
of permitted sets. A solution to this problem is an
-partition
with the added property that whenever
we must have
. List
-partition problems arise naturally when studying
-partitions, since if we decide to put a particular vertex
into a particular set, this will generally place some restrictions on the neighbors and nonneighbors of
which can be encoded by lists.
So now, for every possible symmetric matrix
(over
) we have a decision problem. Namely, given a graph
with a list
for each vertex
, does
have a list
-partition? This problem is quite well understood for matrices of size
and smaller. Here, every such problem is known to either be polynomial solvable, or be NP-complete. In general, Feder and Hell have proven a kind of quasi-dichotomy result for list partition problems. Namely, every such problem is either NP-complete or has a quasi-polynomial time algorithm (
where
is the number of vertices, and
are constants depending only on the matrix). Cameron et all investigated the
matrices and were able to classify all of the associated list partition problems as either polynomial solvable or NP-complete with the exception of two. One is the stubborn problem, specified by the matrix below (and given in the problem statement), the other is the complementary problem (replace
's by
's and
's by
's).
Hell has mentioned to me (M. DeVos) that he believes this stubborn problem to be the tip of a very interesting iceberg, and he suggested the following problem which is closely related, but perhaps better behaved (it is certainly more symmetric).
Problem: Does there exist a polynomial time algorithm which takes as input a complete graph with a (not necessarily proper) edge-coloring
and decides if there exists a vertex coloring
so that no edge
has the same color as both
and
?
Bibliography
[CEHS] K. Cameron, E. Eschen, C.T. Hoàng, R. Sritharan The list partition problem for graphs
* indicates original appearance(s) of problem.