1
$\begingroup$

Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices).

What I was thinking at first is that any vertex $v$ that has at least two neighbors could indicate a $P_3$ but it wouldn't be induced since these two neighbors might be connected. So that would mean I would have to iterate over all pairs of neighbors of every vertex to determine if they're connected and I would exceed the requested runtime. Plus, that way I would actually be able to not only tell if there's a $P_3$ but also find it, which kinda tells me this isn't what I should be doing.

Any suggestions? Or hints?

$\endgroup$
3
$\begingroup$

Without loss of generality, we can assume that the graph is connected and contains at least three vertices. If the graph is a clique, it doesn't contain an induced $P_3$. What happens if it is not a clique?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.