Tree inclusions in windows and slices

I. Guessarian ; P. Cégielski

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 38-53

Résumé

A labelled tree $P$ is an embedded subtree of a labelled tree $T$ if $P$ can be obtained by deleting some nodes from $T$: if a node $v$ is deleted, all edges adjacent to $v$ are also deleted and replaced by edges going from the parent of $v$ (if it exists) to the children of $v$. Deciding whether $P$ is an embedded subtree of $T$ is known to be NP-complete. Given two trees (a target $T$ and a pattern $P$) and a natural number $w$, we address two problems: 1) counting the number of windows of $T$ having height exactly $w$ and containing the pattern $P$ as an embedded subtree, and 2) counting the number of slices of $T$ having height exactly $w$ and containing the pattern $P$ as an embedded subtree. Our algorithms run in time $O(|T|(w-h(P)+2)^{4|P|})$, where $|T|$ (resp., $|P|$) is the size of $T$ (resp., $P$), and $h(P)$ is the height of $P$. Bibl. – 10 titles.