Presentation 2016-11-25
On the Complexity of Finding a Largest Common Subtree of Trees
Hiroki Katsumata, Satoshi Tayu, Shuichi Ueno,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) The largest common subtree problem (LCST) is to find a tree with the maximum number of edges that is a subtree of all the input $N$ trees. It has been known that LCST can be solved in polynomial time if $N=2$, while LCST is NP-hard if $N>2$. The paper shows that LCST is NP-hard even if $N>2$ and the pathwidth of every input tree is one. We also show that LCST is NP-hard even if $N=3$ and the pathwidth of every input tree is two, while LCST is solvable in polynomial time if $N=O(1)$ and the pathwidth of every input tree is one.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) caterpillarcommon subtreeNP-hardpathwidthpolynomial time algorithmtree
Paper # CAS2016-70,MSS2016-50
Date of Issue 2016-11-17 (CAS, MSS)

Conference Information
Committee MSS / CAS / IPSJ-AL
Conference Date 2016/11/24(2days)
Place (in Japanese) (See Japanese page)
Place (in English) Kobe Institute of Computing
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair Satoshi Yamane(Kanazawa Univ.) / Toshihiko Takahashi(Niigata Univ.)
Vice Chair Morikazu Nakamura(Univ. of Ryukyus) / Mitsuru Hiraki(Renesas)
Secretary Morikazu Nakamura(Yamaguchi Univ.) / Mitsuru Hiraki(Toshiba) / (Tohoku Univ.)
Assistant Hideki Kinjo(Okinawa Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi)

Paper Information
Registration To Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Circuits and Systems / Special Interest Group on Algorithms
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) On the Complexity of Finding a Largest Common Subtree of Trees
Sub Title (in English)
Keyword(1) caterpillarcommon subtreeNP-hardpathwidthpolynomial time algorithmtree
1st Author's Name Hiroki Katsumata
1st Author's Affiliation Tokyo Institute of Technology(Tokyo Tech)
2nd Author's Name Satoshi Tayu
2nd Author's Affiliation Tokyo Institute of Technology(Tokyo Tech)
3rd Author's Name Shuichi Ueno
3rd Author's Affiliation Tokyo Institute of Technology(Tokyo Tech)
Date 2016-11-25
Paper # CAS2016-70,MSS2016-50
Volume (vol) vol.116
Number (no) CAS-315,MSS-316
Page pp.pp.89-92(CAS), pp.89-92(MSS),
#Pages 4
Date of Issue 2016-11-17 (CAS, MSS)