retagged by
1,396 views
8 votes
8 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$?

  1. $O (1)$
  2. $O (\log \log n)$ but not $O (1)$
  3. $O (\log n)$ but not $O (\log \log n)$
  4. $O \left(\sqrt{n}\right)$ but not $O (\log n)$
  5. $O (n)$ but not $O \left(\sqrt{n}\right)$
retagged by

2 Answers

1 votes
1 votes

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..

1 votes
1 votes

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.

Answer:

Related questions

4 votes
4 votes
3 answers
4