Breaking intractability of spanning caterpillar tree problem: A logical approach

Document Type : Original Article

Author

Algoreen Software Ltd. Auckland, New Zealand

Abstract

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].

Keywords

Main Subjects

References

[1] S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, J. Algorithms, 12 (1991), p. 308–340.
[2] B. Courcelle, Graph rewriting: An algebraic and logic approach, in Formal Models and Semantics, Elsevier, 1990, pp. 193–242.
[3] , The monadic second-order logic of graphs. i. recognizable sets of finite graphs, Information and compu[1]tation, 85 (1990), pp. 12–75.
[4] M. Csur˝ os, J. A. Holey, and I. B. Rogozin ¨ , In search of lost introns, Bioinformatics, 23 (2007), pp. i87– i96.
[5] R. G. Downey and M. R. Fellows, Parameterized complexity, Springer Science & Business Media, 2012.
[6] S. El-Basil, Caterpillar (gutman) trees in chemical graph theory, Advances in the theory of Benzenoid hydrocarbons, (1990), pp. 273–289.
[7] H. B. Enderton, A mathematical introduction to logic, Elsevier, 2001.
[8] P. Hlinenˇ y, S.-i. Oum, D. Seese, and G. Gottlob ` , Width parameters beyond tree-width and their applcations, The computer journal, 51 (2008), pp. 326–362.
[9] M. Khosravani, Searching for optimal caterpillars in general and bounded treewidth graphs, PhD thesis, ResearchSpace, Auckland, 2011.
[10] A. Lozano, R. Y. Pinter, O. Rokhlenko, G. Valiente, and M. Ziv-Ukelson, Seeded tree alignment, IEEE/ACM transactions on Computational Biology and Bioinformatics, 5 (2008), pp. 503–513.
[11] M. Numan, A. Nawaz, A. Aslam, and S. I. Butt, Hosoya polynomial for subdivided caterpillar graphs, Combinatorial Chemistry & High Throughput Screening, 25 (2022), pp. 554–559.
[12] J. Tan and L. Zhang, The consecutive ones submatrix problem for sparse matrices, Algorithmica, 48 (2007), pp. 287–299.
AUT Journal of Mathematics and Computing
Volume 3, Issue 2
September 2022
Pages 147-151

Files

Share

How to cite

Statistics