Metadata-Version: 2.4
Name: hittingset
Version: 0.0.1
Summary: Solve the Hitting Set problem in polynomial time via a weighted planar IDS reduction.
Home-page: https://github.com/frankvegadelgado/hittingset
Author: Frank Vega
Author-email: vega.frank@gmail.com
License: MIT License
Project-URL: Source Code, https://github.com/frankvegadelgado/hittingset
Project-URL: Documentation Research, https://github.com/frankvegadelgado/hittingset
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development
Classifier: Development Status :: 5 - Production/Stable
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3.12
Classifier: Environment :: Console
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: Intended Audience :: Information Technology
Classifier: Intended Audience :: Science/Research
Classifier: Natural Language :: English
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx[default]>=3.4.2
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: license
Dynamic: license-file
Dynamic: project-url
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

# Hitting Set Solver

![Hitting Set Solver](docs/hits.jpg)

This work builds upon [Hitting Set Solver](https://github.com/frankvegadelgado/hittingset).

---

## 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

```bash
pip install hittingset
```

Or install from source:

```bash
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:

```bash
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:

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

**Output:**

```
bench09.hit: Hitting Set Size 3
```

---

## Command Options

Display help and options:

```bash
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:

```bash
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:

```bash
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`:

```bash
batch_hits -i ./benchmarks/ -c
```

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

```bash
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`:

```bash
test_hits -m 10 -s 3
```

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

```bash
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
...
```

```bash
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:

```bash
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:

```bash
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.
