Colorful Vertex Recoloring of Bipartite Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929669856559104 |
|---|---|
| author | Patt-Shamir, Boaz Rosen, Adi Umboh, Seeun William |
| author_facet | Patt-Shamir, Boaz Rosen, Adi Umboh, Seeun William |
| contents | In vertex recoloring, we are given $n$ vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring vertices, at a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent ``anti affinity'' (disengagement) constraints. Online recoloring is a hard problem. One family of instances which is fairly well-understood is bipartite graphs, in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is $Θ(\log n)$.
We propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. We analyze the simple case of bipartite graphs of bounded largest \emph{bond} (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). First, we propose two algorithms. One exhibits a trade-off for the uniform-cost case: given $Ω(\logβ)\le c\le O(\log n)$ colors, the algorithm guarantees that its cost is at most $O(\frac{\log n}{c})$ times the optimal offline cost for two colors, where $n$ is the number of vertices and $β$ is the size of the largest bond. The other algorithm is for the case where the additional colors come at a higher cost, $D>1$: given $Δ$ additional colors, where $Δ$ is the maximum degree in the graph, the algorithm guarantees $O(\log D)$ competitiveness. As to lower bounds, we show that if the cost of the extra colors is $D>1$, no (randomized) algorithm can achieve a competitive ratio of $o(\log D)$. We also show that for bipartite graphs of unbounded bond size, any deterministic online algorithm has competitive ratio $Ω(\min(D,\log n))$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05796 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Colorful Vertex Recoloring of Bipartite Graphs Patt-Shamir, Boaz Rosen, Adi Umboh, Seeun William Data Structures and Algorithms F.2.2 In vertex recoloring, we are given $n$ vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring vertices, at a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent ``anti affinity'' (disengagement) constraints. Online recoloring is a hard problem. One family of instances which is fairly well-understood is bipartite graphs, in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is $Θ(\log n)$. We propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. We analyze the simple case of bipartite graphs of bounded largest \emph{bond} (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). First, we propose two algorithms. One exhibits a trade-off for the uniform-cost case: given $Ω(\logβ)\le c\le O(\log n)$ colors, the algorithm guarantees that its cost is at most $O(\frac{\log n}{c})$ times the optimal offline cost for two colors, where $n$ is the number of vertices and $β$ is the size of the largest bond. The other algorithm is for the case where the additional colors come at a higher cost, $D>1$: given $Δ$ additional colors, where $Δ$ is the maximum degree in the graph, the algorithm guarantees $O(\log D)$ competitiveness. As to lower bounds, we show that if the cost of the extra colors is $D>1$, no (randomized) algorithm can achieve a competitive ratio of $o(\log D)$. We also show that for bipartite graphs of unbounded bond size, any deterministic online algorithm has competitive ratio $Ω(\min(D,\log n))$. |
| title | Colorful Vertex Recoloring of Bipartite Graphs |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2501.05796 |