# Finding a cutting plane that splits a polyhedron evenly

Say we have a polyhedron in standard form:

\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same? (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

### Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.

• Shouldn't one be able to prove this is an NP-hard problem? Sep 8, 2011 at 18:38
• Thanks @Peter. A proof would be great. That said, I presume the problem is hard, and I think I am more interested in heuristics or approximation algorithms. The motivation behind the idea of restricting the types of cuts was in part to see if there are easier variations of the general problem for which we already know a solution or an approximation algorithm. Sep 8, 2011 at 18:47
• How about something along these lines (not sure if it works) - We know counting the number of maximum bipartite matchings is #P-hard. We also know that a linear program to find a maximum bipartite matching is totally unimodular and thus any corner point/basic feasible solution is integral. For a maximum bipartite matching problem, find the value of the matching. Construct a linear program with the constraint that any solution has to have the optimal value. Then every corner point is a matching. Being able to repeatedly divide evenly means you should be able to count the number of matchings.
– Opt
Sep 8, 2011 at 19:21
• Never mind. One would also have to be able to count the number of vertices added by the cutting plane.
– Opt
Sep 8, 2011 at 19:55