TIFR CSE 2013 | Part B | Question: 15

Question

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$?

• A. $O (1)$
• B. $O (\log \log n)$ but not $O (1)$
• C. $O (\log n)$ but not $O (\log \log n)$
• D. $O \left(\sqrt{n}\right)$ but not $O (\log n)$
• E. $O (n)$ but not $O \left(\sqrt{n}\right)$

Comments

https://gateoverflow.in/29348/tifr-2013-b-15

---

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. 

---

@MiNiPanda 

can we somehow relate this to Dirac's / Ore's theorem ?

Answer 1

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

Comments

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 ?

Answer 2

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.