Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-081 | 10th October 2003 00:00

Computation of the Lov\'asz Theta Function for Circulant Graphs



The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique and chromatic number, two well known hard to compute quantities.

In this paper we deal with the computation of the Lov\'asz function of certain circulant graphs, i.e., graphs whose adjacency matrix is circulant. Such graphs are important for both theoretical and practical reasons, and indeed arise in many different contests. The simplest circulant graph is the cycle; for the cycle, Lov\'asz showed a simple formula expressing the value of the theta function. We consider the theta function of circulant graphs which can be viewed as the super-position of two cycles, i.e., circulant graphs of degree 4. We invertigate the possibility to take advantage
of the specifis structure of the circulants in oreder to achieve higher efficiency. For a circulant graph $C_{n,j}$ on $n$ vertices and with a chord length $j$, $2 \leq j \leq \lfloor n/2 \rfloor$, we propose an $O(j)$ time algorithm to compute $\theta(C_{n,j})$ if $j$ is odd and an $O(n/j)$ time algorithm if $j$ is even. This is a significant improvement over the best known algorithms for the theta function computation for general graphs which take $O(n^4)$ time. We also derive conditions under which $\theta(C_{n,j})$ can be computed in $O(1)$ time.

ISSN 1433-8092 | Imprint