Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR03-081 | 10th October 2003 00:00

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

TR03-081
Authors: Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini
Publication: 29th November 2003 17:55
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.
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.