On the complexity of finding and counting solution-free sets of integers
From MaRDI portal
Publication:1752464
DOI10.1016/j.dam.2018.02.008zbMath1425.68146arXiv1704.03758OpenAlexW2964105244WikidataQ130111012 ScholiaQ130111012MaRDI QIDQ1752464
Publication date: 24 May 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.03758
Analysis of algorithms and problem complexity (68Q25) Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30)
Related Items (2)
Maximum \(k\)-sum \(\mathbf{n}\)-free sets of the 2-dimensional integer lattice ⋮ The complexity of solution-free sets of integers for general linear equations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Hypergraph containers
- On Roth's theorem on progressions
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Sets of integers with no large sum-free subset
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- On the parameterized complexity of multiple-interval graph problems
- Sidon sets in groups and induced subgraphs of Cayley graphs
- On subsets of abelian groups with no 3-term arithmetic progression
- A density version of a geometric Ramsey theorem
- Selection of a large sum-free subset in polynomial time
- Estimates related to sumfree subsets of sets of integers
- Progression-free sets in finite abelian groups.
- Some APX-completeness results for cubic graphs
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- An improved construction of progression-free sets
- PRIMES is in P
- Sum-free sets in abelian groups
- Sum-free sets in groups: a survey
- Parametrized complexity theory.
- The number of maximal sum-free subsets of integers
- A Note on Elkin’s Improvement of Behrend’s Construction
- A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
- Quasirandom Groups
- On sets of integers containing k elements in arithmetic progression
- Notes on Sum-Free and Related Sets
- Solving a linear equation in a set of integers I
- Finding Points in General Position
- The Number of Subsets of Integers with Nok-Term Arithmetic Progression
- The Parameterized Complexity of Counting Problems
- THE CAMERON–ERDOS CONJECTURE
- Solving a linear equation in a set of integers II
- Independent sets in hypergraphs
- On solution-free sets of integers II
- Kernelizations for Parameterized Counting Problems
- Maximal sum-free sets of elements of finite groups
- On Certain Sets of Integers
This page was built for publication: On the complexity of finding and counting solution-free sets of integers
