2 papers
cs.DM2026
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
The non-redundancy (NRD) of a constraint satisfaction problem (CSP) is a combinatorial quantity closely tied to the behavior of CSPs in various computational models including their…
cs.DS2024
Preprocessing to Reduce the Search Space for Odd Cycle Transversal
Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan +1
The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph breaks all odd cycles, and thereby yields a bipartite graph…