[1] Let $p:=max\{1\cdot x:x\in \mathrm{TH}(G\left)\right\}$ and $k:=max\{1\cdot x:x\in \mathrm{TH}(\stackrel{\u203e}{G}\left)\right\}$. We can find (close enough)
estimates of these integers in polytime, using the ellipsoid
algorithm to optimize over the theta body. Then $p$ will be our
"proxy" for the maximum stable set size $\alpha \left(G\right)$ and $k$ the
proxy for the maximum clique size $\omega \left(G\right)$. 
[2] If $\leftV\right(G\left)\right\ne \mathrm{kp}+1$
then $G$ is not a $(p,k)$partitionable graph.

[3] Potatope${}^{*}$ Slicing Proposition:
If $G$ is $(p,k)$partitionable, then ${\mathrm{TH}}_{p}\left(G\right):=\mathrm{TH}\left(G\right)\cap \{x:1\cdot x=p\}$ is a simplex with integral vertices.

[4] The proposition is the heart of the algorithm. It is
obvious for minimally imperfect graphs and the proof is easy for
partitionable graphs (it uses the same ideas of Bland, Huang,
Trotter and Padberg). We now use the ellipsoid algorithm to either
find affinely independent integral vectors ${a}_{1},{a}_{2},\dots {a}_{\leftV\right(G\left)\right}$ in ${\mathrm{TH}}_{p}\left(G\right)$ or show it has a fractional extreme point.
(This algorithm is very similar to several routines in Gr\"otschel,
Lov\'asz, Schrijver.) Similarly, we either deduce
nonpartitionability of $G$, or we find integer vectors ${b}_{1},{b}_{2},\dots $ in ${\mathrm{TH}}_{k}\left(\stackrel{\u203e}{G}\right)$. 
[5] We may now determine partitionability as follows. Let $A$
be the matrix whose ${i}^{\mathrm{th}}$ row is ${a}_{i}$. For each ${a}_{i}$, find
some $j$ such that ${a}_{i}\cdot {b}_{j}=0$  if there is no such, then
$G$ is not partitionable. Let ${b}_{j}$ be the ${i}^{\mathrm{th}}$ column of a
second matrix $B$. Finally, if $AB=JI$, then $G$ is $(p,k)$
partitionable. Otherwise it is not. 