research-article

The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem

Authors:

Marcin Pilipczuk,

Michał Pilipczuk,

Jakub Onufry WojtaszczykAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 1666 - 1674

Published: 23 January 2011 Publication History

Abstract

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 possible 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 complete 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 n^{O(logn/log log n)} time complexity.

Furthermore our result implies a polynomial algorithm for the Stubborn problem which enables us to finish the classification of all List Matrix Partition variants for matrices of size at most four over subsets of {0, 1} started by Cameron et al. [SODA'04].

References

[1]

Open problem garden. http://garden.irmacs.sfu.ca/.

[2]

Andrei A. Bulatov. A dichotomy theorem for constraints on a three-element set. In Proc. of FOCS'02, pages 649--658, 2002.

Digital Library

[3]

Kathie Cameron, Elaine M. Eschen, Chính T. Hoàng, and R. Sritharan. The complexity of the list partition problem for graphs. SIAM J. Discrete Math., 21(4):900--929, 2007.

Digital Library

[4]

M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas. The strong perfect graph theorem. Ann. Math., (164):51--229, 2006.

[5]

Simone Dantas, Celina M. Herrera de Figueiredo, Sylvain Gravier, and Sulamita Klein. Finding h-partitions efficiently. ITA, 39(1):133--144, 2005.

[6]

Eric D. Demaine, Mohammad Taghi Hajiaghayi, and Dániel Marx. Open problems from dagstuhl seminar 09511, 2009.

[7]

Tomás Feder and Pavol Hell. List constraint satisfaction and list partition. manuscript. http://theory.stanford.edu/~tomas/listpart.ps.

[8]

Tomás Feder and Pavol Hell. Full constraint satisfaction problems. SIAM J. Comput., 36(1):230--246, 2006.

Digital Library

[9]

Tomás Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. Complexity of graph partition problems. In Proc. of STOC'99, pages 464--472, 1999.

Digital Library

[10]

Tomás Feder, Pavol Hell, Daniel Král, and Jiri Sgall. Two algorithms for general list matrix partitions. In Proc. of SODA'05, pages 870--876, 2005.

Digital Library

[11]

Tomás Feder, Pavol Hell, David G. Schell, and Juraj Stacho. Dichotomy for tree-structured trigraph list homomorphism problems. Preprint submitted to Elsevier.

[12]

Tomás Feder, Pavol Hell, and Kim Tucker-Nally. Digraph matrix partitions and trigraph homomorphisms. Discrete Applied Mathematics, 154(17):2458--2469, 2006.

Digital Library

[13]

Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proc. of STOC'93, pages 612--622, 1993.

Digital Library

[14]

M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

[15]

Pavol Hell. From graph colouring to constraint satisfaction: There and back again. In Topics in Discrete Mathematics, pages 407--432, 2006.

[16]

Pavol Hell and Jaroslav Nesetril. Colouring, constraint satisfaction, and complexity. Computer Science Review, 2:143--163, 2008.

Digital Library

[17]

Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299--301, 2004.

Digital Library

[18]

T. J. Shaefer. The complexity of satisfiability problems. In Proc. of STOC'78, pages 216--226, 1978.

Digital Library

Cited By

Miracle SRandall D(2016)Algorithms to approximately count and sample conforming colorings of graphsDiscrete Applied Mathematics10.1016/j.dam.2015.05.003210:C(133-149)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1016/j.dam.2015.05.003
Hell P(2014)Graph partitions with prescribed patternsEuropean Journal of Combinatorics10.1016/j.ejc.2013.06.04335(335-353)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.ejc.2013.06.043
Bodirsky MKára JMartin B(2012)The complexity of surjective homomorphism problems-a surveyDiscrete Applied Mathematics10.1016/j.dam.2012.03.029160:12(1680-1690)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1016/j.dam.2012.03.029
Show More Cited By

Recommendations

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More)

One of the driving problems in the CSP area is the dichotomy conjecture, formulated in 1993 by Feder and Vardi [Monotone monadic SNP and constraint satisfaction, in Proceedings of the 25th Annual Symposium on Theory of Computing, ACM, New York, 1993, pp. 612-...
Advances on the list stubborn problem
CATS '10: Proceedings of the Sixteenth Symposium on Computing: the Australasian Theory - Volume 109

The 4-partition problem is defined as partitioning the vertex set of a graph G into at most 4 parts A, B, C, D, where each part is not required to be nonempty, and is a stable set, a clique, or has no restriction; and pairs of distinct parts are ...
On Stubborn Graph Sandwich Problems
ICCGI '07: Proceedings of the International Multi-Conference on Computing in the Global Information Technology

The stubborn partition is a partition of the vertex set of a graph G into at most four parts A, B, C, D, with the following constraints: the internal constraints are part A and part B are required to be independent sets, and part D is required to be a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
58
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miracle SRandall D(2016)Algorithms to approximately count and sample conforming colorings of graphsDiscrete Applied Mathematics10.1016/j.dam.2015.05.003210:C(133-149)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1016/j.dam.2015.05.003
Hell P(2014)Graph partitions with prescribed patternsEuropean Journal of Combinatorics10.1016/j.ejc.2013.06.04335(335-353)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.ejc.2013.06.043
Bodirsky MKára JMartin B(2012)The complexity of surjective homomorphism problems-a surveyDiscrete Applied Mathematics10.1016/j.dam.2012.03.029160:12(1680-1690)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1016/j.dam.2012.03.029
Feder THell PSchell DStacho J(2011)Dichotomy for tree-structured trigraph list homomorphism problemsDiscrete Applied Mathematics10.1016/j.dam.2011.04.005159:12(1217-1224)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.dam.2011.04.005

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents