The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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$?

  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 (42.9k points) | 250 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

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

answered by Veteran (16.9k 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,156 questions
36,980 answers
34,822 users