Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

Pritish Kamath; Ravi Kumar; Pasin Manurangsi

Source-linked AI summary

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

Pritish Kamath, Ravi Kumar, Pasin Manurangsi

arXiv:2609.12508v1Sep 11, 2026cs.DScs.CR

TL;DR

Differentially private combinatorial optimization faces barriers when solutions must be output explicitly. This paper generalizes implicit representations by allowing FPT-time encoders, obtaining improved approximation guarantees and lower bounds for the framework.

Problem
Explicitly outputting solutions privately can yield trivial utility or invalid solutions, motivating implicit representations for combinatorial optimization.
Source: §1 · pp. 1–2
Method
The paper generalizes the implicit representation framework by allowing FPT-time encoders and arbitrary representations with polynomial-time decoders.
Source: §1.1 · p. 2, §6 · p. 25
Results
The generalized model yields (1 ± ˜O(1/ε))-approximations for Vertex Cover, d-Hitting Set, and maximum induced subgraphs on sparse graphs, alongside representation-independent lower bounds under Gap-ETH with advice.
Source: §6 · p. 25
Takeaways & Limitations
Under Gap-ETH with advice, no ε-DP scheme with a subexponential-time decoder achieves the stated approximation thresholds for Vertex Cover, Maximum Independent Set, or Triangle Packing on bounded-degree graphs when ε is sufficiently small.
Source: §4 · p. 17
The subgraph-packing approximation guarantee is non-trivial only when ε ≥ Ω(log k).
Source: §3.2 · p. 14

Abstract

from arXiv · show

We study combinatorial optimization problems under the constraint of $\epsilon$-differential privacy ($\epsilon$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $\epsilon > 0$, we prove that no $\epsilon$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $\epsilon$.

1 Introduction

Differential privacy makes explicit outputs difficult for combinatorial optimization, especially when noisy candidate solutions can violate hard constraints. The paper generalizes implicit representations with FPT-time encoders, obtaining improved approximations and establishing lower bounds for the framework.

1 Introduction

Sensitive graph data motivates private combinatorial optimization, but directly outputting a solution can yield trivial utility or invalid solutions under hard constraints.The implicit-representation approach instead privately outputs a representation that a decoder combines with the input to construct a valid solution.Source: §1 · pp. 1–2

1.1 Our Contributions

The paper generalizes implicit representations to arbitrary representations and polynomial-time decoders, while allowing the randomized private encoder to run in FPT time.This broadens prior work focused mainly on polynomial-time encoders and specific representations or decoders.Source: §1.1 · p. 2

1.1.1 Implicit Representation Model

An implicit representation scheme uses a randomized ε-DP encoder to produce a representation and a decoder that combines it with the original input to produce a valid solution.The final solution need not itself be DP because the decoder sees the full input; the model assumes a polynomial-time decoder to avoid trivial brute-force decoding.Source: §1.1.1 · pp. 2–3

1.1.2 Upper Bounds

For APX-hard problems, the paper reports (1 ± γ)-approximations in FPT time for any γ > 0 when ε is sufficiently large; for Vertex Cover, it obtains a (1 + ˜O(1/ε))-approximation with an FPT encoder.The Vertex Cover result uses a permutation representation, boosts exponentially rare optimal outcomes through repeated runs, and privately selects among candidate representations; it extends to d-Hitting Set.Source: §1.1.2 · p. 3, Vertex Cover and d-Hitting Set · p. 4

Vertex Cover and d-Hitting Set.

For H-packing, the algorithm samples k^O(k) colorings and uses the exponential mechanism to select one yielding a near-optimal packing.The approach adapts color coding, whose random coloring succeeds with probability k^−O(k).Source: Vertex Cover and d-Hitting Set · p. 4
For maximum induced subgraphs with hereditary properties on sparse graphs, a subset representation yields a (1 − O(1/ε))-approximation.The encoder privately selects a small vertex subset with the exponential mechanism, and the decoder extracts a large induced subgraph; the Independent Set application assumes constant degeneracy.Source: Vertex Cover and d-Hitting Set · p. 4

1.1.3 Lower Bounds

With the representation format and decoder fixed to those of the algorithms, the paper proves privacy-approximation tradeoffs for the studied problems using packing arguments.These representation-dependent bounds apply even for larger ε.Source: Representation-Dependent Lower Bounds · p. 4

Representation-Dependent Lower Bounds.

Under Gap-ETH with advice, the paper rules out near-exact approximations for sufficiently small ε and γ, using privacy to obtain a small covering set of representations that can serve as non-uniform advice.The proof runs only the decoder to approximately solve 3SAT; the covering-based technique is described as novel among computational lower-bound proofs in DP.Source: Representation-Dependent Lower Bounds · p. 5

2 Preliminaries

The preliminaries define the privacy and parameterized-approximation conventions used in the paper, describe its optimization problems, and state the Gap-ETH-with-Advice assumption for lower bounds.

2 Preliminaries

The notation defines induced subgraphs G[S], vertex and edge counts n and m, and degree with respect to an edge set.Source: §2 · p. 5

2.1 Differential Privacy

The paper recalls differential privacy, sensitivity, and the Laplace and exponential mechanisms, including their privacy and utility guarantees.Source: §2.1 · pp. 5–6

2.2 (Parameterized) Approximation Algorithms

Parameterized approximation measures expected solution value against k, an under- or over-estimate of the optimum; an FPT-approximation has an FPT-time encoder and normally a polynomial-time decoder.Source: §2.2 · p. 6
An α-approximation with a subexponential-time decoder yields a one-sided-error ρ-gap algorithm when α>ρ for maximization or α<ρ for minimization.Source: §2.2 · p. 7

2.3 Problem Definitions

The studied tasks include d-Hitting Set, maximum induced hereditary subgraphs, H-Packing, and Triangle-Transversal, with Vertex Cover and Independent Set as special cases.Source: §2.3 · p. 7, Maximum Induced Subgraph (with… · pp. 7–8, Triangle-Transversal · p. 8

Maximum Induced Subgraph (with Hereditary Property):

The Independent Set algorithm requires a constant-degenerate graph, a sparsity restriction motivated by strong FPT-inapproximability in general graphs.Source: Maximum Induced Subgraph (with… · p. 7

Triangle-Transversal:

For Triangle-Transversal, the paper gives representation-dependent lower bounds only; its other studied problems receive both representation-dependent and representation-independent lower bounds.Source: Triangle-Transversal · p. 8

2.4 Gap-ETH with Advice

The lower-bound assumption strengthens standard Gap-ETH: bounded-occurrence Gap-3SAT cannot be solved in the stated exponential time even with non-uniform advice.Source: §2.4 · p. 8

3 Algorithms

The section develops private FPT approximation algorithms using implicit representations for d-Hitting Set, H-Packing, and maximum induced Γ-subgraphs. It uses permutation-based sampling and private selection, color coding, and subset representations under stated assumptions.

3.1 Vertex Cover and d-Hitting Set

The d-Hitting Set decoder uses a permutation and chooses each hyperedge’s earliest vertex; this matches [GLM+10]’s representation, improving its approximation at the cost of FPT rather than polynomial running time.Source: §3.1 · p. 9

3.1.1 A Low Probability Algorithm

The noisy-degree sampler is ε0-DP and outputs a permutation decoding to a fixed optimal size-k hitting set with probability at least (d + 1/ε0)^−O(k).Source: §3.1.1 · p. 9

3.1.2 High Probability via Private Selection

E[|Sπ(E)|] ≤ k + O(k log(d+1/ε)) for d-Hitting Set; the encoder runs in (d + 1/ε)^O(k) · n^O(1) time.The algorithm privately selects among candidate runs, randomly dropping runs rather than directly testing candidate sizes, following [GGK+26].Source: §3.1.2 · pp. 12–14

3.2 Subgraph Packing via Color Coding

For fixed H and ε ≥ 1, color coding gives an H-Packing FPT-approximation implicit representation scheme in kO(k) · nO(1) · ln(1 + ε) time.The encoder applies the exponential mechanism to random colorings, and the decoder selects a monochromatic H-copy for each color; the guarantee is non-trivial only when ε ≥ Ω(log k).Source: §3.2 · pp. 14–15

3.3 Maximum Induced Subgraph with Hereditary Property

For any hereditary property Γ and hereditary graph class satisfying Assumptions 20 and 22, ε ≥ 1 yields an ε-DP (1−O(1/ε))-FPT approximation implicit representation scheme for Maximum Induced Γ-subgraph in 2^O(k)·n^O(1) time.Source: §3.3 · p. 15

3.3.1 Algorithm

The encoder uses the exponential mechanism to select a size-k subset T with score |T|/ρ−distΓ(G[T]), and the decoder returns a baseline solution or removes an approximate deletion set from T.The decoder uses the baseline when |V|≥k·C_G and otherwise returns T\ALGdel(G[T]); the deletion-distance score has sensitivity one.Source: §3.3.1 · p. 16, §3.3 · p. 16
When a Γ-satisfying induced subgraph of size at least k exists, the decoder’s expected output size is at least k(1−O(1/ε)).The hereditary property ensures a size-k subset with score at least k/ρ, and the exponential mechanism yields the utility guarantee.Source: §3.3.1 · p. 16

3.3.2 Applications

On ∆-degenerate graphs, the scheme applies to independent sets, cluster graphs, claw-free graphs, split graphs, cographs, bounded-degree graphs, and forests for constant ∆.For hereditary properties containing all independent sets, the large-baseline assumption holds with C_G=∆+1; the listed properties also satisfy the deletion-approximation assumption.Source: §3.3.2 · p. 17

4 Representation-Independent (Computational) Lower Bounds

The section proves that small-ε privacy and a subexponential-time decoder rule out certain approximations, regardless of encoder running time. It derives this bound by converting privacy into a small advice set and applying Gap-ETH-with-Advice reductions.

4 Representation-Independent (Computational) Lower Bounds

Under Gap-ETH with Advice, no ε-DP scheme with a subexponential-time decoder achieves the stated approximations for Vertex Cover, Maximum Independent Set, or Triangle Packing on bounded-degree graphs.The theorem specifies constants ε > 0 and d, with αVC > 1 and αIS, αTP < 1.Source: §4 · p. 17
The lower bound applies without restricting encoder running time, so executing the encoder cannot itself be the contradiction step.Instead, privacy yields a small advice set that can be used with the decoder.Source: §4 · p. 18, §4.1 · p. 18

4.1 From Privacy to Advice String

A subexponential decoder would imply an O(2^δn)-time deterministic algorithm with O(2^δn) advice for the corresponding gap problem on bounded-degree graphs.The conversion uses an ε-DP implicit representation scheme with one-sided error.Source: §4.1 · p. 18

4.2 Lower Bounds for Gap-3SAT-hard Problems

The reduction extends the lower bound to every Gap-3SAT-hard graph optimization problem, and establishes that Maximum Independent Set, Vertex Cover, and Triangle Packing meet this hardness condition.The reductions preserve the gap and have linear graph size and bounded degree.Source: §4.2 · pp. 19–20

5 Representation-Dependent Lower Bounds

These lower bounds constrain particular implicit representations, with tradeoffs that can persist beyond the small-ε regime of the representation-independent results. The section gives separate bounds for permutation, coloring, subset, and Triangle-Transversal settings.

5 Representation-Dependent Lower Bounds

The section contrasts robust representation-independent bounds, which apply only for small ε, with representation-dependent tradeoffs that also hold for larger ε.The authors characterize the former as applying where their algorithms provide weak or trivial guarantees.Source: §5 · p. 20

5.1 Permutation Representation

For permutation-based d-Hitting Set, every ε-DP scheme has approximation ratio at least 1 + Ω(e^-ε).The bound is stated for d ≥ 2.Source: §5.1 · p. 21

5.2 Coloring Representation

For H-Packing with a fixed connected graph H of at least two vertices, ε ≤ c log k forces approximation ratio at most 2/3 under the coloring representation.The constant c depends on H; the bound applies for sufficiently large k.Source: §5.2 · pp. 22–23

5.3 Subset Representation

For Independent Set on one-bounded-degree graphs, the subset representation has approximation ratio at most 1 − Ω(e^-ε).The graph class consists of disjoint edges and isolated vertices.Source: §5.3 · p. 23

5.4 Triangle-Transversal

For Triangle-Transversal under the permutation representation, every ε-DP scheme has approximation ratio at least Ω(n · e^-ε).Thus, constant approximation requires ε = Ω(ln n).Source: §5.4 · p. 24

6 Conclusion and Open Questions

The paper generalizes the implicit representation framework with FPT-time encoders, obtaining improved approximation guarantees and representation-independent lower bounds under Gap-ETH with advice. It leaves open improvements to the tradeoffs, extensions to other computational settings, and how the bounds change under approximate-DP.

6 Conclusion and Open Questions

The paper uses FPT-time encoders to bypass polynomial-time inapproximability barriers and obtains (1 ± ˜O(1/ε))-approximations for several fundamental graph problems.The stated examples include Vertex Cover, d-Hitting Set, and maximum induced subgraphs on sparse graphs.Source: §6 · p. 25
For current representations, closing the gap between the algorithms' ˜O(1/ε) dependence and the lower bounds' Ω(e^-ε) dependence remains open.With new representations, the representation-independent bounds do not rule out exact algorithms when ε is a large constant.Source: §6 · p. 26
The framework could be extended to other FPT techniques, decoders simpler than encoders, or approximate-DP; some lower bounds do not transfer directly to approximate-DP.The authors note that a strong separation between pure-DP and approximate-DP remains possible.Source: §6 · p. 26