More Web Proxy on the site http://driver.im/

Article

Two algorithms for general list matrix partitions

Authors:

Jiří SgallAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 870 - 876

Published: 23 January 2005 Publication History

Abstract

List matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. Most of the existing algorithms apply to concrete small matrices, i.e., to partitions into a small number of parts. We focus on two general classes of partition problems, provide algorithms for their solution, and discuss their implications.The first is an O(n^r+2)-algorithm for the list M-partition problem where M is any r by r matrix over subsets of {0, 1}, which has the "bisplit property". This algorithm can be applied to recognize so-called k-bisplit graphs in polynomial time, yielding a solution of an open problem from [2].The second is an algorithm running in time (rn)^{O(log r log n/log log n)}n^O(log²r) for the list M-partition problem where M is any r × r matrix over subsets of {0,1,...,q- 1}, with the "incomplete property". This algorithm applies to all non-NP-complete list M-partition problems with r = 3, and it improves the running time of the quasi-polynomial algorithm for the "stubborn problem" from [5], and for the "edge-free three-coloring problem" from [12].

References

[1]

B. Aspvall, M. R. Plass, and R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Information Processing Letters 8 (1979), pp. 121--123.

[2]

A. Brandstädt, P. L. Hammer, V. Bang Le, and V. V. Lozin, Bisplit graphs, DIMACS Technical Report 2002-44 and RUTCOR Research Report 2002-28, Rutgers University, Piscataway, NJ, 2002.

[3]

A. Brandstädt, P. L. Hammer, V. Bang Le, and V. V. Lozin, Bisplit graphs, to appear in Discrete Mathematics.

[4]

A. A. Bulatov, Tractable conservative constraint satisfaction problems, in: Proc. 18th IEEE Symposium on Logic in Computer Science (LICS) 2003, pp. 321--330.

Digital Library

[5]

K. Cameron, E. E. Eschen, C. T. Hoang, and R. Sritharan, The list partition problem for graphs, in: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, pp. 391--399.

Digital Library

[6]

S. Dantas. C. M. H. de Figueiredo, S. Gravier, and S. Klein, On H-partition problems, to appear in RAIRO - Theoretical Informatics and Applications. Tech. report PESC UFRJ ES-579/02, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil, 2002.

[7]

S. Dantas, C. M. H. de Figueiredo, S. Gravier, and S. Klein, Extended skew partition problems, to appear in Discrete Mathematics.

[8]

S. Dantas, C. M. H. de Figueiredo, S. Gravier, S. Klein, and B. Reed, Stable skew partition problem, Discrete Applied Mathematics 143 (2004), pp. 17--22.

Digital Library

[9]

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W{1}, Theoretical Computer Science 141 (1995), pp. 109--131.

Digital Library

[10]

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness III: Some structural aspects of the W hierarchy, in: Complexity Theory: Current Research, Cambridge University Press (1993), pp. 191--226.

Digital Library

[11]

R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, NY, 1999.

Digital Library

[12]

T. Feder and P. Hell, List constraint satisfaction and list partition, submitted.

[13]

T. Feder and P. Hell, Matrix partitions of perfect graphs, submitted.

[14]

T. Feder, P. Hell, and J. Huang, Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory 42 (1999), pp. 61--80.

Digital Library

[15]

T. Feder, P. Hell, S. Klein, and R. Motwani, List partitions, SIAM J. Discrete Math. 16 (2003), pp. 449--478.

Digital Library

[16]

T. Feder, P. Hell, and K. Tucker-Nally, List partitions and trigraph homomorphisms, submitted.

[17]

C. M. H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. Reed, Finding skew partitions efficiently, Journal of Algorithms 37 (2000), pp. 505--521.

Digital Library

[18]

P. Hell and J. Nešetřil, Graphs & homomorphisms, Oxford University Press, Oxford, UK, 2004.

Cited By

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
Cygan MPilipczuk MPilipczuk MWojtaszczyk JRandall D(2011)The stubborn problem is stubborn no moreProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133164(1666-1674)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133164
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
Show More Cited By

Two algorithms for general list matrix partitions
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

List matrix partitions of chordal graphs
Graph colorings

It is well known that a clique with k + 1 vertices is the only minimal obstruction to k-colourability of chordal graphs. A similar result is known for the existence of a cover by l cliques. Both of these problems are in fact partition problems, ...
List Partitions

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. Different choices of the matrix M lead to many well-known ...
Counting List Matrix Partitions of Graphs

Given a symmetric $D\times D$ matrix $M$ over \0,1,*\, a list $M$-partition of a graph $G$ is a partition of the vertices of $G$ into $D$ parts which are associated with the rows of $M$. The part of each vertex is chosen from a given list in such a way that no ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

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 2005

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
262
Total Downloads

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

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Cygan MPilipczuk MPilipczuk MWojtaszczyk JRandall D(2011)The stubborn problem is stubborn no moreProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133164(1666-1674)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133164
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
Dantas SFaria Lde Figueiredo CKlein SNogueira LProtti F(2010)Advances on the list stubborn problemProceedings of the Sixteenth Symposium on Computing: the Australasian Theory - Volume 10910.5555/1862317.1862326(65-70)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1862317.1862326
Montassier MRaspaud AZhu X(2009)An upper bound on adaptable choosability of graphsEuropean Journal of Combinatorics10.1016/j.ejc.2008.06.00330:2(351-355)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1016/j.ejc.2008.06.003
Hell PZhu X(2008)On the adaptable chromatic number of graphsEuropean Journal of Combinatorics10.1016/j.ejc.2007.11.01529:4(912-921)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.ejc.2007.11.015
Feder THell PKlein SNogueira LProtti F(2005)List matrix partitions of chordal graphsTheoretical Computer Science10.1016/j.tcs.2005.09.030349:1(52-66)Online publication date: 12-Dec-2005
https://dl.acm.org/doi/10.1016/j.tcs.2005.09.030

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