The goal of this program is to check wether for a given graph there is a clique-acyclic superorientation with special nodes, that has no almost-kernel. See the definitions in the report. The problem is modeled as a constraint satisfaction problem, and solved using ortools.
In [1], we had a conjecture with T. Király, that a graph is h-perfect if and only if every clique-acyclic superorientation of it with special nodes has an almost-kernel (see also my PhD thesis [2]).
Recently, L. Lukács gave the problem to Claude as a test of its math capabilities, and after a few failed attemps with Claude Opus 4.7, Claude Opus 4.8 could solve it, and found a 14 node counterexample: a graph that is not h-perfect, but every clique-acyclic superorientation of it with special nodes has an almost-kernel. To triple check, we both wrote checkers for the second condition (the other side, that the graph is not h-perfect is easier to verify).
[1] T. Király, J. Pap, Kernels, stable matchings, and Scarf's Lemma, RIMS Kokyuroku Bessatsu B23: Combinatorial Optimization and Discrete Algorithms, (ed. S. Iwata), (2010), pp 131-145. Open access: https://www.kurims.kyoto-u.ac.jp/~kenkyubu/bessatsu/open/B23/pdf/B23_007.pdf
[2] J. Pap, Integrality, complexity and colourings in polyhedral combinatorics, PhD thesis. Pdf: https://teo.elte.hu/minosites/ertekezes2012/pap_j.pdf
To install the Python packages used, create a virtual environment, activate it and use pip:
python -m venv venv
source venv/bin/activate
pip install --upgrade pip
pip install -r src/requirements.txt
On Linux, you might need to install these C dependencies:
sudo apt install libcdd-dev libgmp-dev
Claude's and my code use some Python package dependencies, so you'll need to first activate the virtual environment you installed them in. Laci's code doesnt' have any dependencies.
You can run Claude's (fixed) check for the counterexample by
cd src/Claude
python certify_counterexample__fixed.py
You can run Laci's checker by running the src/Laci/run_parallel.sh script.
You can run my code by
cd src/Juli
python check_counterexample.py