7
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ I think the question is interesting, but at best it will generate a list of answers. Should it be CW ? $\endgroup$ – Suresh Venkat Nov 27 '12 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 '12 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 '12 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$ – András Salamon Nov 28 '12 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.