Coloring Sparse Graphs with 3 Colors in the Massively Parallel Computation (MPC) Model Using Strongly Sublinear Memory
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Date
2021-01-26
Department
Major/Subject
Applied Mathematics
Mcode
SCI3053
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
5+22
Series
Abstract
The question of what problems can be solved, and how efficiently, has always been at the core of theoretical computer science. One such fundamental problem is graph coloring; it is well researched and has numerous applications in areas of computer science such as scheduling and pattern matching. The challenges faced when designing graph coloring algorithms are dictated by the underlying graph family, the number of colors allowed, and the model of computation. In this work we consider the graph family of trees and the distributed Massively Parallel Computation (MPC) model, introduced by Karloff et al. \cite{karloff}. Our contribution to the field of distributed computing is a deterministic strongly sublinear MPC algorithm for 3-coloring unbounded degree trees with $n$ nodes in $O(\log \log n)$ time. To the best of our knowledge, this is the current state-of-the-art algorithm, improving on the work of Ghaffari et al. \cite{ghaffari}. It is loosely based on two previous works by Brandt et al. \cite{sparce,sirocco}. Before computing a 3-coloring, our algorithm partitions the input tree into disjoint node sets $H_1,H_2,\dots,H_l$, in $O(\log \log n)$ time. For each node $v \in H_i$, it holds that $v$ has at most two neighbors in the set $\bigcup_{j=i}^l H_j$. We consider this partitioning in and of itself an important contribution, since it has the potential of being a useful subroutine in future algorithms. For example, a similar technique was used by Chang et al. \cite{chang} in their seminal paper to establish an important time hierarchy theorem for the distributed LOCAL model on trees.Teoreettisen tietojenkäsittelytieteen tärkeimpiä tavoitteita on tutkia, mitkä ongelmat ovat ratkaistavissa, ja kuinka tehokkaasti nämä ratkeavat. Eräs sellainen ongelma on verkkojen väritysongelma, jolla on lukuisia sovelluksia tietojenkäsittelytieteen ongelmissa, kuten aikataulutusongelmissa ja hahmontunnistuksessa. Verkkojen värittämiseen liittyvät haasteet riippuvat verkkoperheestä, sallitusta värien määrästä ja valitusta mallista. Tässä työssä keskitytään puiden verkkoperheeseen ja hajautettuun Massiivisen rinnakkaislaskennan (MPC) malliin, jonka esittivät Karloff ym. \cite{karloff}. Työn tulos on MPC-mallissa vahvasti alilineaarista muistia käyttävä deterministinen 3-väritysalgoritmi rajoittamattoman asteen $n$-solmuisissa puissa, jonka ajoaika on $O(\log \log n)$. Kyseessä on läpimurtoalgoritmi, joka parantaa Ghaffari ym. \cite{ghaffari} esittämiä tuloksia ja pohjautuu löyhästi Brandt ym. \cite{sparce,sirocco} esittämiin algoritmeihin. Ratkaistaessa 3-väritysongelmaa algoritmi ensin osittaa puun solmut erillisiin joukkoihin $H_1,H_2,\dots,H_l$, ajassa $O(\log \log n)$. Osituksessa pätee, että jokaisella solmulla $v \in H_i$ on enintään kaksi naapuria joukossa $\bigcup_{j=i}^l H_j$. Kyseinen ositus on esille nostamisen arvoinen ja on myös sellaisenaan mittava tulos, koska osituksella on paljon potentiaalista käyttöä myös muissa algoritmeissa. Esimerkiksi Chang ym. \cite{chang} hyödynsivät vastaavanlaista ositusta mullistavassa artikkelissaan, missä he johtivat tärkeän hajautetun LOCAL-mallin aikahierarkian puissa.Description
Supervisor
Uitto, JaraThesis advisor
Uitto, JaraKeywords
graph problems, trees, 3-coloring, distributed computing, massively parallel computation, strongly sublinear memory