Approximation Algorithms for Graph Partition into Bounded Independent Sets

Jingwei Xie; Yong Chen; An Zhang; Guangting Chen

doi:10.26599/TST.2022.9010062

Tsinghua Science and Technology 2023, 28(6): 1063-1071 https://doi.org/10.26599/TST.2022.9010062

Open Access | Issue | Published: 28 July 2023

Approximation Algorithms for Graph Partition into Bounded Independent Sets

Show Author's Information Hide Author's Information Jingwei Xie^¹, Yong Chen^¹, An Zhang^¹, Guangting Chen^²(

)

1Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China

2Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, China

Keywords:

approximation algorithm, graph partition, independent set, 2-colorable graph

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

Download citation

EndNote(RIS)

BibTeX

283

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

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 $\frac{3}{2}$ -approximation algorithm for any $2$ -colorable graph is presented. An improved $\frac{7}{5}$ -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.

Full text

Abstract

Full text

Outline

About this article

Approximation Algorithms for Graph Partition into Bounded Independent Sets

Show Author's information Hide Author's Information Jingwei Xie^¹, Yong Chen^¹, An Zhang^¹, Guangting Chen^²(

)

1Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China

2Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, China

Abstract

Keywords: approximation algorithm, graph partition, independent set, 2-colorable graph

References(18)

[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.

DOI 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.

DOI Google Scholar

[4]

D. S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms, vol. 13, no. 3, pp. 502–524, 1992.

DOI 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.

DOI

[6]

T. R. Jensen and B. Toft, Graph Coloring Problems. New York, NY, USA: John Wiley and Sons, 1995.

DOI

[7]

S. Irani and V. Leung, Scheduling with conflicts on bipartite and interval graphs, J. Sched., vol. 6, no. 3, pp. 287–307, 2003.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI Google Scholar

[18]

D. Knop, Partitioning graphs into induced subgraphs, Discrete Appl. Math., vol. 272, pp. 31–42, 2020.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 15 September 2022

Revised: 04 December 2022

Accepted: 05 December 2022

Published: 28 July 2023

Issue date: December 2023

Copyright

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 11971139), the Natural Science Foundation of Zhejiang Province (No. LY21A010014), and the Fundamental Research Funds for the Provincial Universities of Zhejiang (No. GK229909299001-407).

Rights and permissions

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/).