Given a sizable graph $G = (V, E)$, with $|V| \approx 1400$ vertices and $|E| \approx 1600$ edges, I have an optimization problem to find a connected subgraph of $G$ of size $k$ such that a given function $f$ over the subgraph is optimal. Furthermore, I have a set of undesirable vertices $U \subset V$ which do not affect the value of $f$, and desirable vertices $D = V - U$.

As a preprocessing step, I'm trying to prune $G$ by removing all undesirable vertices that will never be part of an optimal solution. A undesirable vertex has no affect on the value of $f$, but still might be included in an optimal solution if it is part of a minimal Steiner tree with desirable terminals $T \subset D$. Any vertex which is not part of any minimal Steiner tree of any subset $T \subset D$ is safe to remove.

Now, since I'm very inexperienced in this field and am having trouble finding the right literature, I'm asking for any advice or references for solving the problem of finding such vertices that are provably not part of an optimal solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.