Dark Mode

947 views

7 votes

Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of vertices $S$ of size at most $n/2$ has at least $1.5 |S|$-many neighbours. What is the length of a longest path in $G$?

- $O (1)$
- $O (\log \log n)$ but not $O (1)$
- $O (\log n)$ but not $O (\log \log n)$
- $O \left(\sqrt{n}\right)$ but not $O (\log n)$
- $O (n)$ but not $O \left(\sqrt{n}\right)$

0

1 vote

Here we have to find the longest path in Graph.

Let's start with 1 node(chose any one) & find the number of hops in which whole Graph is reachable i.e. all the n vertices are reachable.

From First node (say A) -

(1) within 1 hop(1 edge traversal) we can reach atleast = 3/2 nodes

{as neighbourhood of A has atleast 3/2 nodes}

(2) within 2 hops we can reach atleast $\left (\frac{3}{2} \right )^2$ nodes

(3) within 3 hops we can reach atleast $\left (\frac{3}{2} \right )^3$ nodes

and so on.. like this when our nodes reach $\left ( \frac{n}{2} \right )$ within 1 more hop we can reach upto $\left ( \frac{n}{2} \right ) * \frac{3}{2} = \frac{3n}{4}$ nodes..

uptill here we will take O(log n) hops {to reach $\frac{3n}{4}$ nodes}.

But this property is valid upto a subset of size atmost n/2 .. so, here I stuck to proceed..

Hope it helps.. Also any suggestions to proceed further are welcome..

0

0

1 vote

First we’ll understand the property $P$ that the question mentions –

Let $G = (V,E)$ be any undirected graph on $n$ nodes, the graph $G$ has property $P$ that every subset $S$ of $V$ such that $S$ having at most $\frac{n}{2}$ nodes then the closed neighbourhood of $S, N[S]$ has at least $1.5*|S|$ nodes.

That is, $(|S| = x) \land (x \le \frac{n}{2}) \implies |N[S]| = 1.5*x \implies$ the (open) neighbourhood of $S, |N(S)| = |S’| = 0.5*x$.

(A).

Consider a complete graph $K_n$ on $n$ nodes, in this graph every node has $(n-1)$ neighbours.

Closed neighbourhood of any subset $S$ of $V$ will have $n$ nodes i.e. $|N[S]| = n, \forall S \subset V$.

Therefore, $K_n$ has property $P$ and we know longest path in $K_n$ has length $n-1$.

Therefore, then length of longest path in $G$ is $O(n)$.

(B).

Lets assume, in a graph $G$ having property $P$ the length of the longest path is $O(\sqrt n)$.

That is, the length of the longest path is $k * \sqrt n$, where $k$ is some positive constant.

Now, we want every node of our graph $G$ to have maximum possible neighbours. The only way to do this is to create $\frac{\sqrt n}{k}$ connected components, each of order $k * \sqrt n$ such that each connected component is a complete subgraph.

Now, select $c$ components such that $c*k* \sqrt n \le \frac{n}{2}$, i.e. the total number of nodes in $c$ selected components is at most $\frac{n}{2}$.

Now, as per property $P$ the closed neighbourhood of this selection of nodes must have at least $1.5*c*k* \sqrt n$ nodes.

But, since any node in the $c$ components is not connected to any other node outside its own component, the closed neighbourhood of our selection will have only $c*k* \sqrt n$ nodes.

This is a contradiction.

Therefore, any graph $G$ having property $P$ cannot have largest path of length $O(\sqrt n)$.

**Answer :- E.**