# Binary Jumbled Pattern Matching on Trees and Tree-Like Structures

arXiv: https://arxiv.org/abs/1301.6127 · HTML: https://mlsanity.com/paper/1301.6127/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2013.

## Built on by (most cited first, 1 of 1)

- [Word Chain Generators for Prefix Normal Words](https://mlsanity.com/paper/2508.19619/) (2025)

## Abstract (arXiv)

Binary jumbled pattern matching asks to preprocess a binary string S in order to answer queries (i,j) which ask for a substring of S that is of length i and has exactly j 1-bits. This problem naturally generalizes to vertex-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an O(n2 / log2 n)-time solution for trees, matching the currently best bound for (the simpler problem of) strings. We also give an Ohg2 / 3 n4 / 3/(log n)4/3-time solution for strings that are compressed by a grammar of size g. This solution improves the known bounds when the string is compressible under many popular compression schemes. Finally, we prove that the problem is fixed-parameter tractable with respect to the treewidth w of the graph, thus improving the previous best nO(w) algorithm [ICALP'07].