Amirkabir University of Technology AUT Journal of Mathematics and Computing 2783-2449 3 2 2022 09 01 Breaking intractability of spanning caterpillar tree problem: A logical approach 147 151 4907 10.22060/ajmc.2022.21716.1104 EN Masoud Khosravani Algoreen Software Ltd. Auckland, New Zealand Journal Article 2022 08 02 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 monadic-second order logical expression. The value of this approach reflected better by the fact that finding a spanning caterpillar in a graph is an NP-complete problem [9]. https://ajmc.aut.ac.ir/article_4907_0e4ceef65add6cf21c0f3f9da53b71c0.pdf