The scenario at hand that I would like to solve is a maximization problem where each vertex in the connected un-directed graph has a value. However, each edge and vertex also has a cost.
Given a starting vertex and a cost budget, is there a recommended algorithm or approach to find the connected subgraph which maximizes the vertex value (including the starting vertex) ?
This is NP-hard because you could use an algorithm for this to solve the Steiner tree problem in graphs by setting the value for each terminal to be 1, the cost for each vertex to be 0, and the cost for each edge to be 1. There is a Steiner tree with weight k if and only if your algorithm with a cost budget of k is able to capture the value from all the terminals.
It may help to investigate the literature for Steiner trees to get some ideas for approximate solution ideas.