Journal Home >

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.

Abstract
Full text
Outline

# Approximation Algorithms for Graph Partition into Bounded Independent Sets

Show Author's information An Zhang1Guangting Chen2( )
Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China
Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, China

## 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: 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.
[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
Acknowledgements
Rights and permissions

## Publication history

Revised: 04 December 2022
Accepted: 05 December 2022
Published: 28 July 2023
Issue date: December 2023