# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 1 Introduction
However, the maximum coloring problem is an NP-hard problem even when its input is an interval graph [11]. Due to its intractability, a lot of papers aim to devise approximation algorithms for it on special graphs [11; 12]. Obviously, the above problem is a kind of vertex coloring, which is totally different from the edge coloring problems defined in this work. Note that some traditional open shop scheduling problems can be solved by using a bipartite-graph based approach [13]. A shop consists of many processors. Each of these processors performs a different task. In open shop no restrictions are placed on the order in which the tasks for any job are to be processed, which is different from the MECP and MDECP defined in this work. In [13], [PERSON] et al. showed that preemptive and non-preemptive optimal finish time schedules can be obtained in linear time when the number of processors is two. When the number of processors is larger than two, the optimal finish time schedule can still be obtained in polynomial time by applying maximal matching in bipartite graphs. To the best knowledge of the authors, this is the first time anyone has set out to define MECP and MDECP by using bipartite graph terms and techniques. Though some sophisticated algorithms have been developed for MDECP [3; 4; 14], MECP and MDECP are open to scholars to devise a polynomial-time algorithm even when the input belongs to biplanar graphs. In this work, we present the first approximation algorithm for MECP with a ratio bound of two when the input graph is biplanar. Moreover, a new graph problem called the cost-sharing maximum edge coloring problem (CSMECP) is defined in this work to further model how to partition communication messages in irregular redistribution scheduling. In our previous conference paper [15], we designed a heuristic algorithm to partition large data segments into multiple small data segments and to schedule them in different communication steps without using graph techniques. In this work, we formally reformulate the ideas by using a new graph decision problem, CSMECP. So far, it is an open question to know whether CSMECP is NP-complete or not. In this work, we also prove that the CSMECP is an NP-complete problem even when the input belongs to biplanar graphs. Figure 5: A solution to the maximum edge coloring problem (MECP) (and maximum degree edge coloring problem (MDECP)) when the input is the distribution graph in Figure 1.0  
In short, the contributions of this work are listed below. 1. Define three new bipartite graph models including MECP, MDECP, and CSMECP. 2. Design a first approximation algorithm with ratio bound of two for MECP when the input is a biplanar graph. 3. Give a formal proof to show that the CSMECP is an NP-complete problem even when the input is a biplanar graph. The remainder of our work is organized below. Section 2 introduces required graph definitions. Related research is briefly described and discussed in Section 3. We design and prove the correctness of an approximation algorithm for MECP in Section 4. Section 5 defines the CSMECP and shows that it is NP-complete. At last, Section 6 concludes this work and points out some future work.