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!

Improve this question
$\endgroup$
7
  • 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, 2018 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, 2018 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, 2018 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, 2018 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$
    – Christian Komusiewicz
    Jul 17, 2018 at 9:52

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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