First time here? Checkout the FAQ!
+5 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)$
asked in Algorithms by Veteran (38.7k points)   | 236 views

I have one doubt in statement -->

S of size at most n/2 has at least 1.5|S|-many neighbors.

Let us say S = n/2 then it has 3/2(n) neighbor but n < = (1/2)n + (3/2)n is a contradiction. Please correct me if i am wrong. 

1 Answer

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

answered by Veteran (16.2k points)  

it says n/2 can have at least 1.5(s) which means at most this graph can become complete graph, and in that case path length will be O(n).

 how does it mean that " 1.5(s) " mean complete graph ?


at least 1.5(s), at most it can be anything. 1.5(s) is lower bound ex: if we consider n/2 set then it will have at least n/4 neighbors, whereas these n/4 neighbors will surely have at least 2(n/4) neighbors
So, according to you O(n) should be correct ?

Related questions

Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points

25,991 questions
33,561 answers
31,029 users