breaking intractability of spanning caterpillar tree problem: a logical approach

In this paper we pursue a logical approach to prove that the optimisation problem of finding a spanning caterpillar tree in a graph has polynomial algorithm for bounded tree width graphs. a caterpillar (tree) is a tree with the property that if one removes all its leaves only a path is left. to this end we use courcelle’s theorem and we show how one can present the spanning caterpillar tree problem by using monadicsecond order logical expression. the value of this approach reflected better by the fact that finding a spanning caterpillar in a graph is an npcomplete problem.