The Art Gallery Guardian

Induced subgraph with constant diameter


Let TT be a rooted tree on vertices VV. TvT_v to be the subtree of TT rooted at vv. Let GTk\mathbb{G}_T^k contains all graphs GG on VV with the property that for every vv, the diameter of G[V(Tv)]G[V(T_v)] is at most kk.

Let GTkG_T^k to be the graph in GTk\mathbb{G}_T^k with minimum number of edges(break ties arbitrarily), what can we say about the number of edges in GT2G_T^2?

Theorem1

If TT has nn vertices, then GT2G_T^2 have O(nlogn)O(n \log n) edges.

Proof

Let G|G| to be the number of vertices in G|G|.

We construct a graph GGT2G\in \mathbb{G}_T^2 recursively. For each TvT_v, we construct a GvG_v on the same vertex set such that it has the property there exist a vertex that connects to all other vertex in GvG_v. Call such vertex a golden vertex of GvG_v. GvG_v would be a union of all GuG_u, where uu is a child of TvT_v with some extra edges. Let uu to be the child of vv such that GuG_u has the maximum number of vertices (break ties arbitrarily), and uu' is the golden vertex of GuG_u, then we add edges from uu' to all other vertices in GvG_v. Let G=GrG=G_r, where rr is the root of TT.

The distance between any two vertex is at most 22 in G[V(Tv))]=GvG[V(T_v))]=G_v for all vv, because any two vertex is connected by a golden vertex in the induced subgraph.

The number of edges is at most O(nlogn)O(n\log n). Label vv with Tv|T_v|. The number of edges added at the step to build GvG_v is TvTu|T_v|-|T_u|, where GuG_u contains the golden vertex, and it also have the most number of vertices among all GcG_c where cc is a child of vv in TT. Sum of all labels over the tree TT except the heaviest child is O(nlogn)O(n\log n) using analysis akin to heavy-light decomposition.

This bound is in fact best possible by considering a complete binary tree and the following lemma:

Lemma2

If G=(V,E)G=(V,E) is a graph with diameter 22, then for any cut δ(U)\delta(U), we have δ(U)min(U,VU)|\delta(U)|\geq min(|U|,|V\setminus U|).

Proof

wlog, let UVU|U|\leq |V\setminus U|. If all vertex in UU has an neighbor in VUV\setminus U, then δ(U)U|\delta(U)|\geq |U| and we are done. Otherwise, there is an vertex uUu\in U has no neighbor in VUV\setminus U, then for any v∉Uv\not\in U, there is an uUu'\in U, and there is a path uuvuu'v. This implies there are at least V|V| edges in δ(U)\delta(U).

Is this the best possible for general GTkG_T^k too? Not at all. To show this, we introduce an algorithmic problem.

Problem3

Preprocess a rooted tree TT where the elements in the tree TT has weights from a semigroup (S,+)(S,+), such that we can answer the following query in kk semigroup operations.

Query Input: xx and yy where xx is an ancestor of yy.

Query Output: The sum of weights of the unique simple path between xx and yy.

Alon and Schieber showed this problem can be solved by precompute O(nλ(k,n))O(n\lambda(k,n)) path sums [???]. Where λ(k,n)\lambda(k,n) is related to the inverse Ackermann function, and λ(4,n)=O(nlogn)\lambda(4,n)=O(n\log^*n).

Theorem4

If TT has nn vertices, then GTkG_T^k have O(nλ(k,n))O(n \lambda(k,n)) edges.

Proof

A simple reduction from our tree problem by input our rooted tree TT into Alon and Schieber's algorithm. For each path sum they preprocess, we create an edge in our GG. The diameter of all GvG_v is at most 2k2k, since for any 2 vertices xx and yy, we find it's lowest common ancestor ww in TT, then there is a path of length kk from xx to ww and another of length at most kk from ww to yy.

Their paper argued an lower bound of preprocess Ω(nλk(n))\Omega(n\lambda_k(n)) path sums for a single rooted path. In our model, we can add O(n)O(n) edges is sufficient. An edge from the leaf to every other vertex, making the diameter only 22. This is because we have a lot more freedom in our diameter problem.

In their problem, their path sum is actually divide the path into kk subpaths, our path of length 22 would imply there is an overlap in the sum.

One might to think the reason we can do it in O(n)O(n) edges comes directly from in the undirected model we can traverse back from the leaf and allow overlaps. Maybe the following problem might give us an lower bound.

Problem5

Preprocess a rooted tree TT where the elements in the tree TT has weights from a semigroup (S,+)(S,+), such that we can answer the following query in kk semigroup operations.

Query Input: xx and yy where xx is an ancestor of yy and yy is a leaf.

Query Output: The sum of weights of any walk lies strictly in between xyxy and that start at xx and ends at yy.

Unfortunately, this does not give us an lower bound. Following the proof in Alon's and Schieber's paper, we can show any algorithm would need to precompute at least O(nλk(n))O(n\lambda_k(n)) paths in order to output the solution using kk semigroup operations on this particular tree: TT is a rooted tree consist of one single path of length nn, and for each vertex, we add one single dangling leaf.

Again, for this graph, we can add at most nn edges and force diameter to be at most 22. Take the lowest leaf and add edge to all other vertices. Here would be an formulation that could result an lower bound.

Problem6

Preprocess a rooted tree TT where the elements in the tree TT has weights from a semigroup (S,+)(S,+), such that we can answer the following query in kk semigroup operations.

Query Input: xx and yy where xx is an ancestor of yy.

Query Output: The sum of weights of any walk from xx to yy that lies strictly inside the subtree rooted at xx.

Finally, here is a conjecture. Instead of using tree, we use Laminar family to simplify the wording of the conjecture.

Conjecture7

For every constant kk, there exist a Laminar family XX over ground set VV of nn vertices, such that for any graph G=(V,E)G=(V,E) such that G[A]G[A] has diameter at most kk for all AXA\in X, then E=Ω(nλk(n))|E|=\Omega(n\lambda_k(n)).

If diameter is 33, then we can show there is a Ω(nloglogn)\Omega(n\log \log n) lower bound by consider the Laminar family such that a set of size nn gets partitioned into n\sqrt{n} children each with n\sqrt{n} vertices, and it is applied recursively.

The idea is at any level, say has nn elements and n\sqrt{n} subsets. A vertex is called interior if it does not connect to any vertex outside the subset, and exterior otherwise. A subset is shy if it contains a interior vertex. We show there is at least 1/5n1/5 n edges in between the subsets. If there are at least 1/2n1/2n exterior vertices, then we are done. Otherwise, there are at lease 1/2n1/2n interior vertices. We call the subsets with at least one interior vertex shy. At least n/2\sqrt{n}/2 of those subsets are shy. Consider any two distinct shy subset and pick a interior vertex from each. In order to have a distance 3 path between two interior vertices, the path has to contain two exterior vertex, one in each shy subset. But this shows if we contract all the shy subsets to one vertex, we get a clique. This means there has to be at least (n/21)2>1/5n(\sqrt{n}/2-1)^2>1/5n edges in between the subsets (for large enough nn).

Posted by Chao Xu on .
Tags: .