http://swrc.ontoware.org/ontology#TechnicalReport
A Note on the Spanning Subgraph Isomorphism Problem
en
Department of Information and Communications Engineering Tokyo Institute of Technology
Department of Information and Communications Engineering Tokyo Institute of Technology
Department of Information and Communications Engineering Tokyo Institute of Technology
Kenji Ichikawa
Satoshi Tayu
Shuichi Ueno
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.
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-160
15
1-6
2016-11-17
2188-8566