Metraipolis › archive › dc_cd6a34da590f
From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures — arXiv:2608.13033
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.13033
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T04:56:58.386Z
- SHA-256 of the archived text
12c9beb1125f5e0e93bb1caf404c4f4947f4e8f101c9ef455cac73304634680f- Stable URL of this page
https://metraipolis.com/documento/dc_cd6a34da590f
How to cite
From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures — arXiv:2608.13033 — arXiv (en), https://arxiv.org/abs/2608.13033 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd6a34da590f (Metraipolis archive dc_cd6a34da590f, sha256 12c9beb1125f5e0e93bb1caf404c4f4947f4e8f101c9ef455cac73304634680f)
BibTeX
@misc{dccd6a34da590f,
title = {From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures — arXiv:2608.13033},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.13033},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd6a34da590f; sha256 12c9beb1125f5e0e93bb1caf404c4f4947f4e8f101c9ef455cac73304634680f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.13033. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of returning a single feasible or optimal solution, the goal is to output a \emph{collection} of meaningfully different solutions, often measured by symmetric differences. Diverse variants have been studied using sparsification, network-flow reductions, and algebraic techniques. We investigate the fixed-parameter tractability of diverse variants of an implicit set-system problem. Given parameters $k$ and $r$ and a threshold $b$, the task is to compute $r$ feasible solutions, each of size at most $k$, whose diversity under a specified objective is at least $b$. Our main contribution is an oracle-based meta-theorem. We identify a broad class of objectives, called \emph{consistently diverse}, that includes several standard measures. Assuming an \emph{exact empty-extension oracle} given a forbidden set ${\sf Forb}$, which returns a feasible solution of a prescribed size avoiding ${\sf Forb}$ or reports that none exists, we obtain a fixed-parameter tractable algorithm parameterized by $k+r$. The algorithm makes at most $(2kr)^{kr} \cdot r$ oracle calls, and in each call the oracle parameter satisfies $s+|{\sf Forb}| \leq k+2kr$. Our framework unifies and strengthens previous oracle-based approaches. Compared with Kumabe's framework (ESA 2025), which gives a doubly exponential bound on the number of oracle calls, our approach achieves the single exponential bound $2^{O(kr\log(kr))}$ and directly constructs the desired tuple of solutions. We recover fixed-parameter tractable algorithms for all problems covered by that framework, with improved oracle complexity, and obtain strong bounds for diverse variants of classical graph and matroid problems.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-14 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.13033 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:52:49.851Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).