Inferring graphs from path frequency
has been studied as an important problem
which has a potential application to drug design
and elucidation of chemical structures.
Given a multiple set g of strings of labels
with length at most K,
the problem asks to find a vertex-labeled graph G
that attains a one-to-one correspondence
between g and the occurrences of labels along all paths
of length at most K in G.
In this paper, we prove that
the problem with K=1 can be formulated as a problem of finding
a loopless and connected detachment, based on
which an efficient algorithm for
solving the problem is derived.
Our algorithm also solves the problem
with an additional constraint
such that every vertex in an inferred graph is
required to have a specified degree.