1. What is the horizontal axis on that plot? 2. By looking at the plot I would conjecture that $\alpha(n)$ converges to a constant ;-) Isn't there a more useful plot or table?

I don't think so. In Sokoban, you cannot freely move any chip as you like (as in the Question). You must go there and push from a free square on the opposite side. In the Question, the only constraint is that the chips cover distinct positions. (I am not sure if the question is polynomially solvable.)

Please state your question more precisely. $\mathbb{N}_0$ carries numerous semiring structures, like $(+,\times)$, $(\max,+)$, $(\min,+)$, $(\min,\times)$, $(\min,\max)$ etc. State that you mean linear systems of the form $Ax=Bx$ for matrices $A,B$ and an unknown vector $x$. (If this is the case) Is something known about the $(\min,\max)$ semiring, over some linearly ordered domain?

@Jernej: what do you mean by "subdivision" in "Sage simply computes the subdivision of the Laplacian matrix"? For non-empty graphs, one can remove an arbitrary row and column and compute the determinant. How does sage remove a row from the empty matrix.

There is no polynomial $g(x) \in \mathbf{Q}[x]$ such that the function $f(x,y)=g(x)+g(y)$ has the desired property. The examples on the problem statement are suggestive of such a stronger reading (and this got also me confused at first). The statement follows from the fact that if the degree of $g$ is more than 2, then the range of $g$ is not dense enough for $g(x)+g(y)$ to fill $\mathbf{Z}$; degree 2 or 1 is already excluded in Qiaochu's answer.

I wonder how sage does the calculation. The complete graph on $k$ vertices is not $k$-connected. Here, the condition that a $k$-connected graph must have at least $k+1$ vertices is usually formulated explicitly. Setting $k=1$ it would mean that not even the graph with one vertex is 1-connected (=connected). So these analogies break down when it come to small values.

I would have expected the condition $m\le n$. Is that what you mean? Or is this another version of the problem? Every line segment that is not $\pm45$ degrees, and every sufficiently smooth curve that is not a $\pm45$ degree line segment must cross a dyadic square (even with the strong definition of dyadic square). So if there are counterexamples they are pretty pathological.

Any idea how tight? Anything known about a lower bound? Can we assume the samples are independent? How is $n$ related to $d$? Apparently $n$ does not go to infinity (as it usually does in probability), since $n\ge d$ makes no sense.

1) I clarified the concept of "cost". 2) Yes I overlooked the positivity. What I said holds for the nonnegative variant. Positivity can be achieved by adding constraints $w_{ij}\ge\epsilon$ to the constraints and maximizing $\epsilon$. (After all is is a linear inequalities problem (so definitely not NP-complete)). In the network model, one can try to make a particular $w_{ij}$ positive by pushing flow around. If this works for all edges, the average of those solutions is positive on all edges. A more elegant solution identifies the arcs that have zero flow in all solutions.