We study the communication complexity of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2024_475_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">$(\Delta + 1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertex coloring, where the edges of an n-vertex graph of maximum degree <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2024_475_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> are partitioned between two players. We provide a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combining this with a folklore <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2024_475_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> lower bound, this settles the randomized communication complexity of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2024_475_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="116" /> </InlineMediaObject> <EquationSource Format="TEX">$({\Delta + 1})\text {-coloring}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> </mrow> <mo stretchy="false">)</mo> <mtext>-coloring</mtext> </mrow> </math></EquationSource> </InlineEquation> up to constant factors.

($\Delta + 1$) vertex coloring in O(n) communication

期刊论文
发表日期：

2025年1月10日

查看全文

Maxime Flin,
Parth Mittal

摘要

We study the communication complexity of $(\Delta + 1)$ $(Δ + 1)$ vertex coloring, where the edges of an n-vertex graph of maximum degree $\Delta $ $Δ$ are partitioned between two players. We provide a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combining this with a folklore $\Omega (n)$ $Ω (n)$ lower bound, this settles the randomized communication complexity of $({\Delta + 1})\text {-coloring}$ $(Δ + 1) -coloring$ up to constant factors.

(\(\Delta + 1\)) vertex coloring in O(n) communication

摘要