# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 5 New Graph Model for Applying Partitioning Message Techniques  
In order to solve the CSMECP efficiently, we try to shorten the total communication time but do not increase the required total steps simultaneously. In [15], [PERSON] et al. have designed a heuristic algorithm for the CSMECP. Unlike existing conventional approaches, the intuitive idea behind our previous work [15] is partitioning larger data into multiple small data units, and our algorithm reschedules these added small data units properly in different existing steps. So far, it is an open question to know whether CSMECP is NP-hard or not. In this section, we give a proof for CSMECP. When \(G\) is bipartite, \(\chi^{\prime}(G)=\Delta(G)\) is a well-known graph property [18]. In terms of graphs, this equation indicates the number of minimum colors is equal to the maximum degree of the inputted bipartite graph. In terms of communication, this equation indicates that the minimum number of communication steps for this distribution (discussed in this work) equals the maximum degree \(\Delta(G)\) of the corresponding distribution graph \(G\). Specifically, to avoid increasing the total communication steps, we should partition larger data into small data units as many as possible and scatter them into different steps if \(\Delta(G)=\Delta(G^{\prime})\) here \(G^{\prime}\) represents the new distribution graph after these partitions. How to scatter these new add-in small data elements into different steps is another key issue for CSMECP. When a new data communication is added in a pre-schedule for an arbitrary step, if the size of the new data unit is larger than that of every data units in the pre-schedule, the time for this step becomes longer. Note that CSMECP is designed to avoid this case. In CSMECP, to model how to partition larger data into small data units, we add duplicate edges for each of these edges with larger weights to the redistribution graph. For such edge \(e\) with larger weight, these corresponding new-adding edges share weights with \(e\). The above techniques are used to present the properties of CSMECP as follows. **Property 1**. : _When a weighted biplanar graph \(G=(S,\,T,\,E)\) is taken as an input, the CSMECP is a kind of decision problem, which adds additional edges \(E^{\prime}\) so that the new graph \(G^{\prime}=(S,\,T,\,E\cup E^{\prime})\) satisfies the subsequent constraints:_  
1. _Additional edge \((s,\,t)\) is allowed to be added in edge set \(E^{\prime}\) only if these two end points, \(s\) and \(t\), are originally adjacent by an edge \((s,\,t)\) in \(E\)._
2. \(\Delta(G^{\prime})=\Delta(G)\)_. That means after adding some multiple edges, the maximum degree of the new graph \(G^{\prime}\) remains unchanged when compared to that of the original one \(G\)._
3. _In_ \(G^{\prime}=(S,\,T,\,E\cup E^{\prime})\)_,_ \(\sum_{i=1}^{\Delta(G^{\prime})}\left\{w(e)\middle|e=(s,\,t)\text{ in }E\,\right\}=\sum_{i=1}^{ \Delta(G^{\prime})}\left\{w(e)\middle|e=(s,\,t)\text{ in }E\,\right\}\) _in_ \(G=(S,\,T,\,E)\)_, where w(e) is the weight of_ \(e\)_._  
_When a weighted bipartite graph \(G=(S,\,T,\,E)\) with a value \(K\) are given as inputs, the cost-sharing maximum edge coloring problem (CSMECP) is to answer whether there is a proper edge coloring \(\{F_{1},\,F_{2},\,F_{3},\,\ldots,\,F_{\Delta}\}\) of \(G^{\prime}\) = (\(V,\,E\cup E^{\prime}\)) such that \(\sum_{i=1}^{\Delta}\max\{w(e)\middle|e\in F_{i}\,\}\leq K\)._  
In the rest of this section, we show that CSMECP is NP-complete even when \(G\) is biplanar by transforming the partition problem to CSMECP. **Property 2**. : _When a set \(A\) with a function s(k)\(\in\)Z\({}^{+}\) for each k\(\in\)A are given as inputs, the partition problem is to answer whether there exists a subset \(A^{*}\) in \(A\) such that \(\sum\limits_{k\in A*}s(k)=\sum\limits_{k\in A-A*}s(k)\)._  
**Theorem 7**. : _CSMECP is NP-complete even when the input is a biplanar graph._  
Proof.