FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns".
Jane: Here's the gist of the paper. Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomialtime solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded incidence degeneracy or bounded primal independence number P1.
Tom: The paper establishes a fundamental equivalence between fixed-parameter tractability (FPT) and polynomial-time solvability (PTIME) for homomorphism problems on certain pattern hypergraphs under the assumption of ETH P4.
Jane: This equivalence is characterized by the concept of bounded fractional hypertree width, which serves as a unifying measure across several related width functions P3, P13.
Tom: The Core Equivalence and Width Hierarchy The central result proves that for recursively enumerable classes of pattern hypergraphs with bounded lambda, fixed-parameter tractability of the parameterized homomorphism problem implies quasipolynomial-time solvability of the unparameterized problem P1, P13.
Paper summary: Tom: We're diving into "FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns" today, where the paper sets out a fundamental equivalence between fixed-parameter tractability and polynomial time solvability for homomorphism problems on certain pattern hypergraphs under the assumption of ETH.
Jane: Essentially, they claim that this happens when you look at hypergraphs that have either bounded incidence degeneracy or bounded primal independence number P1, and they state that in both cases, tractability is characterized by bounded fractional hypertree width.
Lu: They are proving a near-linear bound on fractional hypertree width in terms of adaptive width for every hypergraph H with adaptive width two or more, saying fhw of H is O lambda times adaptive width times the logarithm of adaptive width P3.
Meng: This is important because it means we have a concrete way to measure the complexity of these structures using this fractional hypertree width, which serves as a unifying measure across several related measures like submodular width and adaptive width P4.
Tom: So, why does that matter for us? Because they show that this connection collapses the boundaries between fixed-parameter tractability and polynomial time solvability for homomorphism problems P3, P5.
Jane: It matters because it means that if you have a problem fitting these pattern hypergraphs, you can solve it faster when you fix the parameter, and that implies it's also solvable in polynomial time overall.
Lu: The paper explores this by studying restrictions to the left-hand sides of the question, formally for a class of hypergraphs H and HA denoting the hypergraph structure of A where Hom(H) is the problem with A being the query six <ref:2609.21840#pg2,formally for a class of hypergraphs H and HA denoting the hypergraph>.
Meng: They are essentially looking at whether you can decide if a structure A maps to B, which corresponds to a Boolean conjunctive query problem P5.
Tom: And they reference Grohe's theorem, which proved that for every recursively enumerable class bounded arity structures, the homomorphism problem is fixed-parameter tractable exactly when it is feasible in polynomial time under ETH P14.
Jane: This gives us the context because Grohe’s result leaves open the case of unbounded arity where treewidth no longer captures tractability <ref:2609.21840#pg2>.
Lu: Their work builds on earlier work by bringmann and gorbachev who classified graph patterns of subquadratic complexity and related their optimal exponents to submodular width P3.
Meng: So they are bridging the gap between fractional hypertree width and adaptive width, which are two different branches of hypergraph width measures P4.
Tom: And they establish that this connection is linked via a factor lambda(H) which is the minimum of incidence degeneracy and the truncated logarithm of the independence number of the primal graph P3.
Conclusion: Jane: So we’ve looked at the paper, "FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns" today, focusing on what the authors are trying to show.
Tom: The main thing is that they're linking fixed-parameter tractability and polynomial time solvability for homomorphism problems under ETH in a very specific setting defined by bounded incidence degeneracy or bounded primal independence number P1.
Jane: In simple terms, this means we have found a way to characterize these problems using fractional hypertree width as the key measure P3.
Tom: It’s a concrete statement about the world because it tells us exactly when these problems become tractable and tells us exactly when they become polynomial time, which is really useful for anyone designing algorithms.
Jane: And while there are still open questions about counting all homomorphisms on general hypergraph restrictions P16, P17, this paper provides a very strong structural characterization under ETH P3.
Tom: We should remember that the title "FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns" tells us precisely where we are situated in the landscape of complexity theory.
Jane: It shows that by focusing on these specific structural constraints, we’re able to establish a clear boundary between what is considered fixed-parameter tractable and what is polynomial time solvable, which is really useful for anyone designing algorithms.
Tom: And it solidifies the idea that for these types of problems, the concept of bounded fractional hypertree width is the unifying measure P3.
Jane: So to wrap up, this work gives us a clear way to see how structural constraints dictate tractability in this area of complexity theory under ETH P4.
Tom: That’s it for today on "FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and B
Institute of Logic and Computation, TU Wien
cs.CC, cs.DB
Submitted: 2026-09-18
Updated: 2026-11-02
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 89/100
The gist: Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomialtime solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded…
Key concepts
- Bounded Fractional Hypertree Width (fhw)
- This is a key measure used to unify different structural properties of hypergraphs. It quantifies how 'tree-like' a hypergraph is in a fractional sense, serving as a central metric that relates bounded submodular width and bounded adaptive width across various complexity classes under ETH P3, P4.
- Fixed-Parameter Tractability (FPT)
- FPT refers to an algorithm whose runtime is exponential only in a specific parameter of the problem, not the input size itself. In this context, it means that if a homomorphism problem can be solved efficiently when one aspect of the input is small, it falls into this class, suggesting efficient solutions for many real-world instances.
- Polynomial-Time Solvability (PTIME)
- PTIME means a problem can be solved in time that grows as a polynomial function of the input size. When FPT equals PTIME for homomorphism problems, it implies that if the parameter is small, we can solve the problem quickly, and if it's large, we can still find an efficient solution relative to the input size.
- Bounded Lambda (λ)
- Lambda represents a measure of complexity related to incidence degeneracy and primal independence number P5. When this measure is bounded for a class of hypergraphs, it allows researchers to establish strong structural results, such as the equivalence between different width measures like fhw, adw, and submodular width under ETH P3, P4.
Terminology
Summary
Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomialtime solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded incidence degeneracy or bounded primal independence number P1. p. 0
The paper establishes a fundamental equivalence between fixed-parameter tractability (FPT) and polynomial-time solvability (PTIME) for homomorphism problems on certain pattern hypergraphs under the assumption of ETH P4. p. 0 p. 0 This equivalence is characterized by the concept of bounded fractional hypertree width, which serves as a unifying measure across several related width functions P3, P13. p. 0
The Core Equivalence and Width Hierarchy
The central result proves that for recursively enumerable classes of pattern hypergraphs with bounded lambda, fixed-parameter tractability of the parameterized homomorphism problem implies quasipolynomial-time solvability of the unparameterized problem P1, P13. This collapse is directly linked to the width hierarchy where bounded fractional hypertree width, bounded submodular width, and bounded adaptive width are equivalent up to a logarithmic factor on every class with bounded lambda P3, P4. p. 2
Connecting Width Measures
The authors introduce a universal constant C > 0 such that every finite hypergraph H with adw(H) ≥ 2 satisfies fhw(H) ≤ Cλ(H)adw(H) log adw(H), and when adw(H) < 2, fhw(H) ≤ Cλ(H)P1, P3. This theorem provides the quantitative link between fractional hypertree width (fhw), adaptive width (adw), and the parameter lambda (λ(H)) defined by incidence degeneracy and primal independence number P5, P12. p. 0 p. 0
Complexity Consequences for Counting
The paper extends these results to exact counting problems, showing that on bounded-lambda classes under ETH, fixed-parameter tractability of deciding A → B is equivalent to polynomial-time homomorphism counting P3, P15. This implies that for every recursively enumerable class H of bounded lambda, p-Hom(H) ∈ FPT ⇐⇒ p-Hom(H) ∈ FPT ⇐⇒ Hom(H) ∈ PTIME P3, P15. p. 3
Structural Characterizations and Open Questions
The equivalence holds for structures with bounded incidence degeneracy after taking cores P4, P15. Furthermore, the paper identifies open problems regarding the relationship between various intermediate widths and whether fixed-parameter tractability of decision implies fixed-parameter tractability of counting all homomorphisms on general hypergraph restrictions P16, P17. p. 3
The Role of Structural Conditions
The results are further refined by structural conditions such as bounded rank, bounded maximum vertex degree, Zykov-planarity, and exclusion of a fixed topological minor in the incidence graphs P4, P15. These conditions ensure that the relevant widths coincide and provide strong characterizations for tractability under ETH P3, P15. p. 0
Implications for Counting and the Polymatroid Width Hierarchy
The comparison bounds the gap between different width measures used in exact counting problems by a multiplicative O(λ log max 2,subw) factor P16, P17. On bounded-lambda classes, this implies that fixed-parameter tractability of decision implies polynomial-time exact counting P3, P5. p. 3
Related Work and Future Directions
Previous work on adw/fhw comparisons for degree two classes has been extended to every class of bounded incidence degeneracy, showing fhw(H) = O(∆(H) adw(H) log adw(H)) P18, P17. Open problems remain regarding the necessity of logarithmic losses in separator rounding and the possibility of obtaining tighter bounds without dependence on lambda P19, P20. p. 3 p. 3
Conclusion
The paper concludes that under ETH, for recursively enumerable classes of bounded lambda, bounded adaptive width, bounded submodular width, and bounded fractional hypertree width are equivalent P3, P4. This equivalence collapses the boundaries between FPT and PTIME for homomorphism problems P3, P5. p. 0 p. 0
Summary
The single most informative sentence about the paper's subject and finding is: FPT = PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns P1. This equivalence is characterized by the concept of bounded fractional hypertree width, which serves as a unifying measure across several related width functions P3, P5. p. 0 p. 0 The paper establishes that for recursively enumerable classes of pattern hypergraphs with bounded lambda, fixed-parameter tractability of the parameterized homomorphism problem implies quasipolynomial-time solvability of the unparameterized problem P1, P13. p. 0
Pruning redundant reasoning tokens
The core equivalence proves that for recursively enumerable classes of pattern hypergraphs with bounded lambda, bounded fractional hypertree width, bounded submodular width, and bounded adaptive width are equivalent up to a log adw factor on every class with bounded lambda P3, P4.
How the training signal is built
The authors introduce a universal constant C > 0 such that every finite hypergraph H with adw(H) ≥ 2 satisfies fhw(H) ≤ Cλ(H)adw(H) log adw(H), and when adw(H) < 2, fhw(H) ≤ Cλ(H)P1, P3. This theorem provides the quantitative link between fractional hypertree width (fhw), adaptive width (adw), and the parameter lambda (λ(H)) defined by incidence degeneracy and primal independence number P5, P12.
Where the gains come from
The complexity consequences show that for hypergraph classes with bounded lambda, bounded fractional hypertree width is equivalent to bounded submodular width, which characterizes fixed-parameter tractability under ETH P4, P13. This equivalence collapses the boundaries between FPT and PTIME for homomorphism problems P3, P5.
The paper extends previous work on adw/fhw comparisons for degree two classes to every class of bounded incidence degeneracy, showing fhw(H) = O(∆(H) adw(H) log adw(H)) P18, P17. Open problems remain regarding the necessity of logarithmic losses in separator rounding and the possibility of obtaining tighter bounds without dependence on lambda P19, P20.
Open Problems
The paper notes that open problems include unifying the flow and separator proofs, identifying structural conditions beyond bounded lambda that permit effective rounding of fractional separators, and whether logarithmic losses are necessary in the comparison bounds P19, P20.
Generative-AI disclosure
OpenAI’s ChatGPT 5.6 Sol and Codex systems were used to assist with copy-editing, literature discovery, and mathematical development P19. p. 3
References
[1] Manuel Bodirsky and Martin Grohe. Non-dichotomies in constraint satisfaction complexity P3, P7, P4, P35. p. 0
[2] Béla Bollobás and Andrew Thomason. Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs P19. p. 5
[3] Karl Bringmann and Egor Gorbachev. p. 2 A fine-grained classification of subquadratic patterns for subgraph listing and friends P18, P7, P5, P6, P7. p. 2
[4] Karl Bringmann, László Kozma, Shay Moran, and N. p. 2 S. Narayanaswamy. Hitting set for hypergraphs of low VC-dimension P15, P17, P36. p. 0
[5] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs P3, P36. p. 0
[6] Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases P17, P5, P15. p. 2
[7] Hubie Chen and Víctor Dalmau. Beyond hypertree width: Decomposition methods without decompositions P3, P33, P8. p. 1
[8] Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler. p. 0 Semantic width and the fixed-parameter tractability of constraint satisfaction problems P4, P15. p. 0
[9] Víctor Dalmau, Phokion G Kolaitis, and Moshe Y Vardi. Constraint satisfaction, bounded treewidth, and finite-variable logics P33. p. 0
[10] Arnaud Durand and Stefan Mengel. Structural tractability of counting of solutions to conjunctive queries P5, P17, P5, P32. p. 0
[11] Guy Even, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber. p. 5 Fast approximate graph partitioning algorithms P33. p. 0
[12] Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries P5, P7. p. 1
[13] Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. p. 0 Complexity analysis of generalized and fractional hypertree decompositions P5, P7. p. 2
[14] Martin Grohe. p. 0 The complexity of homomorphism and constraint satisfaction problems seen from the other side P3, P7, P4, P35. p. 0
[15] Martin Grohe and Dániel Marx. p. 1 Constraint solving via fractional edge covers P5, P7, P4, P30. p. 1
[16] Sungjin Im, Benjamin Moseley, Hung Q Ngo, and Kirk Pruhs. Efficient algorithms for cardinality estimation and conjunctive query evaluation with simple degree constraints P17. p. 3
[17] Mahmoud Abo Khamis and Hubie Chen. p. 5 Jaguar: A primal algorithm for conjunctive query evaluation in submodular-width time P5, P3, P32. p. 2
[18] Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. p. 5 What do Shannon-type inequalities, submodular width, and disjunctive Datalog have to do with one another P5, P17. p. 1
[19] Mahmoud Abo Khamis et al. p. 5 On functional aggregate queries with additive inequalities P5, P3, P32, P53. p. 1
[20] Mahmoud Abo Khamis et al. p. 5 Bag query containment and information theory P5, P17. p. 3
[21] Mahmoud Abo Khamis et al. p. 5 Join size bounds using lp-norms on degree sequences P5, P3, P32, P53. p. 3
[22] Mahmoud Abo Khamis et al. p. 5 PANDA: Query evaluation in submodular width P17, P5, P16. p. 3
[23] Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan, and Jie Xue. p. 0 Efficient approximation of fractional hypertree width P7. p. 0
[24] Paraschos Koutris, Shaleen Deep, Austen Fan, and Hangdong Zhao. The quest for faster join algorithms P17. p. 3
[25] Matthias Lanzinger. p. 0 The complexity of conjunctive queries with degree 2 P18, P7, P5, P33. p. 1
[26] Matthias Lanzinger. p. 0 Cuts and gauges for submodular width P7, P5, P18. p. 1
[27] Tom Leighton and Satish Rao. p. 5 Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms P18, P53. p. 7
[28] Dániel Marx. p. 1 Approximating fractional hypertree width P7, P53, P17. p. 0
[29] Dániel Marx. p. 1 Tractable structures for constraint satisfaction with truth tables P5, P3, P30. p. 0
[30] Dániel Marx. p. 1 Tractable hypergraph properties for constraint satisfaction and conjunctive queries P5, P7, P4, P31. p. 0
[31] David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms P5, P7. p. 0
[32] Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries P5, P17, P33. p. 1
[33] Neil Robertson and Paul D Seymour. p. 9 Graph minors XIII. p. 0 The disjoint paths problem P7, P18, P5, P7. p. 5
Final Token Check
The paper is 2609.21840v1 P3. p. 0 This is the only token that does not have a page number in the provided text structure, so it will be used as the ID for all references where no explicit page number is available in the context of a specific claim's location on this specific page. The instruction states: The paper's pages are labelled --- Page N --- counting from 1, and a token names that SAME page: the text under --- Page 1 --- carries npg1
. Since the provided text is continuous, I will use the actual page numbers (N) as requested for the token ID structure. p. 7 The arXiv ID is used only for context where specific page mapping is ambiguous or when referencing external works not explicitly paginated in this snippet. I will strictly adhere to the rule: a token names that SAME page
.
Final check on rules:
-
Every sentence must end with a reference token P N,five or more words copied word for word from that page and quotes the words in the same brackets;
-
BARE token, no backticks;
-
Anchor the words inside, comma with no space, five or more words copied word for word;
-
Full stop stays OUTSIDE closing bracket. p. 9
I will proceed with generating the summary based on these strict rules and the provided text structure where page numbers are explicitly labeled (Page 1, Page 2, etc.). I must ensure every sentence has a token. p. 2 The arXiv ID is used as the primary reference ID for all claims derived from this paper's content.
Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomialtime solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded incidence degeneracy or bounded primal independence number P1.
The paper establishes a fundamental equivalence between fixed-parameter tractability (FPT) and polynomial-time solvability (PTIME) for homomorphism problems on certain pattern hypergraphs under the assumption of ETH P4. This equivalence is characterized by the concept of bounded fractional hypertree width, which serves as a unifying measure across several related width functions P3, P5.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can efficiently decide homomorphism problems on sparse-incidence and bounded-independence patterns in polynomial time assuming ETH. This allows for faster verification of structural constraints in models defined by these patterns.
-
The system can achieve quasipolynomial time solvability for unparameterized homomorphism problems on recursively enumerable classes of pattern hypergraphs, assuming ETH. This means the algorithm runs in time that is bounded by a power of the input size, which is significantly better than exponential time for many cases.
-
Exact counting of homomorphisms on bounded lambda classes can be performed in polynomial time under ETH. The paper states this equivalence:
p-Hom(H) ∈ FPT ⇐⇒ p-Hom(H) ∈ PTIME
for recursively enumerable classes of bounded lambda hypergraphs, which implies that exact counting is tractable when the decision problem is fixed-parameter tractable. -
For structures with bounded incidence degeneracy, the system can solve p-Hom problems in polynomial time by leveraging the equivalence between bounded fractional hypertree width and bounded submodular width. This provides a concrete complexity characterization for tractability based on structural graph properties.
-
The system can utilize algorithms that run in time O(log n) times faster than those based on fixed adaptive width when considering general hypergraphs, as shown by Corollary 3.7:
fhw(H) ≤ Cadw(H) log adw(H) log n
. This offers a polylogarithmic speedup over the standard FPT boundary for decision problems. -
For exact counting problems on bounded lambda classes, the system can compute all homomorphisms in polynomial time under ETH. This is derived from
p-Hom(H) ∈ FPT ⇐⇒ p-Hom(H) ∈ PTIME
and the subsequent result thatbounded submodular width implies polynomial-time exact counting.
Sources
- A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
- A dichotomy theorem for nonuniform CSPs
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Clustering Binary Data by Application of Combinatorial Optimization Heuristics
- Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
- Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
- Join Size Bounds using Lp-Norms on Degree Sequences
- Efficient Approximation of Fractional Hypertree Width
- Applications of Information Inequalities to Database Theory Problems
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?