8 citations · 59 across the 30 of their papers we have counts for
32 papers
Tractability of Quantified Temporal Constraints To The Max
Manuel Bodirsky, Hubie Chen, Michał Wrona
A temporal constraint language is a set of relations that are first-order definable over (Q;<). We show that several temporal constraint languages whose constraint satisfaction pro…
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
Hubie Chen
The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not t…
Best-case and Worst-case Sparsifiability of Boolean CSPs
Hubie Chen, Bart M. P. Jansen, Astrid Pieterse
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number…
Homomorphisms are indeed a good basis for counting: Three fixed-template dichotomy theorems, for the price of one
Hubie Chen
Many natural combinatorial quantities can be expressed by counting the number of homomorphisms to a fixed relational structure. For example, the number of 3-colorings of an undirec…
Testing Assignments to Constraint Satisfaction Problems
Hubie Chen, Matt Valeriote, Yuichi Yoshida
For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered he…