Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$. Proof that vertex-minors of complete graphs are complete, star, or edgeless: From a complete graph, vertex deletion gives a complete graph and local complementation gives a star graph. From a star graph, deletion of the central ...


Maybe this will give ideas for a faster algorithm: Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm. Proof. Here's the algorithm: Using binary search over the $O(n^2)$-pairwise distances $\{d(u,w) : u, w\in V\}$, find the minimum radius $r$ such that the graph $G_r=(V, E_r)$ is bipartite, where $E_r = E \cup\{(u,w) : d(u, w) > r\}$. ...


I wrote an implementation of this algorithm here: https://github.com/geodavic/poly_factor There is also a public API and a website to test it out. See the README.

Only top voted, non community-wiki answers of a minimum length are eligible