#CPM2026 hashtag - Bluesky

@jnalanko.bsky.social

5 days ago

Computing k-mers in Graphs We initiate the study of computational problems on $k$-mers (strings of length $k$) in labeled graphs. As a starting point, we consider the problem of counting the number of distinct $k$-mers found on...

Accepted to CPM 2026! In this paper, we consider the problem of k-mer counting in *graphs*. We show that it's #P-hard even in deterministic DAGs. But on Wheeler graphs, it's tractable -- easy in O(nk) time. We can also do O(poly(n) log k) but it gets complicated. #CPM2026
arxiv.org/abs/2509.22885