CS Paper Radar

Source Assignment: Hardness, Approximation, and Parameterized Algorithms

Ruxandra Marinescu-Ghemeci, Adrian Miclăuş, Alexandru Popa

cs.DS ·submitted 2026-11-10 22:17 UTC · v1
hot direction

Abstract

In Source Assignment, each pointer represents a substring of a common reference string and may have several possible source occurrences. The goal is to choose one source for each pointer while minimizing the number of distinct reference boundaries used by the selected sources. The problem was introduced by Qiu and Kingsford (Bioinformatics 2021) in the context of compact genome-graph construction. We distinguish \emph{Explicit Source Assignment}, where admissible source sets are given explicitly, from \emph{Complete Source Assignment}, where all occurrences of each pointer string are available. We show that Explicit Source Assignment has an exact value-preserving formulation as cardinality Set Cover with Pairs. For every fixed $\varepsilon>0$, it cannot be approximated within $(1-\varepsilon)\ln p$ unless $\mathrm{P}=\mathrm{NP}$, even over a binary alphabet when all pointers have length one, while known algorithms for Minimum-Weight Multicolored Subgraph give an $O(\sqrt{q\log p})$-approximation for arbitrary pointer lengths. Our main hardness result proves that Complete Source Assignment is APX-hard even over a binary alphabet, with equal pointer lengths and at most two sources per pointer. For edge-disjoint equal-length instances, we give a $3/2$-approximation and a $1.12585$-approximation when each pointer has at most two sources. We also introduce the rainbow-path length $λ$: the problem is polynomial-time solvable for $λ\le2$, and for $λ\le3$ we obtain a $(9/8+\varepsilon)$-approximation. We further give a polynomial-time test for deciding whether abstract source sets can be realized exactly as complete occurrence sets over an unrestricted alphabet. Finally, we give exact fixed-parameter algorithms for several structural parameters, and show that Complete Source Assignment is fixed-parameter tractable in the alphabet size and maximum pointer length.

Closest papers

Nearest neighbours by meaning across the whole index.

Hardness, Approximation, and Parameterized Algorithms for Asynchronous Border Minimization

cs.DS ·2026-11-12 ·Giulian Buzatu, Adrian Miclăuş, Alexandru Popa
theory similarity 0.66
Abstract

In the Asynchronous Border Minimization Problem (BMP), a set of DNA probe strings is placed on a grid and synthesized using a common sequence of nucleotide-deposition steps. At each step, every cell may accept or skip the offered nucleotide. The cost is the total number of disagreements between neighboring cells over all steps. We study both free placement, where the probes may be rearranged, and fixed placement, where their positions are given. We show that free-placement BMP on a square grid is NP-complete over three symbols. For one-dimensional BMP, we prove APX-hardness over a binary alphabet, and NP-completeness even when every probe has length two. We also obtain an $8/7$-approximation for the latter restriction. For square grids, we give a randomized $O(n^{1/4}\log n)$-approximation, improving the earlier $O(n^{1/4}\log^2 n)$ guarantee. Both free- and fixed-placement BMP on rectangular grids are fixed-parameter tractable when parameterized only by the allowed border cost.

0.25

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

cs.DS ·2026-09-21 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
similarity 0.64
Abstract

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

0.08

Tokenization: Hardness and Bicriteria Approximation Algorithms

cs.DS cs.AIcs.CC ·2026-11-11 ·Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
theory similarity 0.63
Abstract

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

0.18

Towards Optimal Prefix-Free Graph Construction: NP-Hardness and Structural Insights

cs.CC ·2026-09-15 ·Andrej Baláž, Alexandru Popa
similarity 0.63
Abstract · 11 pages, 0 figures

Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

0.31

Mining Correlated Motifs with Wildcards in PPI Networks: Exact and Optimal

cs.DS ·2026-10-13 ·Lucas P. Oliveira, Ben Bals, Aalt D. J. van Dijk, Solon P. Pissis
similarity 0.61
Abstract · ALENEX 2027

A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (CMM) seeks pairs of sequence motifs whose co-occurrence in interacting proteins reveals binding sites and interaction mechanisms. Formally, in the $(\ell,d)$-CMM problem, we are given a graph $G=(V,E)$, with $V\subseteqΣ^*$ for an alphabet $Σ$, and integers $0\leq d<\ell$, and we seek a pair $\{X,Y\}$ of motifs, each of length $\ell$ and containing $d$ wildcards, that maximizes a support measure $f(G,\{X,Y\})$; e.g., the count $f_E$ of edges $\{u,v\}\in E$ such that $X$ matches a substring of $u$ and $Y$ matches a substring of $v$, or vice versa. Although existing approaches have produced biologically meaningful results, they are either inefficient or heuristic-based, as the underlying optimization problem is NP-hard. Here, we revisit $(\ell,d)$-CMM. For $d=0$, we give an exact $\mathcal{O}(N^2)$-time and $\mathcal{O}(N)$-space algorithm, where $N$ is the total length of the node strings, and prove that this time is conditionally optimal under the Strong Exponential-Time Hypothesis. For any $d>0$, we give an exact $\mathcal{O}\!\left(\binom{\ell}{d}^2N^2\right)$-time and $\mathcal{O}(N)$-space algorithm, and observe that the problem is W[1]-hard parameterized by $d$. The latter algorithm improves the state of the art by exponentially large factors in both time and space. We further demonstrate experimentally that our algorithms are practical on real-world PPI networks and find significantly higher-scoring motif pairs than the state of the art. Moreover, we show that our algorithms find many top-scoring motif pairs that the state of the art misses entirely. Taken together, our results suggest that exact CMM with wildcards is more tractable in practice than previously assumed.

0.23

Hardness Results for Approximate Distance Labeling in Sparse Graphs

cs.DS ·2026-11-02 ·Tsvi Kopelowitz, Ariel Korin, Liam Roditty
top venuetheory similarity 0.61
Abstract · To appear in SODA 2027

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

0.38

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

cs.IT ·2026-09-30 ·Fengqi Hou
similarity 0.60
Abstract · 15 pages. Lean formalization included as ancillary files

We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

0.12

Counting approximate breakpoint medians of random genomes

cs.CE cs.DSq-bio.PE ·2026-10-29 ·Poly H. da Silva, Arash Jamshidpey, David Sankoff
theory similarity 0.59
Abstract · 32 pages, 1 figure

Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively. The breakpoint distance counts the adjacencies of one genome that are absent from the other, and a breakpoint median minimizes the total breakpoint distance to a given set of genomes. Deciding whether a permutation is a median often requires a minimization over the whole symmetric group, which makes the median set resistant to exact counting. We replace this global condition by a local one: a c-approximate median is a genome having at most c adjacencies absent from all the input genomes. For a fixed genome we introduce its approximate median inverse, the set of ordered k-tuples of genomes ad- mitting it as a c-approximate median, and we construct and count this set explicitly. For k genomes chosen uniformly and independently at random, this gives the probability that a given genome is a c-approximate median and the expected number of such approximate medians. The relaxation is not only technical: approximate medians and near-optimal genomes co- incide up to a shift of the tolerance that remains bounded in probability as the number of genes grows. Finally, we derive an explicit upper bound on the probability that a given genome is an exact median, and on the expected number of exact breakpoint medians.

0.13