3
$\begingroup$

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.$?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?. $\endgroup$ – Brout Apr 25 '18 at 13:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 26 '18 at 5:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.