dsdp-theta - Man Page

dsdp-theta [Options] GRAPH_FILE

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.

-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

The input file should be in the following format:

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.

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

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