Abstract
This paper investigates the "batch coloring" model, a hybrid between offline and online graph coloring where vertices arrive in $k$ discrete groups. We analyze the competitive ratio for various graph classes, revealing a significant "information gap" for interval graphs where geometric representation knowledge improves performance. For most other classes, including trees and planar graphs, the optimal competitive ratio is shown to be $k$.
Introduction
Traditional graph coloring models occupy two extremes: the offline model, where the entire graph is known, and the online model, where vertices arrive one by one. Many practical scenarios, such as resource allocation and job scheduling, fall into a middle ground where information arrives in batches. This paper formalizes the Batch Model, where an adversary reveals the graph in $k$ discrete batches. The challenge lies in coloring each batch without knowledge of future arrivals, aiming to minimize the competitive ratio—the performance gap between the batch algorithm and an optimal offline algorithm.
Methods
The research employs theoretical proofs and adversarial constructions to determine upper and lower bounds on competitive ratios. Key methodologies include:
- Adversarial Strategies: Constructing specific graph instances that force batch algorithms to use a high number of colors.
- Algorithm Design: Developing strategies like
TwoBatchesfor interval graphs, which utilizes stack-based coloring for initial batches and "chain-crossover" methods for subsequent ones. - Sum Coloring Analysis: Evaluating the "Sum Coloring" problem, where the goal is to minimize the total sum of color indices, using series convergence to bound performance when $k$ is unknown.
Key Insights and Results
The Information Gap in Interval Graphs
A primary finding is the "information gap" in interval graphs. In standard online coloring, knowing the geometric interval representation does not offer an advantage. However, in the batch model ($k=2$), seeing the intervals allows for a 1.5-competitive ratio, whereas seeing only the edges limits the ratio to 2.
General Graph Classes and the "New Colors" Strategy
For many graph classes, including trees, bipartite, and planar graphs, the optimal strategy is the "New Colors" approach: using a disjoint set of colors for each new batch. This results in a competitive ratio of $k$.
Summary of Results
- Trees and Forests: The optimal competitive ratio is exactly $k$.
- Interval Graphs ($k=2$): The ratio is 2 without representation knowledge and 1.5 with it.
- Sum Coloring: When $k$ is known, the ratio is $k$. When $k$ is unknown, the ratio grows at a rate of $O(k \log k (\log \log k)^2)$.
- First-Fit Performance: The First-Fit algorithm is 2-competitive for sum coloring on trees, independent of the number of batches.
Conclusion
The study primarily addresses cases where $k$ is a small constant or known in advance. While it establishes bounds for unknown $k$ in sum coloring, exact closed-form expressions remain an area for future research. Further exploration could include "advice complexity" or applying the batch model to other combinatorial problems like vertex covers.
Summary updated