2
$\begingroup$

Say I have a graph $G$ on $n$ vertices that is $P_4$-free (it has no induced paths of length 4). These are known as cographs. Note that $G$ might not be connected.

I'd like to list the induced $P_3$ in $G$. That is, I want to find the list of all vertex triples $\{a,b,c\}$ that induce a path of length 3, meaning that exactly one edge is missing between these 3.

My question is : at most how many $P_3$ will I have in the list, in big-O notation ?

An obvious upper bound is ${n \choose 3} \in O(n^3)$ induced $P_3$. However I haven't been able to construct a $P_4$-free graph having that many. So are there possibly $O(n^2)$ ?

I'd also be interested in an algorithm that finds all $P_3$ quickly.

And as a side question, should we write the plural of $P_3$ as "$P_3$s" ?

$\endgroup$
3
$\begingroup$

In the complete bipartite graph $K_{n,n}$ every vertex is the center of ${n\choose 2}$ different $P_3$'s and there are $2n$ vertices, so this certainly qualifies for $O(n^3)$.

For the algoritm I would also simply take each vertex as the center and list its neighbour pairs. Since the output has size $O(n^3)$ this must be approximately optimal.

Since I am not english I won't guess how you write the plural of $P_3$, but I do it the way you can see earlier in this answer :)

$\endgroup$
2
  • $\begingroup$ Yes thank you ! I was kind of hoping to avoid having to look at $O(n^3)$ sets of vertices but it seems it can't be avoided in general. Oh well, thanks again ! $\endgroup$ May 30 '14 at 5:29
  • $\begingroup$ I usually see the same notation: $P_3$'s. $\endgroup$ May 30 '14 at 17:41

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.