Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to find the connected subgraph (not sure about this terminology) with maximum number of edges, among all the connected subgraph of $C$ that satisfy the following:

  1. includes vertex $v_1$
  2. has exactly $m$ number of vertices (including $v_1$)

By connected subgraph of $C$, I mean a subgraph of $C$, such that each pair of vertices in it are connected by a path.

  • $\begingroup$ There is only one connected component containing a vertex. It doesn't seem like what you are saying is what you really want to ask. $\endgroup$ – plop Jul 14 at 20:34
  • $\begingroup$ What I meant is: find the subset (with max edges) of the connected component, among all the possible subset of size m of the connected component. I'm not sure about the exact terminologies. $\endgroup$ – Mamun Jul 14 at 20:40
  • $\begingroup$ @plop Please see if the edited question makes sense now. $\endgroup$ – Mamun Jul 14 at 21:04
  • $\begingroup$ @Mamun All above comments have become outdated since my edit. $\endgroup$ – John L. Jul 16 at 6:04
  • $\begingroup$ @D.W, can you remove all above comments? Thanks. $\endgroup$ – John L. Jul 16 at 6:04

It's NP-hard (by reduction from clique problem).

Let $G$ be an arbitrary graph, and we want to check if there exists a clique of size $m-1$ in this graph. This problem is NP-hard. By adding $v_1$ to the graph and connecting it to all vertices in $G$, we reduce the clique problem to your problem (since clique, when exists, has the maximum number of edges).

| cite | improve this answer | |

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.