Research map / Graph learning / GNN architectures
Graph Choosability via SAT: Beyond the Nullstellensatz
Markus Kirchweger, Tomáš Peitl, David Seka, Stefan Szeider
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the vetting method propagator (ablation) | SMS choosability encoding · Bipartite graphs, 9 vertices, width 5 | runtime (s): 2966.41 -> 7.02 s | Improved |
| add the vetting method propagator (ablation) | SMS choosability encoding · Tripartite graphs, 9 vertices, width 5 | runtime (s): 3705.66 -> 432.22 s | Improved |
| add the Nullstellensatz propagator alone (ablation) | SMS choosability encoding · Bipartite graphs, 9 vertices, width 5 | runtime (s): 2966.41 -> 2494.83 s | No clear effect |
| add Nullstellensatz propagator on top of vetting (ablation) | SMS choosability encoding · Bipartite graphs, 9 vertices, width 5 | runtime (s): 7.02 -> 6.62 s | No clear effect |
| add Nullstellensatz propagator on top of vetting (ablation) | SMS choosability encoding · Tripartite graphs, 9 vertices, width 6 | runtime (s): 11606.48 -> 9858.11 s | Improved |
| increase width bound by one color (ablation) | SMS choosability encoding · Bipartite graphs, 9 vertices (vet + ns) | runtime (s): 3.63 -> 6.62 s (width 4 -> 5) | Hurt |
| tighten width bound via Corollary 1 (8 to 7 colors) for 3-choosability (ablation) | SMS choosability encoding · gap graphs k=3, 9 vertices | search space | Improved |
| filter triangulations by jewel absence before Nullstellensatz check (ablation) | Nelsen's method · planar triangulations n=22..26 | runtime: only 3%-5% need NS check; 20-30x speedup | Improved |
| branching recursive polynomial expansion instead of direct expansion (ablation) | Nullstellensatz check · planar triangulations, n=17 | runtime (s): 6.5 minutes -> 2 seconds | Improved |
| reduce inscribed triangles to forbidden patterns (Lemma 9) with vetting | QBF encoding · 27-vertex planar graph 4-choosability | runtime (s): direct encoding infeasible -> 203 s vetting + 3 s CQesto | Improved |
Closest papers by meaning
- Breaking Symmetries in Quantified Graph Search: A Comparative Study (AAAI 2025 · similarity 0.85)
- A SAT + Computer Algebra System Verification of the Ramsey Problem R(3, 8) (Student Abstract) (AAAI 2024 · similarity 0.85)
- SAT-Based Algorithms for Regular Graph Pattern Matching (AAAI 2024 · similarity 0.82)
- Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs (AAAI 2025 · similarity 0.81)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.81)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
