DIMACS

General Information

Student: Hongyi Brian Hu
School: Carnegie Mellon University
E-mail: hongyih@andrew.cmu.edu
Project: Sum edge coloring of multigraphs

Project Description

We study sum edge coloring for multigraphs, motivated by the bi-processor scheduling problem; the jobs must be scheduled in such a way that no two jobs that share a processor may run at the same time and the average completion time is minimized. If edges are jobs and vertices processors, then the scheduling problem is precisely edge coloring with the intention to minimize the sum over all colors used. We investigate two variants of sum coloring: the Minimum Edge Chromatic Sum (MECS) problem and the Optimum Cost Chromatic Partition (OCCP) problem. The former aims to find an edge coloring that minimizes the sum of the maximum color on each edge while the latter the sum of all colors used. Despite similarity of the two objectives, they are quite different in complexity. This difference is most observable when restricted to trees; we show that the former remains NP-hard, while the latter is polynomially solvable.

Preliminary Presentation
Final Presentation
Final Techincal Report

Weekly Log

Week 1:

My mentor and I had our first official meeting. I was introduced to my new teammate Stephen. I spent time getting familar with the sum coloring definitions. Furthermore, I also studied a tiny bit of introductory concepts in complexity theory, such as Turing machine, complexity classes, reduction. Stephen and I worked together to prove Fact 1.1 from Salavatipour's On Sum Coloring of Graphs as warm up. Over the weekend, we finished the preliminary presentation slides, which I will present next week Monday.

Week 2:

All participants this summer, including myself, gave their presentations on their topic on Monday and Tuesday. On Thrusday, Atefeh went over Salavatipour's tree coloring algorithm with me. I reproduced the result myself and proved its correctness. On all the other days, I spent time going over lots of relavent previous works on sum coloring and their solutions. There are many papers that I've saved (here), and they were all very difficult to understand, but it was interesting to see the kind of questions that the community have been asking. One of the most interesting one uses linear programming and random rounding to produce an approximation algorithm for coloring. After all this exploring, I made my own list of overarching questions for this summer, and I will meet with Atefeh again next week to discuss their viability.

Week 3:

Progress has been slow. We decided on our short-term goal for this summer:

  1. Develop polynomial algorithm for multi-tree with bounded degree and multiplicity
  2. Show it is NP-hard to find a sum coloring for multi-trees of arbitrary degree and multiplicity
So far the paper Minimum Sum Multicoloring on the Edges of Trees by Marx has been tremendously useful. We are trying to imitate its techniques. In other news, I attended a great lecture by Samotij on some nice connections betweeen probability theory and random graphs. In particular, people have been using random graphs to answer problems in theory of large deviation for non-linear variables (here). I hope next week will be more fruitful.

Week 4:

It turns out that the algorithm in Marx's paper in Theorem 2.2 can be applied directly to solve our problem, assuming that both degree and edge multiplicity is bounded. We will write up this algorithm using our problem notation as soon as possible. I've also started learning about Marx's proof of edge multicoloring being NP-hard. He does a reduction proof using a specific case of 3-SAT. The constructions that he is doing are very interesting and worth understanding deeply about. For my problem, I'm not sure whether bounding edge multiplicity at most 2 is enough. It most likely will be, but maybe a little more is needed. This decision is important because it will decide how my tree construction will turn out.

Week 5:

We learned that Marx's proof for NP-hardest can be immitated for our case. When the tree has an optimum coloring (under our definition), it also has an A-good coloring (under his definition), which can be constructed by recoloring the optimum coloring. This is sufficient for finishing both directions of the reduction proof.

Week 6:

I have been writing up the stuff we have done in the past weeks up in $\LaTeX$.

Week 7:

The MECS problem is not NP-hard for multitrees. It actually has a polynomial time solution via LP that was under our nose the whole time. For weeks I have doubted imitating Marx's complexity proof, and it turns out I was right. What also made me doubt that it's NP-hard is a result by Giaro that says MECS is $O(n^4 \log n)$ for simple bipartite. Although edge multiplicity is 1, bipartite graphs seem a lot of complex than trees.

Week 8:

We found out that Marx's proof has a small notational/conceptual error. Although 3-occurence 3SAT is NP-hard when each clause is defined as having AT MOST 3 variables, it is trivial when there are exactly 3. Marx's did his proof assuming each clause has exactly 3. Luckily his proof still holds if we just extend one of this gadgets for clauses with exactly 2 variables. We will make this an additional content in our final paper.

Week 9:

We competed the slides and gave our presentation on Thursday. We also grinded till Friday night, finishing our report for the summer. This concludes the program.

Acknowledgement

We would like to thank the National Science Foundation grant CCF-1852215 for supporting our research. We would also like to thank Dr. Atefeh Mohajeri for her guidance, the DIMACS REU, and Dr. Lazaros Gallos for making all of this possible.

References

[CRV08] Jean Cardinal, Vlady Ravelomanana, and Mario Valencia-Pabon. “Chromatic edge strength of some multigraphs”. In:Electronic Notes in Discrete Mathematics 30 (2008), pp. 39–44.
[Kro+96] Leo G Kroon et al. “The optimal cost chromatic partition problem for trees andinterval graphs”. In:International Workshop on Graph-Theoretic Concepts in Computer Science. Springer. 1996, pp. 279–292.
[Mar03] Dániel Marx. “Minimum sum multicoloring on the edges of trees”. In:Inter-national Workshop on Approximation and Online Algorithms. Springer. 2003, pp. 214–226.
[Sal03] Mohammad R Salavatipour. “On sum coloring of graphs”. In:Discrete Applied Mathematics 127.3 (2003), pp. 477–488.
[Tov84] Craig A. Tovey. “A Simplified NP-Complete Satisfiability Problem”. In:Discrete Applied Mathematics8 (1984), pp. 85–89.
[Vai89] Pravin M Vaidya. “Speeding-up linear programming using fast matrix multipli-cation”. In:30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1989, pp. 332–337.