# Which problems in graph theory can be stated as quadratic programs?

There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ${\bf L}$ of a graph. Examples are:

1) the max-cut problem is equivalent to finding a sign vector that maximizes a quadratic form $$\max_{x_i\in\{\pm1\}} \sum_{i,j}A_{i,j}(1- x_ix_j),$$ 2) The densest $k$-subgraph is equivalent to $$\max_{x_i\in\{0,1/\sqrt{k}\},\;{\bf 1}^T{\bf x}=1} {\bf x}^T{\bf A}{\bf x}$$ 3) The Grothendieck constant involves maximizing the adjacency's quadratic form over sign vectors $$\max_{x_i\in\{\pm1\}} {\bf x}^T{\bf A}{\bf x},$$ 4) The spectral profile of a graph $$\Lambda(\delta) = \min_{d(\text{supp}({\bf x}))\le \delta} \frac{{\bf x}^T{\bf L}{\bf x}}{\sum_i \text{deg}(\text{vertex}_i) x_i^2},$$ where $d(\text{supp}(x))$ is the fraction of edges incident on vertices within the support of vector ${\bf x}$

4+$\epsilon$) Anything involving the computation of an adjacency/laplacian eigenvalue.

${\bf Q}$: Which other problems in graph theory can be expressed as maximizing/minimizing a quadratic form?

• I think the question is interesting, but at best it will generate a list of answers. Should it be CW ? – Suresh Venkat Nov 27 '12 at 4:06
• That is true, I completely agree. There is no definitive answer for sure, but I'm still hoping for interesting answers. – Dimitris Nov 27 '12 at 7:48
• The quadratic traveling salesman problem amounts to a non-convex quadratic program with integrality constraints. See tu-chemnitz.de/mathematik/preprint/2011/PREPRINT_08.pdf – Dominique Nov 27 '12 at 14:46
• The Independent Set problem has an easy (adjacency) quadratic programming formulation, using the 0-1 representation instead of -1/+1. See doi:10.1016/0012-365X(92)00057-X for more. – András Salamon Nov 28 '12 at 12:39