AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (5.5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
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

539

Views

41

Downloads

1

Crossref

1

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 15 September 2022
Revised: 04 December 2022
Accepted: 05 December 2022
Published: 28 July 2023
© The author(s) 2023.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return