Membership in moment cones and quiver semi-invariants for bipartite quivers

Let $Q$ be a bipartite quiver with vertex set $Q_0$ such that the number of arrows between any two source and sink vertices is constant. Let $\beta=(\beta(x))_{x \in Q_0}$ be a dimension vector of $Q$ with positive integer coordinates, and let $\Delta(Q, \beta)$ be the moment cone associated to $(Q, \beta)$. We show that the membership problem for $\Delta(Q, \beta)$ can be solved in strongly polynomial time. As a key step in our approach, we first solve the polytopal problem for semi-invariants of $Q$ and its flag-extensions. Specifically, let $Q_{\beta}$ be the flag-extension of $Q$ obtained by attaching a flag $\mathcal{F}(x)$ of length $\beta(x)-1$ at every vertex $x$ of $Q$, and let $\widetilde{\beta}$ be the extension of $\beta$ to $Q_{\beta}$ that takes values $1, \ldots, \beta(x)$ along the vertices of the flag $\mathcal{F}(x)$ for every vertex $x$ of $Q$. For an integral weight $\widetilde{\sigma}$ of $Q_{\beta}$, let $K_{\widetilde{\sigma}}$ be the dimension of the space of semi-invariants of weight $\widetilde{\sigma}$ on the representation space of $\widetilde{\beta}$-dimensional complex representations of $Q_{\beta}$. We show that $K_{\widetilde{\sigma}}$ can be expressed as the number of lattice points of a certain hive-type polytope. This polytopal description together with Derksen-Weyman's Saturation Theorem for quiver semi-invariants allows us to use Tardos's algorithm to solve the membership problem for $\Delta(Q,\beta)$ in strongly polynomial time.