Fast algorithm to find a maximum connected subgraph of k vertices Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)$ is maximum. 


This problem is a generalization of the maximum connected subgraph of size $k$, which can be solved by means of integer linear programming. Unfortunately, my objective function $f$ is nonlinear. One can enumerate all connected subgraphs of size $k$ and take one with the largest objective value. However, I think this approach is very slow. I also tried the color-coding technique but it is slow too. Does anyone know any best/fast algorithms to solve this problem in a such general scheme? Thank you in advance!
This is a self-plug but in the paper An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems we consider exactly problems such as the one that you describe. The running time of the algorithm is $O((e\cdot (\Delta-1))^k\cdot (\Delta+k)\cdot n)\cdot T(n,k)$ where $T(n,k)$ is the time needed for evaluating the objective function $f$. Here, $\Delta$ is the maximum degree in the input graph. The algorithm is based on enumeration of connected subgraphs of order $k$. Observe that a graph may have $\Omega((e\cdot (\Delta-1))^k\cdot n/k)$ such induced subgraphs. The bounds for the number of connected induced subgraphs are based on a result of Bollobás in The Art of Mathematics - Coffe Time in Memphis.

Thus, to further improve on the running time above, one either needs to consider other structural properties of the input graph or to exploit some properties of $f$ that make it possible to avoid enumerating all connected induced subgraphs.