<p>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: </p>

<p>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}$</p>

<p>( <a href="http://www.eecs.berkeley.edu/~prasad/Files/spectralprofile.pdf">http://www.eecs.berkeley.edu/~prasad/Files/spectralprofile.pdf</a> )</p>

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

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

CC BY-SA 3.0
2012-11-27T04:06:55.790Z
I think the question is interesting, but at best it will generate a list of answers. Should it be CW ?
Suresh Venkat
CC BY-SA 3.0
2012-11-27T07:48:51.780Z
That is true, I completely agree. There is no definitive answer for sure, but I'm still hoping for interesting answers.
Dimitris
CC BY-SA 3.0
2012-11-27T14:46:26.367Z
The quadratic traveling salesman problem amounts to a non-convex quadratic program with integrality constraints. See http://www.tu-chemnitz.de/mathematik/preprint/2011/PREPRINT_08.pdf
Dominique
CC BY-SA 3.0
2012-11-28T12:39:23.697Z
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
<graph-theory><optimization><spectral-graph-theory>
Which problems in graph theory can be stated as quadratic programs?
Dimitris
# Which problems in graph theory can be stated as quadratic programs?

(Asked by: username_0 on 2012-11-27)

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}$

( <http://www.eecs.berkeley.edu/~prasad/Files/spectralprofile.pdf> )

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?

**Tags:** graph-theory, optimization, spectral-graph-theory

> **Comments:**
> **username_1**: I think the question is interesting, but at best it will generate a list of answers. Should it be CW ?  
> **username_0**: That is true, I completely agree. There is no definitive answer for sure, but I'm still hoping for interesting answers.  
> **username_2**: The quadratic traveling salesman problem amounts to a non-convex quadratic program with integrality constraints. See http://www.tu-chemnitz.de/mathematik/preprint/2011/PREPRINT_08.pdf  
> **username_3**: 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.  

---

## 0 answers

