# Set Cover, minimum RAFs, and the cost of irreducibility

This executable example builds the literal Set Cover reduction in *Min-RAF
inapproximability*. It explains the construction through food closure, checks
its exact correspondence on small instances, and exposes the distinction between
an inclusion-minimal RAF and a smallest RAF. The source records the manuscript
SHA-256. The implementation is original Python from the manuscript definitions;
it is not extracted from Lean.

## Inputs and model

Edit USER INPUTS at the top of `example.py`. `UNIVERSE_SIZE` is the number m of
elements, numbered from zero. `SETS` is an indexed family of subsets whose union
must cover the universe. Repeated and empty sets are permitted. `BLOCK_LENGTH`
is the positive integer M. These are combinatorial inputs with no physical units.
The default is the paper's three-element, three-set worked instance with M=2.

`SetCover` owns incidence and cover queries. `Network` owns literal reactions,
synchronous food closure, the RAF predicate, maximal-RAF pruning, and deletion
search. `CoverReduction` builds and decodes the construction and audits the
correspondence. These components can be imported without plotting or execution.

Every network has one food species f, m gate reactions forming a chain, and M
reactions per indexed set. Each block requires the final gate product; its final
product catalyses the whole block and precisely the gates for elements in that
set. A nonempty RAF must therefore contain the entire gate scaffold and complete
blocks for a cover D. Its size is exactly m + M|D|. Catalysis is tested after food
closure; it does not gate the closure iterations. This is a structural RAF model,
not a kinetic simulation or a startup mechanism.

## Run

Python 3.11 or newer; Matplotlib is needed only to generate figures. The model
and tests use the standard library. Requirements pin the direct plotting
dependency, not the complete transitive environment.

Windows PowerShell:

```powershell
py -m venv .venv
.\.venv\Scripts\python.exe -m pip install -r requirements.txt
.\.venv\Scripts\python.exe example.py --output outputs
.\.venv\Scripts\python.exe -m unittest -v
```

POSIX:

```sh
python3 -m venv .venv
.venv/bin/python -m pip install -r requirements.txt
.venv/bin/python example.py --output outputs
.venv/bin/python -m unittest -v
```

The included outputs were generated by the default command. `run_metadata.json`
records the source/manuscript hashes, environment, command, elapsed time, and
output hashes. There is no random sampling. SVG file metadata may differ between
runs; compare the exact JSON and CSV values for scientific reproducibility.

## Reuse and scope

```python
from example import SetCover, CoverReduction

problem = SetCover(4, ({0, 1, 2, 3}, {0}, {1}, {2}, {3}))
model = CoverReduction(problem, block_length=4)
candidate = model.canonical({1, 2, 3, 4})
assert model.network.is_raf(candidate)
assert model.decode(candidate) == {1, 2, 3, 4}
print(len(candidate))                      # 20
print(model.approximation({1, 2, 3, 4}))     # cover ratio 4, RAF ratio 5/2
```

Use `Network` directly for a different single-product reaction system, or replace
the cover-selection heuristic while keeping the construction and checked decoder.
Exact `all_covers`, `all_rafs`, `audit`, and ratio queries are intended for small
instances. The declared set/reaction caps prevent unintended exponential searches;
exceeding them raises an error. Constructing networks, checking a supplied cover,
decoding, and deletion/pruning do not enumerate all subsets. A larger default
input may need a model-only import workflow instead of the exhaustive entry run.

## Results and interpretation

The worked example has nine reactions. Directly testing all 512 reaction subsets
finds exactly three RAFs, corresponding to covers {0,1}, {0,2}, and {0,1,2}.
Their sizes are 7, 7, and 9. `covers.csv` records identifiers and closure depth;
`network.json` exposes every reaction and catalyst. `closure_stages.csv` shows
the food-generation stages of one minimum example.

`amplification.csv` varies M for a fixed four-element instance and singleton
cover. Exact rational arithmetic shows how the gate overhead affects approximation
ratios. When M >= m, a c-approximate RAF decodes to a cover with ratio at most
2c-1. Values below that condition are labelled inapplicable. M=1 still preserves
the optimum identity, but does not establish that approximation guarantee.

`irreducible_gap.csv` uses one whole-universe set and q singleton sets with M=q.
Deleting the universal block first returns q(q+1) reactions; deleting singleton
blocks first returns 2q. Both are irreducible. At q=8 these are 72 and 16, a ratio
of 9/2. Irreducibility alone therefore does not certify a good size approximation.
The figures display the gate/block accounting and the deletion-order gap.

Six test groups check the literal nine-reaction system; all 98 coverable indexed
three-set systems over two elements at two block lengths; closure and deletion
behavior; rational approximation transfer; the gap family; and rejected inputs
or exhausted budgets. The subset oracle uses the reaction model independently of
cover enumeration. These are exact finite checks, not a proof of complexity
inapproximability. The general hardness result and its complexity assumption
remain the manuscript theorem. No Lean compilation is claimed.

## License

MIT is proposed for this original example code, pending the owner's license
choice. No license grant is asserted here. This does not change the license of
the manuscript or any third-party dependency.