<p>A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints.  In particular, they prove:</p>

<blockquote>
  <p>Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$. 
  Then $G$ contains a $k$-clique,<br>
  <strong>if and only if</strong> there exist real numbers $x_1,\ldots,x_n$ 
  that satisfy the quadratic constraint<br>
  $$\sum_{(i,j)\in E}x_ix_j \ge \frac12\left(1-\frac1k\right)$$
  together with the linear constraints $\sum_{i=1}^nx_i=1$ 
  and $x_1,\ldots,x_n\ge0$.</p>
</blockquote>

<ul>
<li>Since the $k$-clique problem is NP-hard, this implies that feasibility testing for a linear program plus a single quadratic <strong>inequality</strong> constraint is NP-hard.</li>
<li>If the graph $G$ contains a $k$-clique $C$, then for $i\in C$ we may set $x_i=1/k$ and for $i\notin C$ we may set $x_i=0$. 
Note that the resulting point $x$ satisfies all constraints in the feasibility problem with equality. 
This yields that also feasibility testing for a linear program plus a single quadratic <strong>equality</strong> constraint is NP-hard.</li>
</ul>

<p>Reference:<br>
T.S. Motzkin and E.G. Straus (1965), "Maxima for graphs and a new proof of a theorem of Turán." Canadian Journal of Mathematics 17, pp 533–540.</p>

CC BY-SA 3.0
2018-04-25T13:46:54.960Z
Does the same argument work for GI on why I cannot solve GI by just $PGP′=H$ on constraint permutation $P$ is generated by linear constraints $$\forall i: \sum_{j = 1}^n{P_{ij}} = 1$$
$$\forall j: \sum_{i = 1}^n{P_{ij}} = 1$$
$$\forall i, j: P_{ij} \geq 0$$ where $G$ and $H$ are adjacency matrices of graphs whose isomorphisms need to be tested?.
Turbo
CC BY-SA 3.0
2018-04-26T05:05:27.593Z
For a permutation matrix $P$, you can write $PG = HP$ instead of $PGP^T = H$. This gives a linear program together with the constraint you give, and you can solve it. But the solution will be a doubly stochastic matrix $P$, not necessarily a permutation matrix. While you can write a doubly stochastic $P$ as a convex combination of permutation matrices, there is no guarantee any of them will be an isomorphism.
Sasho Nikolov
CC BY-SA 3.0
2018-04-25T09:25:48.530Z
2018-04-25T09:25:48.530Z
Gamow
<p>Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ many quadratic (not necessarily convex constraints)</p>

<ol>
<li><p>equality constraints in $P$?</p></li>
<li><p>inequality constraints in $P$?</p></li>
</ol>

<blockquote>
  <p>Can $k=\Omega(poly(n))$ hold in both cases? At least can $k&gt;0$ hold at least for $1.$?</p>
</blockquote>

<cc.complexity-theory><ds.algorithms><linear-programming><polynomial-time><convex-optimization>
On complexity of linear programming with quadratic equality/inequality constraints?
Turbo
# On complexity of linear programming with quadratic equality/inequality constraints?

(Asked by: username_0 on 2018-04-25)

Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ many quadratic (not necessarily convex constraints)

1. equality constraints in $P$?
2. inequality constraints in $P$?

> Can $k=\Omega(poly(n))$ hold in both cases? At least can $k>0$ hold at least for $1.$?

**Tags:** cc.complexity-theory, ds.algorithms, linear-programming, polynomial-time, convex-optimization

---

## 1 answers

### Answer by username_1 on 2018-04-25. Score: 6 | Accepted answer

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove:

> Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$.
> Then $G$ contains a $k$-clique,  
> **if and only if** there exist real numbers $x\_1,\ldots,x\_n$
> that satisfy the quadratic constraint  
> $$\sum\_{(i,j)\in E}x\_ix\_j \ge \frac12\left(1-\frac1k\right)$$
> together with the linear constraints $\sum\_{i=1}^nx\_i=1$
> and $x\_1,\ldots,x\_n\ge0$.

* Since the $k$-clique problem is NP-hard, this implies that feasibility testing for a linear program plus a single quadratic **inequality** constraint is NP-hard.
* If the graph $G$ contains a $k$-clique $C$, then for $i\in C$ we may set $x\_i=1/k$ and for $i\notin C$ we may set $x\_i=0$.
  Note that the resulting point $x$ satisfies all constraints in the feasibility problem with equality.
  This yields that also feasibility testing for a linear program plus a single quadratic **equality** constraint is NP-hard.

Reference:  
T.S. Motzkin and E.G. Straus (1965), "Maxima for graphs and a new proof of a theorem of Turán." Canadian Journal of Mathematics 17, pp 533–540.

> **Comments:**
> **username_0**: Does the same argument work for GI on why I cannot solve GI by just $PGP′=H$ on constraint permutation $P$ is generated by linear constraints $$\forall i: \sum_{j = 1}^n{P_{ij}} = 1$$ $$\forall j: \sum_{i = 1}^n{P_{ij}} = 1$$ $$\forall i, j: P_{ij} \geq 0$$ where $G$ and $H$ are adjacency matrices of graphs whose isomorphisms need to be tested?.  
> **username_2**: For a permutation matrix $P$, you can write $PG = HP$ instead of $PGP^T = H$. This gives a linear program together with the constraint you give, and you can solve it. But the solution will be a doubly stochastic matrix $P$, not necessarily a permutation matrix. While you can write a doubly stochastic $P$ as a convex combination of permutation matrices, there is no guarantee any of them will be an isomorphism.  

---

