Open Access
Issue
Published:
*28 July 2023*

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

301

Views

34

Downloads

Citations

1

Crossref

1

WoS

1

Scopus

0

CSCD

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

menu

Abstract

Full text

Outline

About this article

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

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

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

[4]

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

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

[6]

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

[7]

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

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

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

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

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

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

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

[14]

G. C. M. Gomes and V. F. dos Santos, Kernelization results for equitable coloring, *Proc. Comput. Sci.*, vol. 195, pp. 59–67, 2021.

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

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

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

[18]

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

Publication history

Copyright

Acknowledgements

Rights and permissions

Received: 15 September 2022

Revised: 04 December 2022

Accepted: 05 December 2022

Published:
28 July 2023

Issue date: December 2023

© The author(s) 2023.

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

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