Lower bound for the maximum number of vertices of a connected rooted sub-digraph of a simple acyclic digraph

Question

Given a simple directed acyclic graph with $n$ vertices and $m$ edges, we get the maximum number of vertices over all connected rooted sub-digraphs of it. Connected rooted sub-digraph means here that there is a path from the root vertex to any other vertex.

Is there any known result that give a lower bound for the maximum number of vertices of a connected rooted sub-digraph as a function of $n$ and $m$?

I would be satisfied also with an answer to this subproblem: what is the minimum $m$ as a function of $n$ that guarantees a connected rooted sub-digraph with at least $n/2$ vertices?

To be more clear with an example, in this digraph the maximum number of vertices is $6$ obtained with the connected rooted sub-digraph with root vertex labeled with $7$ and vertices $7$, $11$, $8$, $2$, $9$, $10$. I want to get a lower bound over all possible digraphs with $n$ vertices and $m$ edges.

EDIT

Regarding the subproblem, I believe that it is possible to build a digraph where node $1$ is the head of $n-1$ arcs from the other $n-1$ nodes (tails). Then we choose another node $2$ among these $n-1$ nodes to be the head of $n-2$ arcs from the remaining $n-2$ nodes (all nodes but $1$ and $2$). We continue in a similar way with nodes $3,4,\ldots,\lceil n/2 \rceil$. At this point we have the desired number of vertices in a connected rooted sub-digraph. Therefore if $f(n)$ is the minimum number of edges that guarantees a connected rooted sub-digraph with at least $n/2$ vertices then:

$$f(n) \ge -3/16 - 3/16 (-1)^{1 + n} - n/8 + 1/8 (-1)^{1 + n} n + 3 n^2/8$$

where the RHS counts the edges of the graphs constructed as described above, and the formula has been obtained with the help of OEIS.

However, how can we turn the inequality into an equality?

Answer 1

A few definitions and ideas that may help to find some answers. It's too much to be a comment and it's not an "answer" i'm afraid.

Let $\lambda$ be the lower bound you're looking for. First, assign to each node a level $l$ in the following way:

• if $v$ is a sink $l(v) = 0$
• $l(v) = i$ if the out-neighbor of lowest level of $v$ is $i-1$.

Observe that the size of the maximum rooted connected subgraph is at least the highest level of the node +1, so now the idea would be to try to create graphs with as much edges as possible while keeping the highest level low.

Let then $V_i$ the nodes of level $i$ and $E_{i,j}$ be the edges from level $i$ to level $j$. Then a few observations:

• if $m=0$ trivially $\lambda = 1$.
• if $m\le n-1$ then $\lambda =2$: consider a star-like pattern $|V_0| =1$, $|V_1| = n-1$.
• with $m\le 2n-6$ I have a construction that would suggest $\lambda = 3$: consider $|V_0|= 2$, $|V_2|=1$ and $V_1 =V_1^1 \cup V_1^2$. Vertices in $V_1^1$ have a single neighbor in $V_0$, while vertices in $V_1^2$ have two neighbors in $V_0$. The only neighbors to the vertex of $V_2$ are $V_1^1$. By chosing $|V_1^1| = 1$, you may have $2 + 2(n-4) = 2n-6$ edges. Clearly in this construction the maximum connected subgraph has only $3$ vertices. However, I do not know if you can find a graph holding more edges.
• using a similar construction i would say that $m\le k-1+(k-1)(n-2k-1)$ gets you $\lambda = k$. Basically you have a vertex of level $k-1$ having a path of length $k$ up to a sink, while all the path is completely separated from the rest of the graph. Then, you have an additional $k-1$ vertex of level 0 and $n-2k-1$ vertices of level $1$. You can put up to $(k-1)(n-2k-1)$ edges between these two groups, while keeping the biggest rooted connected subgraph of size at most $k$.