<p>This is a self-plug but in the paper <a href="https://cms.uni-marburg.de/fb12/arbeitsgruppen/algorithmik/papers/mu-clique-theory-long-web.pdf" rel="nofollow noreferrer">An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems</a> 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 <a href="http://www.cambridge.org/de/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/art-mathematics-coffee-time-memphis" rel="nofollow noreferrer">The Art of Mathematics - Coffe Time in Memphis</a>.</p>

<p>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. </p>

CC BY-SA 4.0
2018-07-17T09:51:12.063Z
2018-07-17T09:51:12.063Z
Christian Komusiewicz
<blockquote>
  <p>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. </p>
</blockquote>

<p>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 <a href="https://en.wikipedia.org/wiki/Color-coding" rel="noreferrer">color-coding</a> 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!</p>

CC BY-SA 4.0
2018-07-12T16:19:22.363Z
The complexity of the problem depends heavily on the function $f$. For example, if $f(V_T) = |E_T|$ the problem generalizes $k$-clique and therefore has no $f(k)n^{o(k)}$ time algorithm assuming the ETH.
daniello
CC BY-SA 4.0
2018-07-12T21:53:10.807Z
@daniello Many thanks. Do you know any algorithms which are good for traversing all connected subgraph of size k?
Thomas Edison
CC BY-SA 4.0
2018-07-12T22:42:13.533Z
What do you mean by traversing all subgraphs?  If you mean enumerating all of them, there is no good algorithm, because there are (in general) exponentially many subgraphs, so any such algorithm has to take exponential time in general.
D.W.
CC BY-SA 4.0
2018-07-12T23:10:22.787Z
yeah. I want to know which might be the best exponential time algorithm or any good heuristic algorithms
Thomas Edison
CC BY-SA 4.0
2018-07-17T09:52:50.620Z
I tried to give an answer that I feel appropriate for the theoretical aspect of your question below, but it seems you are also interested in a fast implementation of such an algorithm?
Christian Komusiewicz
CC BY-SA 4.0
2018-07-17T10:04:50.793Z
@CKomus Yeah, fast/heuristic algorithm is the most important because I want to compute it for a real world problem.
Thomas Edison
CC BY-SA 4.0
2018-07-17T10:49:58.897Z
In that case, a good starting point for enumeration could be the algorithm described in Kavosh: a new algorithm for finding network motifs, https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-10-318.
Christian Komusiewicz
<ds.algorithms><reference-request><graph-theory><graph-algorithms>
Fast algorithm to find a maximum connected subgraph of k vertices
Thomas Edison
# Fast algorithm to find a maximum connected subgraph of k vertices

(Asked by: username_0 on 2018-07-12)

> 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](https://en.wikipedia.org/wiki/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!

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: The complexity of the problem depends heavily on the function $f$. For example, if $f(V_T) = |E_T|$ the problem generalizes $k$-clique and therefore has no $f(k)n^{o(k)}$ time algorithm assuming the ETH.  
> **username_0**: @username_1 Many thanks. Do you know any algorithms which are good for traversing all connected subgraph of size k?  
> **username_2**: What do you mean by traversing all subgraphs?  If you mean enumerating all of them, there is no good algorithm, because there are (in general) exponentially many subgraphs, so any such algorithm has to take exponential time in general.  
> **username_0**: yeah. I want to know which might be the best exponential time algorithm or any good heuristic algorithms  
> **username_3**: I tried to give an answer that I feel appropriate for the theoretical aspect of your question below, but it seems you are also interested in a fast implementation of such an algorithm?  
> **username_0**: @CKomus Yeah, fast/heuristic algorithm is the most important because I want to compute it for a real world problem.  
> **username_3**: In that case, a good starting point for enumeration could be the algorithm described in Kavosh: a new algorithm for finding network motifs, https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-10-318.  

---

## 1 answers

### Answer by username_3 on 2018-07-17. Score: 3

This is a self-plug but in the paper [An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems](https://cms.uni-marburg.de/fb12/arbeitsgruppen/algorithmik/papers/mu-clique-theory-long-web.pdf) 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](http://www.cambridge.org/de/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/art-mathematics-coffee-time-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.


---

