Presentation	2005-04-18 On the Complexity of Inferring a Graph from Path Frequency Tatsuya AKUTSU, Daiji FUKAGAWA,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	We consider the problem of inferring a graph (and a sequence) from the numbers of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs in machine learning : to reconstruct a graph from its feature space representation. We show that this problem can be solved in polynomial time of the size of an output graph if graphs are trees of bounded degree and the lengths of given paths are bounded by a constant. On the other hand, we show that this problem is strongly NP-complete even for planer graphs of bounded degree.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	graph inference / path frequency / pre-image / strongly NP-complete
Paper #	COMP2005-7
Date of Issue

Conference Information
Committee	COMP
Conference Date	2005/4/11(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On the Complexity of Inferring a Graph from Path Frequency
Sub Title (in English)
Keyword(1)	graph inference
Keyword(2)	path frequency
Keyword(3)	pre-image
Keyword(4)	strongly NP-complete
1st Author's Name	Tatsuya AKUTSU
1st Author's Affiliation	Bioinformatics Center, Institute for Chemical Research, Kyoto University()
2nd Author's Name	Daiji FUKAGAWA
2nd Author's Affiliation	Graduate School of Informatics, Kyoto University
Date	2005-04-18
Paper #	COMP2005-7
Volume (vol)	vol.105
Number (no)	7
Page	pp.pp.-
#Pages	7
Date of Issue