Home Tsinghua Science and Technology Article
PDF (5.5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

Approximation Algorithms for Graph Partition into Bounded Independent Sets

Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China
Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, China
Show Author Information

Abstract

The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper. This problem is NP-hard, even restricted to bipartite graphs. First, a simple 32-approximation algorithm for any 2-colorable graph is presented. An improved 75-approximation algorithm is then designed for a tree. The theoretical proof of the improved algorithm performance ratio is constructive, thus providing an explicit partition approach for each case according to the cardinality of two color classes.

Keywords

graph partitionindependent set2-colorable graphapproximation algorithm

References

[1]
H. L. Bodlaender and K. Jansen, Restrictions of graph partition problems, Part I, Theor. Comput. Sci., vol. 148, no. 1, pp. 93–109, 1995.
Crossref Google Scholar
[2]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA, USA: W. H. Freeman & Company, 1979.
[3]
H. L. Bodlaender, K. Jansen, and G. J. Woeginger, Scheduling with incompatible jobs, Discrete Appl. Math., vol. 55, no. 3, pp. 219–232, 1994.
Crossref Google Scholar
[4]
D. S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms, vol. 13, no. 3, pp. 502–524, 1992.
Crossref Google Scholar
[5]
P. M. Pardalos, T. Mavridou, and J. Xue, The graph coloring problem: A bibliographic survey, in Handbook of Combinatorial Optimization, D. Z. Du and P. M. Pardalos, eds. New York, NY, USA: Springer, 1998, pp. 1077–1141.
Crossref
[6]
T. R. Jensen and B. Toft, Graph Coloring Problems. New York, NY, USA: John Wiley and Sons, 1995.
Crossref
[7]
S. Irani and V. Leung, Scheduling with conflicts on bipartite and interval graphs, J. Sched., vol. 6, no. 3, pp. 287–307, 2003.
Crossref Google Scholar
[8]
G. Even, M. M. Halldórsson, L. Kaplan, and D. Ron, Scheduling with conflicts: Online and offline algorithms, J. Sched., vol. 12, no. 2, pp. 199–224, 2009.
Crossref Google Scholar
[9]
N. Bianchessi and E. Tresoldi, A Stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts, Comput. Oper. Res., vol. 136, p. 105464, 2021.
Crossref Google Scholar
[10]
D. R. Page and R. Solis-Oba, Makespan minimization on unrelated parallel machines with a few bags, Theor. Comput. Sci., vol. 821, pp. 34–44, 2020.
Crossref Google Scholar
[11]
A. Mallek, M. Bendraouche, and M. Boudhar, Scheduling identical jobs on uniform machines with a conflict graph, Comput. Oper. Res., vol. 111, pp. 357–366, 2019.
Crossref Google Scholar
[12]
T. Pikies, K. Turowski, and M. Kubale, Scheduling with complete multipartite incompatibility graph on parallel machines: Complexity and algorithms, Artif. Intell., vol. 309, p. 103711, 2022.
Crossref Google Scholar
[13]
H. L. Bodlaender and F. V. Fomin, Equitable colorings of bounded treewidth graphs, Theor. Comput. Sci., vol. 349, no. 1, pp. 22–30, 2005.
Crossref Google Scholar
[14]
G. C. M. Gomes and V. F. dos Santos, Kernelization results for equitable coloring, Proc. Comput. Sci., vol. 195, pp. 59–67, 2021.
Crossref Google Scholar
[15]
H. Furmańczyk and V. Mkrtchyan, Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs, arXiv preprint arXiv: 2009.12784, 2022.
Crossref Google Scholar
[16]
D. De Werra, M. Demange, B. Escoffier, J. Monnot, and V. T. Paschos, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, Discrete Appl. Math., vol. 157, no. 4, pp. 819–832, 2009.
Crossref Google Scholar
[17]
F. Bonomo and D. De. Estrada, On the thinness and proper thinness of a graph, Discrete Appl. Math., vol. 261, pp. 78–92, 2019.
Crossref Google Scholar
[18]
D. Knop, Partitioning graphs into induced subgraphs, Discrete Appl. Math., vol. 272, pp. 31–42, 2020.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 6,
December 2023
Pages 1063-1071
DOI: 10.26599/TST.2022.9010062
Cite this article:
Xie J, Chen Y, Zhang A, et al. Approximation Algorithms for Graph Partition into Bounded Independent Sets. Tsinghua Science and Technology, 2023, 28(6): 1063-1071. https://doi.org/10.26599/TST.2022.9010062
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return