The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+6 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)$

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

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,156 questions

36,980 answers

92,147 comments

34,822 users