Efficiently computing or approximating the VC-dimension of a neural network My goal is to solve the following problem, which I have described by its input and output:
Input:
A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m &gt; n \geq 1$).
Output:
The VC-dimension (or an approximation of it) for the neural network with topology $G$.
More specifics:

Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
The learning algorithm is fixed (say backward-propagation).
The $n$ source nodes are the input neurons and can only take strings from $\{-1,1\}^n$ as input.
The sink node is the output unit. It outputs a real value from $[-1,1]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

Question
Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?
Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?
Notes
I asked a similar question on stats.SE but it generated no interest.
If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.

It's not strictly an answer to your question, but it might help you on the way. The result is due to Baum and Haussler (1989).