4
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – daniello Jul 12 '18 at 16:19
  • $\begingroup$ @daniello Many thanks. Do you know any algorithms which are good for traversing all connected subgraph of size k? $\endgroup$ – Thomas Edison Jul 12 '18 at 21:53
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 12 '18 at 22:42
  • $\begingroup$ yeah. I want to know which might be the best exponential time algorithm or any good heuristic algorithms $\endgroup$ – Thomas Edison Jul 12 '18 at 23:10
  • 1
    $\begingroup$ 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? $\endgroup$ – C Komus Jul 17 '18 at 9:52
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.