Coloring Sparse Graphs with 3 Colors in the Massively Parallel Computation (MPC) Model Using Strongly Sublinear Memory

Thumbnail Image

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, Jara

Thesis advisor

Uitto, Jara

Keywords

graph problems, trees, 3-coloring, distributed computing, massively parallel computation, strongly sublinear memory

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202101311755

Collections

[dipl] Perustieteiden korkeakoulu / SCI