Applying DSDP to Graph Problems

Within the directory DSDPROOT/examples/ is a program maxcut.c which reads a file containing a graph, generates the semidefinite relaxation of a maximum cut problem, and solves the relaxation. For example,

> maxcut graph1

The first line of the graph should contain two integers. The first integer states the number of nodes in the graph, and the second integer states the number of edges. Subsequent lines have two or three entries separated by a space. The first two entries specify the two nodes that an edge connects. The optional third entry specifies the weight of the node. If no weight is specified, a weight of $1$ will be assigned.

The same options that apply to reading SDPA files also apply here.

A similar program reads a graph from a file, formulates a minimum bisection problem or Lovász $\Theta$ problem, and solves it. For example,

> theta graph1

reads the graph in the file graph1 and solves this graph problem.