2024-05-29T08:02:27Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001759922024-03-29T05:26:34Z01164:02592:08452:08957
A Note on the Spanning Subgraph Isomorphism ProblemA Note on the Spanning Subgraph Isomorphism Problemenghttp://id.nii.ac.jp/1001/00175958/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=175992&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.Department of Information and Communications Engineering Tokyo Institute of TechnologyDepartment of Information and Communications Engineering Tokyo Institute of TechnologyDepartment of Information and Communications Engineering Tokyo Institute of TechnologyKenji, IchikawaSatoshi, TayuShuichi, UenoWe consider the subgraph isomorphism problem of two graphs which is to decide if a pattern graph is isomorphic to a subgraph of a base graph. It is known that the problem is NP - complete if the pattern and base graphs are bipartite permutation graphs with the same number of vertices. We show that the problem is NP - complete even if the pattern graph is an n - vertex tree of pathwidth at most 2 and the base graph is an n - vertex bipartite permutation graph.We consider the subgraph isomorphism problem of two graphs which is to decide if a pattern graph is isomorphic to a subgraph of a base graph. It is known that the problem is NP - complete if the pattern and base graphs are bipartite permutation graphs with the same number of vertices. We show that the problem is NP - complete even if the pattern graph is an n - vertex tree of pathwidth at most 2 and the base graph is an n - vertex bipartite permutation graph.AN1009593X研究報告アルゴリズム（AL）2016-AL-16015162016-11-172188-85662016-11-15