The stubborn problem is stubborn no more

22nd Annual ACM-SIAM Symposium on Discrete Algorithms

数学;计算机科学

(a polynomial algorithm for 3{compatible colouring ; the stubborn list partition problem)

Others  :  http://www.siam.org/proceedings/soda/2011/SODA11_127_cyganm.pdf
PID  :  32610

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We present a polynomial time algorithm for the 3- Compatible colouring problem, where we are given a complete graph with each edge assigned one of 3 possi- ble colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. Consequently we com- plete the proof of a dichotomy for the k-Compatible Colouring problem. The tractability of the 3-Compatible colouring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] | a quasipolynomial algorithm with a nO(logn= log logn) time complexity. Furthermore our result implies a polynomial algo- rithm for the Stubborn problem which enables us to nish the classication of all List Matrix Partition variants for matrices of size at most four over subsets of