Combinatorial Derandomization for Parameterized Algorithms

This direction is split into other directions: deterministic derandomization. Its last version stays readable and citable here.

Version 1 of 128 papers30 conceptsfrozen 2026-10-04

In theoretical computer science, randomness is often a "cheat code" that makes hard problems easy. If you need to find a needle in a haystack, picking random handfuls of hay is often faster than a systematic search. However, in many applications—from safety-critical systems to formal verification—we require the absolute certainty of a deterministic algorithm.

The research direction explored here focuses on derandomization: the process of replacing "random luck" with structured combinatorial guarantees. By using mathematical objects like perfect hash functions, universal sets, and splitters, researchers transform probabilistic existence proofs into efficient, deterministic search procedures.

The Intuition: From Luck to Coverage

To understand derandomization, consider the technique of color-coding. Suppose you want to find a path of length $k$ in a large graph. A randomized approach might assign one of $k$ colors to every vertex at random. If you are lucky, the path you are looking for will be "colorful"—meaning every vertex on the path has a different color. Once a path is colorful, it is much easier to find using dynamic programming.

The "luck" required here is probabilistic. But as Shai Gutner demonstrates in Balanced Families of Perfect Hash Functions and Their Applications, we can replace this luck with a perfect hash family. Instead of one random coloring, we use a predefined set of colorings. The mathematical guarantee is that for any set of $k$ vertices, at least one coloring in our family will map them to distinct colors.

By iterating through this family, we move from "we might find the path" to "we are guaranteed to find the path."

Universal Sets and State Coverage

When searching for local improvements or specific subgraphs, algorithms often need to "hit" a specific configuration of vertices. In randomized algorithms, we might select vertices with some probability. To derandomize this, researchers use universal sets.

A universal set is a collection of bitstrings such that for any subset of indices of a certain size, all possible patterns of 0s and 1s appear at least once. Serge Gaspers and Stefan Szeider apply this in Don't Be Strict in Local Search! to ensure that a local search algorithm explores enough of a neighborhood to find an improvement, transforming a W[1]-hard problem into a fixed-parameter tractable (FPT) one.

Similarly, R. Krithika and Pranabendu Misra use universal sets in A Single Exponential-Time FPT Algorithm for Cactus Contraction to bound the search space for edge contractions. The universal set acts as a deterministic "net" that is guaranteed to catch the correct set of edges to contract, regardless of where they are hidden in the graph.

Splitters and Separators

For problems involving graph cuts or reconstruction, the challenge is ensuring that we've sampled enough vertices to "split" the graph correctly. Debmalya Panigrahi and Jason Li utilize splitters—combinatorial structures that guarantee the selection of necessary vertex subsets—to create a Deterministic Min-cut in Poly-logarithmic Max-flows.

This same logic applies to graph reconstruction. Juha Harviainen and Pekka Parviainen show in Graph Reconstruction with a Connected Components Oracle that by using splitters or p-query-schemes, one can reconstruct hidden graphs with a logarithmic number of queries. The splitter ensures that every potential "witness" (a set of vertices proving an edge exists or doesn't) is eventually queried.

Constructive Lovász Local Lemma

Perhaps the most famous non-constructive tool in combinatorics is the Lovász Local Lemma (LLL), which proves that if a set of "bad events" are mostly independent and have low probability, there is a non-zero chance that none of them happen. For decades, this only proved a solution existed without telling us how to find it.

Bernhard Haeupler and Karthekeyan Chandrasekaran bridged this gap in Deterministic Algorithms for the Lovasz Local Lemma. By introducing "partial witness trees," they turned the LLL into a deterministic search algorithm. This allows researchers to solve complex constraints, like those in $k$-CNF satisfiability, with absolute certainty in polynomial time.

Why It Works: The Efficiency Trade-off

The core insight across these papers is that we don't need true randomness; we only need the properties that randomness usually provides (like diversity and coverage).

  1. Identify the property: What does the random step achieve? (e.g., "It makes the path colorful with probability $p$.")
  2. Construct a surrogate: Build a deterministic set of objects that satisfies that property. (e.g., "A family of hash functions where every path is colorful in at least one.")
  3. Iterate: Run the algorithm for each object in the surrogate set.

While this often increases the running time compared to a single randomized trial, researchers like Hadas Shachnai have developed tradeoff-based approaches to keep these deterministic versions efficient. As seen in the work on Kidney Exchange by Aritra Banik and colleagues, these deterministic tools are now reaching speeds ($O^*(10.88^t)$) that rival or exceed previous randomized benchmarks.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_derandomization_for_parame_06dc1e44,
  title = {Combinatorial Derandomization for Parameterized Algorithms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-derandomization-for-parameterized-algorithms/rdr_06dc1e447ff344cea6ab399bdd7a2372},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_combinatorial_derandomization_for_parame_06dc1e44_v1,
  title = {Combinatorial Derandomization for Parameterized Algorithms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-derandomization-for-parameterized-algorithms/rdr_06dc1e447ff344cea6ab399bdd7a2372/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}