hittingset 0.0.1

Solve the Hitting Set problem in polynomial time via a weighted planar IDS reduction.

Hitting Set Solver

This work builds upon Hitting Set Solver.

---

The Hitting Set Problem

Problem: Given a universe $U$ and a collection of subsets $\mathcal{S} = \{S_1, S_2, \ldots, S_M\}$ with each $S_i \subseteq U$, find a set $H \subseteq U$ such that $H \cap S_i \neq \emptyset$ for every $i$.

Background:

The Hitting Set problem is equivalent (by duality) to Set Cover and is NP-hard in general. Minimising $|H|$ is NP-hard to approximate within $(1 - \varepsilon)\ln N$ for any $\varepsilon > 0$ unless P = NP. This solver uses a polynomial-time reduction to a Minimum Weighted Independent Dominating Set (MIDS) on a planar graph, then applies Baker's $(1+\varepsilon)$-PTAS.

Concepts:

• Universe $U$: a finite set of elements $\{1, 2, \ldots, n\}$.
• Subset collection $\mathcal{S}$: a family of non-empty subsets of $U$.
• Hitting set $H$: a set $H \subseteq U$ that intersects every subset in $\mathcal{S}$.
• Minimum hitting set: a hitting set of smallest possible cardinality.

Example:

Universe $U = \{1, 2, 3, 4, 5\}$, subsets $\{\{1,2,3\},\{2,4\},\{3,5\}\}$. A hitting set is $H = \{2, 3\}$: element $2$ hits $S_1$ and $S_2$, element $3$ hits $S_1$ and $S_3$.

---

Input Format (.hit files)

Instance files use the .hit extension:

c  comment lines (ignored)
p hit <num_elements> <num_subsets>
<elem1> <elem2> ... 0
<elem1> <elem2> ... 0

• The p hit header declares $|U|$ (elements are the integers $1 \ldots n$) and the number of subsets.
• Each subsequent line is one subset: space-separated element indices terminated by 0.
• Lines starting with c are comments.

Example .hit file:

c Hitting Set example
c Universe: {1, 2, 3, 4, 5}, Subsets: 3
p hit 5 3
1 2 3 0
2 4 0
3 5 0

Compressed variants .xz, .lzma, .bz2, and .bzip2 are also accepted.

---

Algorithm

The solver runs a portfolio of three strategies, repairs and prunes every candidate to an inclusion-wise minimal hitting set, and returns the smallest:

1. Planar IDS reduction + Baker's PTAS — reduce to Minimum Weighted Independent Dominating Set (MIDS) on a planar gadget graph and apply Baker's $(1+\varepsilon)$-PTAS with $\varepsilon = 0.5$.
2. Bipartite Max-Cut — exact maximum cut with a minimized, subset-forbidden side on the incidence graph, in $O(n + m)$.
3. Bucket-queue greedy — the classic frequency-greedy ($O(\log M)$-approximation) implemented with a bucket queue in $O\left(\sum_i |S_i|\right)$, i.e. linear in the input size.
4. Seeded greedy restarts — every hitting set must contain an element of a smallest subset $S^*$, so greedy is restarted once per element of $S^*$ ($\le \min_i |S_i|$ restarts, each linear).

Every candidate then passes through two linear-time post-processing steps:

• Repair — any unhit subset gets its maximum-frequency element added (validity guarantee), in $O\left(\sum_i |S_i|\right)$.
• Prune — redundant elements are removed (an element is redundant iff every subset containing it is hit by another chosen element), processed in ascending frequency via counting sort, in $O\left(|H| + M + \sum_i |S_i|\right)$. The result is an inclusion-wise minimal hitting set.

Graph Construction

For a universe $U$ and subsets $S_1, \ldots, S_M$, construct a weighted graph $G$ as follows:

Node	Represents	Weight
$(x, 0)$	element $x \in U$	$1$
$(x, i)$	copy of $x$ for subset $S_i$	$0$
$(\mathtt{u}, x, i)$	matching partner of $(x, i)$	$0$
$(\mathtt{D}, i)$	domination sentinel for $S_i$	$10 \cdot N$

Edges (for every $x \in S_i$, $1 \le i \le M$):

(x, 0)  --  (x, i)  --  ('u', x, i)  --  ('D', i)

Semantics: The sentinels $(\mathtt{D}, i)$ carry weight $10N$ (where $N = |U|$). Since the most expensive valid hitting set costs at most $N$ (the full universe), a single sentinel always outweighs any hitting set, so the minimum-weight IDS avoids selecting them. To dominate $(\mathtt{D}, i)$ cheaply the IDS must include some $(\mathtt{u}, x, i)$, which forces $(x, 0)$ into the IDS (cost $1$). The extracted hitting set is therefore:

$$H = \{ x \in U : (x, 0) \in \mathrm{IDS} \}$$

If the gadget graph is not planar, a maximal planar subgraph is extracted before running the PTAS.

Baker's PTAS

Baker's $(1+\varepsilon)$-PTAS for Minimum Weighted IDS on planar graphs is applied with $\varepsilon = 0.5$ (approximation ratio $1.5$ on the planar gadget). The algorithm:

1. Computes BFS layers of the planar gadget graph.
2. For each offset $i \in \{0, \ldots, k-1\}$ (where $k = \lceil 1/\varepsilon \rceil = 2$), removes layer-$i$ vertices and solves IDS on each remaining connected component via tree-decomposition DP.
3. Returns the best solution found across all offsets.

The extracted hitting set is repaired (any subset the IDS failed to encode gets its maximum-frequency element) before entering the portfolio comparison.

---

Compile and Environment

Prerequisites

• Python ≥ 3.12

Installation

pip install hittingset

Or install from source:

git clone https://github.com/frankvegadelgado/hittingset.git
cd hittingset
pip install -e .

---

Execution

Run the solver on a single .hit file using the hits command:

hits -i ./benchmarks/bench09.hit

Example Output:

bench09.hit: Hitting Set Found 3, 5, 7

This indicates elements 3, 5, 7 form a Hitting Set.

---

Hitting Set Size

Use the -c flag to count the elements in the Hitting Set instead of listing them:

hits -i ./benchmarks/bench09.hit -c

Output:

bench09.hit: Hitting Set Size 3

---

Command Options

Display help and options:

hits -h

Output:

usage: hits [-h] -i INPUTFILE [-a] [-b] [-c] [-v] [-l] [--version]

Solve the Hitting Set problem using a .hit file as input.

options:
  -h, --help            show this help message and exit
  -i INPUTFILE, --inputFile INPUTFILE
                        input file path
  -a, --approximation   enable comparison with a polynomial-time approximation
                        approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-
                        force approach
  -c, --count           calculate the size of the Hitting Set
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --version             show program's version number and exit

---

Brute Force Comparison

Use -b to run the exponential-time exact solver alongside the PTAS and report the exact approximation ratio:

hits -i ./benchmarks/bench09.hit -b -c

Output:

bench09.hit: (Brute Force) Hitting Set Size 3
bench09.hit: Hitting Set Size 3
Exact Ratio (PTAS/Optimal): 1.0

---

Approximation Comparison

Use -a to run the greedy logarithmic-approximation solver and report an upper bound on the approximation ratio:

hits -i ./benchmarks/bench09.hit -a -c

Output:

bench09.hit: (Approximation) Hitting Set Size 3
bench09.hit: Hitting Set Size 3
Upper Bound for Ratio (PTAS/Optimal): 1.9459101490553132

When -b and -a are both supplied, the exact ratio (from brute force) is reported.

---

Batch Execution

Solve every .hit file in a directory with batch_hits:

batch_hits -i ./benchmarks/ -c

All flags (-a, -b, -c, -v, -l) apply to every file.

batch_hits -h

Output:

usage: batch_hits [-h] -i INPUTDIRECTORY [-a] [-b] [-c] [-v] [-l] [--version]

Solve the Hitting Set problem on all .hit files in a directory.

options:
  -h, --help            show this help message and exit
  -i INPUTDIRECTORY, --inputDirectory INPUTDIRECTORY
                        input directory path containing .hit files
  -a, --approximation   enable comparison with a polynomial-time approximation
                        approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-
                        force approach
  -c, --count           calculate the size of the Hitting Set
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --version             show program's version number and exit

---

Random Testing

Generate and solve a random instance with test_hits:

test_hits -m 10 -s 3

With all solvers, 4 tests, and a fixed seed:

test_hits -m 6 -s 3 -n 4 -u 8 --seed 42 -b -a -c

Output:

1-Approximation Test: Hitting Set Size 2
1-Brute Force Test: Hitting Set Size 2
1-PTAS Test: Hitting Set Size 2
Exact Ratio (PTAS/Optimal): 1.0
2-Approximation Test: Hitting Set Size 2
2-Brute Force Test: Hitting Set Size 2
2-PTAS Test: Hitting Set Size 2
Exact Ratio (PTAS/Optimal): 1.0
...

test_hits -h

Output:

usage: test_hits [-h] -m NUMSUBSETS -s SUBSETSIZE [-n NUM_TESTS]
                 [-u UNIVERSESIZE] [--seed SEED] [-a] [-b] [-c] [-v] [-l]
                 [--version]

Test Hitting Set solvers on a random instance.

options:
  -h, --help            show this help message and exit
  -m NUMSUBSETS, --numSubsets NUMSUBSETS
                        number of subsets M
  -s SUBSETSIZE, --subsetSize SUBSETSIZE
                        number of elements per subset
  -n NUM_TESTS, --num_tests NUM_TESTS
                        number of random tests to run (default: 5)
  -u UNIVERSESIZE, --universeSize UNIVERSESIZE
                        universe size |U| (default: max(M, 2*subsetSize))
  --seed SEED           random seed for reproducibility
  -a, --approximation   enable comparison with a polynomial-time approximation
                        approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-
                        force approach
  -c, --count           calculate the size of the Hitting Set
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --version             show program's version number and exit

---

Benchmarks

The benchmarks/ directory contains 30 hand-crafted .hit instances designed to stress-test all three solvers. Instance families include:

• Exact-cover and sunflower structures
• Grid and bipartite / Latin-square structures
• Fano-plane and Steiner-triple-system instances
• Adversarial greedy instances
• All-pairs / all-triples instances over small universes
• Dense small-universe mixed-size instances

Run the full benchmark suite with all solvers:

batch_hits -i ./benchmarks/ -b -a -c

---

CAR Experiment (Correctness & Approximation Ratio)

The car/ directory contains a large-scale stress experiment: 100,000 adversarial instances, kept small enough ($|U| \le 14$) that the exact optimum is computed by brute force on every instance, so the reported ratios are exact — not upper bounds. All instances are feasible by construction.

Eight adversarial families are generated (12,500 instances each): random vertex-cover graphs, 3-uniform hypergraph covers, transposed textbook greedy-killer set systems (OPT = 2, frequency-greedy lured into $\Theta(\log n)$ picks), sunflowers with high-frequency decoy cores, chains and cycles, Fano-plane designs, hidden exact covers buried under decoy supersets, and dense mixed families.

Results (seed 2026, full table in car/RESULTS.md / car/results.csv):

Metric	Value
Instances solved	100,000 / 100,000 valid (0 failures)
Optimum matched	99,407 (99.41%)
Mean ratio $|H|/\mathrm{OPT}$	1.00149
Max ratio observed	1.3333

Family	Optimal	Mean ratio	Max ratio	Greedy mean	Greedy max
chain_cycle	100.00%	1.00000	1.0000	1.00000	1.0000
dense_mixed	99.48%	1.00137	1.3333	1.03415	1.6667
design	100.00%	1.00000	1.0000	1.00000	1.0000
exact_cover	99.73%	1.00075	1.3333	1.02290	1.6667
greedy_killer	100.00%	1.00000	1.0000	1.49832	2.0000
sunflower	98.04%	1.00539	1.3333	1.13985	1.5000
triple_cover	98.73%	1.00317	1.3333	1.03428	2.0000
vertex_cover	99.28%	1.00120	1.2500	1.02071	1.5000

Notably, on the greedy_killer family the standalone greedy solver averages ratio 1.498 (max 2.0) while the portfolio stays at 1.0 — the Max-Cut, PTAS, and seeded-restart strategies plus the linear-time prune neutralize the trap. The worst observed portfolio ratio over all 100,000 adversarial instances is $1.3333 \le 2$, consistent with the candidate ratio $r = 2$; the worst instance of each family is saved in car/worst/*.hit for reproduction.

Reproduce with:

python3 car/experiment.py -n 100000 --seed 2026

Sharded execution and merging are supported for constrained environments (--start, --partial, --aggregate).

---

Solvers at a Glance

Solver	Flag	Time complexity	Solution quality
Portfolio (Baker PTAS + Max-Cut + greedy + seeded restarts, repair + prune)	(default)	polynomial	$= 1.0$ on all 30 benchmarks; $99.41%$ optimal on 100,000 adversarial CAR instances
Greedy (bucket queue)	-a	$O\left(\sum_i |S_i|\right)$ — linear	$O(\log N)$-approximation
Brute Force	-b	$O(2^{|U|} \cdot M)$ worst case; enumerates by increasing cardinality with early exit	exact minimum

The brute-force solver is exact but exponential in $|U|$; use it only for small instances ($|U| \le 20$).

---

Approximation Barriers and Theoretical Significance

Hardness threshold under P ≠ NP

The Hitting Set problem is equivalent to Set Cover via LP duality. Feige (1998) proved, and Dinur–Steurer (2014) sharpened to a clean NP-hardness statement, that no polynomial-time algorithm can approximate the minimum Hitting Set within a multiplicative factor strictly better than

$$\rho = (1 - \delta)\ln N, \quad N = |U|,$$

for any fixed $\delta > 0$, unless P = NP. The classical greedy algorithm matches this threshold with ratio $H_N \approx \ln N$. Any polynomial-time algorithm whose ratio $r$ satisfies $r < (1-\delta)\ln N$ for all instances with $N$ elements would therefore prove P = NP.

Hardness threshold under the Unique Games Conjecture (UGC)

Khot's Unique Games Conjecture (2002) implies strong inapproximability for a wide range of combinatorial optimisation problems. For Set Cover / Hitting Set, the most directly relevant strengthening is the Projection Games Conjecture (Moshkovitz–Raz, 2010), which is closely related to UGC and implies that Hitting Set is NP-hard to approximate within any constant factor smaller than $\Omega(\ln N)$ — ruling out constant-ratio polynomial-time algorithms. A constructive constant-approximation would therefore provide strong evidence against the Projection Games Conjecture, and by extension against those variants of UGC that entail it.

Why a 2-approximation lies inside the forbidden zone

Baker's $(1+\varepsilon)$-PTAS on the weighted planar gadget graph yields an IDS solution of cost at most $(1+\varepsilon)\cdot\mathrm{OPT}_{\text{IDS}}$. Under the hypothesis that the reduction is exact — i.e., that $\mathrm{OPT}_{\text{IDS}}$ equals the optimal hitting-set cost counted through the weight-1 universe nodes — the extracted set $H$ satisfies

$$|H| \leq (1 + \varepsilon)\cdot\mathrm{OPT}_{\text{HS}}.$$

With $\varepsilon = 0.5$ the gadget-level ratio is $1.5$. Across all 30 hand-crafted benchmarks the observed ratio $|H|/\mathrm{OPT}$ is exactly $1.0$ — the solver matches the brute-force optimum on every instance. We adopt $r = 2$ as a conservative candidate approximation ratio:

• The gadget-level guarantee with $\varepsilon = 0.5$ is $1.5 \leq 2$; the portfolio only improves on the gadget candidate.
• All 30 benchmark instances achieve ratio $1.0 \leq 2$, well within the guarantee, and the CAR experiment (below) measures the empirical ratio over 100,000 adversarial instances.
• The Feige threshold is $\rho = (1-\delta)\ln N$. Because $\ln N > 2$ for every $N \geq 8$ (since $\ln 8 \approx 2.08$), the ratio $r = 2$ lies strictly below $\rho$ on every instance with $N \geq 8$. Framed additively:

$$r = 2 = \rho - \Delta, \quad \Delta = \rho - 2 > 0 \text{ for } N \geq 8,$$

and $\Delta$ grows without bound as $N \to \infty$, so a 2-approximation is asymptotically deep inside the zone that is forbidden under P $\neq$ NP.

Status: possible candidate

The theoretical significance of this solver hinges on whether the Hitting-Set-to-IDS reduction is exact: specifically, whether the minimum-weight IDS of the planar gadget graph always encodes precisely a minimum hitting set, with no distortion introduced by the planarity-enforcement step (maximal planar subgraph extraction). If that correspondence holds, then the observed $\leq 2$-approximation (gadget guarantee $1.5$ with $\varepsilon = 0.5$, ratio $1.0$ on all 30 benchmarks, and max ratio $1.3333$ over the 100,000 adversarial CAR instances) constitutes a possible candidate for:

1. Proving P = NP — by providing a polynomial-time algorithm whose approximation ratio beats the Feige/Dinur–Steurer lower bound on every instance with $N \geq 8$.
2. Disproving the Projection Games Conjecture (and UGC-derived hardness for Set Cover) — by achieving a constant approximation ratio that those conjectures rule out.

A formal proof that the reduction is lossless — and in particular that planarity enforcement does not silently drop constraints — remains the open theoretical step. Until that is settled the algorithm should be treated as a possible candidate rather than a confirmed breakthrough.

---

Runtime Analysis

The following table summarises the time complexity of each phase in terms of $N = |U|$ (universe size) and $M$ (number of subsets). Let $K = \sum_{i=1}^{M} |S_i|$ denote the total input size; in the worst case $K = N \cdot M$.

Phase	Cost
Incidence structures (occ, freq), built once	$O(K)$ — linear
Gadget construction + planarity enforcement	polynomial in $K$
Baker PTAS (tree-decomposition DP, $\varepsilon = 0.5$)	polynomial for fixed $\varepsilon$; dominant phase
Bipartite Max-Cut strategy	$O(N + M + K)$ — linear
Bucket-queue greedy strategy	$O(K)$ — linear
Seeded greedy restarts	$O\left(\min_i |S_i| \cdot K\right)$
Repair pass (per candidate)	$O(K)$ — linear
Prune pass (per candidate)	$O(|H| + M + K)$ — linear

The Max-Cut and greedy strategies, together with the repair and prune post-processing of all candidate solutions, run in time linear in the input size $K$. Total runtime is polynomial and dominated by the Baker PTAS phase; disable that strategy for a fully linear pipeline.