Inferring a graph from path frequency

Tatsuya Akutsu, Daiji Fukagawa, Jesper Andreas Jansson, Kunihiko Sadakane

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)1416-1428
Number of pages13
JournalDiscrete Applied Mathematics
Volume160
Issue number10-11
DOIs
Publication statusPublished - 1 Jul 2012
Externally publishedYes

Keywords

  • Feature vector
  • Graph algorithms
  • Kernel method
  • Pre-image

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this