The stubborn list partition problem

Importance: Medium ✭✭

Author(s):	Cameron, Kathie
	Eschen, Elaine M.
	Hoang, Chinh T.
	Sritharan, R.

Subject:	Graph Theory
	» Graph Algorithms

Keywords:	list partition
	polynomial algorithm

Recomm. for undergrads: no

Prize: none

Posted	by:	mdevos
	on:	March 14th, 2007

Problem Does there exist a polynomial time algorithm which takes as input a graph $G$ and for every vertex $v \in V(G)$ a subset $\ell(v)$ of $\{1,2,3,4\}$ , and decides if there exists a partition of $V(G)$ into $\{A_1,A_2,A_3,A_4\}$ so that $v \in A_i$ only if $i \in \ell(v)$ and so that $A_1,A_2$ are independent, $A_4$ is a clique, and there are no edges between $A_1$ and $A_3$ ?

List partition problems form a very general framework for graph partitioning algorithms. Let $M$ be a symmetric $k \times k$ matrix over the alphabet $\{0,1,*\}$ . An $M$ -partition of a graph $G$ is a collection of pairwise disjoint sets $A_1,A_2,\ldots,A_k \subseteq V(G)$ with union $V(G)$ with the following properties. For every $i \neq j$ , there are no edges between $A_i$ and $A_j$ if $M_{ij} = 0$ , and all possible edges between $A_i$ and $A_j$ if $M_{ij} = 1$ . Similarly, for every $i$ , the set $A_i$ is independent if $A_{ii} = 0$ and a clique if $A_{ii} = 1$ . This framework captures a number of interesting problems. For instance, 3-colorability and skew-partitions are represented by the following matrices. $\left[ \begin{array}{ccc} 0 & * & * * & 0 & * * & * & 0 \end{array} \right] \quad\quad\quad \left[ \begin{array}{cccc} * & 1 & * & * 1 & * & * & * * & * & * & 0 * & * & 0 & * \end{array} \right]$ So, a graph has an $M$ -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 $M$ -partition for the second matrix above with the added constraint that $A_1,A_2,A_3,A_4$ are all nonempty.

An even more general framework than $M$ -partitions is list $M$ -partitions. Here, in addition to a $k \times k$ matrix $M$ , each vertex $v$ of the input graph comes with a list $\ell(v) \subseteq \{1,2,\ldots,k\}$ of permitted sets. A solution to this problem is an $M$ -partition $A_1,A_2,\ldots,A_k$ with the added property that whenever $v \in A_i$ we must have $i \in \ell(v)$ . List $M$ -partition problems arise naturally when studying $M$ -partitions, since if we decide to put a particular vertex $v$ into a particular set, this will generally place some restrictions on the neighbors and nonneighbors of $v$ which can be encoded by lists.

So now, for every possible symmetric $k \times k$ matrix $M$ (over $\{0,1,*\}$ ) we have a decision problem. Namely, given a graph $G$ with a list $\ell(v)$ for each vertex $v \in V(G)$ , does $G$ have a list $M$ -partition? This problem is quite well understood for matrices of size $3 \times 3$ 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 ( $O(n^{c \log^t n})$ where $n$ is the number of vertices, and $c,t$ are constants depending only on the matrix). Cameron et all investigated the $4 \times 4$ 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 $0$ 's by $1$ 's and $1$ 's by $0$ 's). $\left[ \begin{array}{cccc} 0 & * & 0 & * * & 0 & * & * 0 & * & * & * * & * & * & 1 \end{array} \right]$ 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 $K_n$ with a (not necessarily proper) edge-coloring $f : E(K_n) \rightarrow \{1,2,3\}$ and decides if there exists a vertex coloring $g : V(K_n) \rightarrow \{1,2,3\}$ so that no edge $xy$ has the same color as both $x$ and $y$ ?