Vertex Cover → External macro data compression Construction open

Unsolved

Clone https://github.com/reduction-zoo/vertex-cover-external-macro-compression to investigate Vertex Cover → External macro data compression. Read the fixed question and state. Use preparation notes, the test corpus, and verifier if present; otherwise complete Prepare before a reduction attempt. Follow the repository instructions and your AutoResearch pipeline.

Submit a solution

Why this question matters

This reconstructs a rule for selecting reusable dictionary phrases under an explicit storage-cost model.

The cited source points to Storer and Storer-Szymanski compression results. Recovering their precise construction and compatible pointer conventions is part of the task, rather than a new claim of compression hardness.

The reduction to construct

Given a finite simple graph and k, return a vertex cover of size at most k, or NO-SOLUTION. All finite combinatorial structures are explicit and numerical data use binary encoding.

Given a finite string s, pointer cost h and budget B, return a dictionary D and compressed string C composed of literals and pointers to substrings of D. Recursive replacement must terminate and expand C to s. Count every literal as one unit and every pointer occurrence as h units across both D and C; require total cost at most B. Encode pointer destinations and substring endpoints explicitly.

Construct deterministic polynomial-time maps F and G. F must produce a legal target instance, and G(x,y) must return a valid source output for every valid target output y, including NO-SOLUTION. A complete rule may reconstruct a published construction or give a new one; it must specify every gadget, numerical parameter and decoding step.

Three tested gadget families admitted false-YES encodings through arbitrary dictionary intervals. A valid converse must account for all legal pointer sharing and dictionary overlaps, with explicit pointer costs and recursive expansion semantics.

What a complete answer must include

Deliver executable instance construction and output recovery, a general proof covering all legal inputs and target outputs, and worst-case polynomial time and encoding-size bounds. Cite the actual proof used, or identify a newly derived argument. Check small positive and negative instances with independent solvers; finite tests alone do not establish correctness.

References

Literature checked 2026-09-25. Seven research rounds checked the classical EPM definition and adjacent constructions, but did not retrieve the full Storer proof or establish a compatible reduction. A 120-case independent source corpus and three finite gadget counterexamples support the recorded negative findings; no general result or independent review is claimed.