4
$\begingroup$

I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.

A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.

The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.

Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length >1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.

Improve this question
$\endgroup$
3
  • $\begingroup$ Take care that your runtime does not yet hold for all NO-instances. $\endgroup$
    – Raphael
    Commented Oct 5, 2014 at 17:44
  • $\begingroup$ @Raphael are you referring to disconnected graphs? I'd check for those by testing if all vertices have been marked after the first DFS run (with random starting vertex). Should not hurt the runtime. Or is there another NO-instance I didn't think of? $\endgroup$
    – Jorge
    Commented Oct 5, 2014 at 18:21
  • $\begingroup$ Take the complete graph. You say it yourself: BFS and DFS both take time $O(n + m)$ so if $m \in \omega(n)$ (definitely a NO-instance, the graph can't by cycle-free) your algorithm is too slow. So you need to make a small tweak. (You seem to address this issue partly, but not yet convincingly, in the comments on Juho's answer.) $\endgroup$
    – Raphael
    Commented Oct 6, 2014 at 5:07

1 Answer 1

Reset to default
5
$\begingroup$

When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid.

In other words, we can first prove that caterpillars are such trees that when you delete all the leaves and incident edges, you are left with a path graph. This immediately suggest a simple linear time algorithm: check that your input graph is a tree, remove all the leaves, and check that you have a path.

In fact, I suggest you divide your problem into 3 subtasks you can work on independently:

  1. Implement a function that outputs YES/NO based on whether the input graph is a tree.
  2. Implement a function that removes all the leaves and the edges incident to them from the input graph.
  3. Implement a function that outputs YES/NO based on whether the input graph is a path.
Improve this answer
$\endgroup$
7
  • $\begingroup$ so, you suggest something like this? 1: run DFS and if a vertex in the adjcency list has already been marked as "visted", abort (cycle found). Also mark any vertex that has 0 others in it's adjacency list as "leaf". 2: remove all vertices v marked "leaf" (and I suppose also the edges(x,v)). 3: run over it again and check if it is a path (i.e., each vertex has at most one adjacent) $\endgroup$
    – Jorge
    Commented Oct 5, 2014 at 15:18
  • $\begingroup$ @Jorge You already know the tasks you need to do, and were able to describe an approach to solve them. Have confidence in yourself! What do you think? Do you see a problem? (Hint: OK, you know what a tree is. I'm not sure I understand your definition of a leaf (it has exactly 1 neighbor, not 0 as you seem to imply). Also, in a path, does every vertex really have at most 1 adjacent vertex?) $\endgroup$
    – Juho
    Commented Oct 5, 2014 at 15:56
  • $\begingroup$ Sorry about that, my definitions were bad indeed! I meant to say that a leaf has 0 children (1 neighbour). And of course for task 3 I was a bit blind. Each vertex in a path is allowed to have a max of 2 neighbours. Thanks a lot for your help. If you can clear up one little remaining uncertainty for me, will close this question then and mark it as answered: $\endgroup$
    – Jorge
    Commented Oct 5, 2014 at 16:21
  • $\begingroup$ After task 1 we are working with a tree, so traversing in O(|V|) is easy. However, before this (in step 1), the input graph might be complete (we do not yet know if it even is a tree), thus resulting in O(|V|+|E|) complexity for DFS. Can we simply argue that if the graph is not a tree, we detect that and abort "early enough" to comply with the given O(|V|)? I'd say "yes", since we can detect cycles in O(n) because at most n-1 edges are tree edges. So if we do not detect cycles, the given graph is a tree and we are golden! Is this explanation regarding runtime complexity correct? $\endgroup$
    – Jorge
    Commented Oct 5, 2014 at 16:23
  • $\begingroup$ @Jorge If we can detect cycles in $O(n)$ time, and a tree is defined to be acyclic, I agree we are golden. (Check and/or prove these facts hold). $\endgroup$
    – Juho
    Commented Oct 5, 2014 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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