# dsdp-theta man page

dsdp-theta — Compute the Lovasz Theta number of a graph

## Synopsis

**dsdp-theta** [Options] *GRAPH_FILE*

## Description

The dsdp-theta program uses the DSDP library to compute the Lovasz Theta number of an input graph. This number is an upper bound for the maximum clique of a graph, a lower bound for the minimal graph coloring, and serves as a bound for several other combinatorial graph problems. The number is the solution to a semidefinite program.

The input file should be the complement of the graph. This file also demonstrates the use of customized data matrices in DSDP.

## Options

**-dloginfo***N*- Set the logging level (default 0). More information is printed for higher numbers.
**-params***FILE*- Read DSDP parameters from
*FILE* **-help**- Print a help message

## File Format

The input file should be in the following format:

n m

r1 c1 [w1]

…

im jm [wm]

where n is the number of nodes, and m is the number of edges. Each r/c pair or r/c/w triple describes one edge, where r is the row, c is the column, and w is the weight. The weight is ignored, if present.

## See Also

## Referenced By

dsdp5(1), dsdp-color(1), dsdp-maxcut(1), dsdp-stable(1).