# Constraint Solving via Fractional Edge Covers

arXiv: https://arxiv.org/abs/1711.04506 · HTML: https://mlsanity.com/paper/1711.04506/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2017.

## Built on by (most cited first, 5 of 5)

- [Epistemic Logic Programs: Non-Ground and Counting Complexity](https://mlsanity.com/paper/2503.04731/) (2025)
- [Graphical Join: A New Physical Join Algorithm for RDBMSs](https://mlsanity.com/paper/2206.10435/) (2022)
- [Computing a partition function of a generalized pattern-based energy over a semiring](https://mlsanity.com/paper/2305.17526/) (2023)
- [Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability](https://mlsanity.com/paper/2311.14579/) (2023)
- [Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue](https://mlsanity.com/paper/2502.20233/) (2025)

## Abstract (arXiv)

Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this paper, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number. Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that a the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions by Marx, it follows that bounded fractional hypertree width is now the most general known structural property that guarantees polynomial-time solvability.