| Title | : | Local Algorithms for Variants of Graph Coloring |
| Speaker | : | Keshav Tiwari (IITM) |
| Details | : | Thu, 4 Jul, 2024 2:30 PM @ SSB 233 (Turing Hall |
| Abstract: | : | Graph coloring is a fundamental algorithm problem in computer science. Given a graph G, the algorithmic task is to assign a color to each vertex such that no two adjacent vertices share the same color. The minimum number of colors used to perform this task is called the chromatic number of the graph. Where it is trivial to color the graph with n colors, it is NP-Hard to find the chromatic number of a graph. And the decision problem of determining whether for a given k, a graph G admits a k coloring is NP-Complete. Classical models and algorithms assume the ability to read the entire input and produce the entire output. However, for extremely large inputs, such as graphs with millions or billions of nodes, this becomes impractical due to excessive time and space requirements which makes it impractical for a single processor to process. Such situations can be dealt with, alternative computation models such as parallel and distributed models of computing, or requiring that the output is only approximate or other weaker guarantees. In this work we study, Local Computation Algorithms (LCAs). LCAs only read a small portion of the input and produce a small portion of the output. For instance, for graph coloring problem, given a vertex query in a graph, an LCA will read a limited number of vertices and output the color of the queried vertex according to a specific coloring scheme. In this study, we look into weaker notions of coloring. One such notion is weak coloring, where all vertices needs at least a minimum number of neighbors to be of different colors, and other notion is partial coloring, where a large fraction of vertices will have all their neighbors of different colors and a combination of weak and partial colorings. A graph is α-partially colored if at least (1 − α) fraction of vertices have all their neighbors of different colors, and a graph is weakly 2-colored if each vertex is colored with one of the two given colors and has a neighbor of different color. We have developed LCAs, that needs time sublinear in input size for weak 2-coloring problem, and takes constant time for α-partial weak 2-coloring problem for bounded maximum degree graphs. Also we have developed LCAs that take constant time for weak 2-coloring and α-partial coloring of hyperfinite graphs. |
