Home » Subject » Graph Theory » Graph Algorithms
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 & * & * <br> * & 0 & * <br> * & * & 0 \end{array} \right] \quad\quad\quad \left[ \begin{array}{cccc} * & 1 & * & * <br> 1 & * & * & * <br> * & * & * & 0 <br> * & * & 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 & * <br> * & 0 & * & * <br> 0 & * & * & * <br> * & * & * & 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 $?

Bibliography

[CEHS] K. Cameron, E. Eschen, C.T. Hoàng, R. Sritharan The list partition problem for graphs


* indicates original appearance(s) of problem.
1 comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options