Mobile Agents on Chordal Graphs: Maximum Independent Set and Beyond

We consider the problem of finding a maximum independent set (MaxIS) of chordal graphs using mobile agents. Suppose n agents are initially placed arbitrarily on the nodes of an n-node chordal graph G = (V, E). Agents need to find a maximum independent set M of G such that each node of M is occupied by at least one agent. Also, each of the n agents must know whether its occupied node is a part of M or not. Starting from both rooted and arbitrary initial configuration, we provide distributed algorithms for n mobile agents having O(log n) memory each to compute the MaxIS of G in O(mnlog Delta) time, where m denotes the number of edges in G and Delta is the maximum degree of the graph. Agents do not need prior knowledge of any parameters if the initial configuration is rooted. For arbitrary initial configuration, agents need to know few global parameters beforehand. We further show that using a similar approach it is possible to find the maximum clique in chordal graphs and color any chordal graph with the minimum number of colors. We also provide a dynamic programming-based approach to solve the MaxIS finding problem in trees in O(n) time.