Inferring a graph from path frequency

详细信息	查看全文 | 推荐本文 |

• 作者：Tatsuya Akutsu^a ; ^{takutsu@kuicr.kyoto-u.ac.jp} ; Daiji Fukagawa^b ; ^{dfukagaw@mail.doshisha.ac.jp} ; Jesper Jansson^c ; ^{Jesper.Jansson@ocha.ac.jp} ; Kunihiko Sadakane^d ; ^{sada@nii.ac.jp}
• 关键词：Kernel method ; Graph algorithms ; Feature vector ; Pre-image
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：July, 2012
• 卷：160
• 期：10-11
• 页码：1416-1428
• 文件大小：425 K

摘要

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied.