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?

  • 4
    $\begingroup$ I think the question is interesting, but at best it will generate a list of answers. Should it be CW ? $\endgroup$ Nov 27, 2012 at 4:06
  • $\begingroup$ That is true, I completely agree. There is no definitive answer for sure, but I'm still hoping for interesting answers. $\endgroup$
    – Dimitris
    Nov 27, 2012 at 7:48
  • 1
    $\begingroup$ 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 $\endgroup$
    – Dominique
    Nov 27, 2012 at 14:46
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 28, 2012 at 12:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.