The complexity of solution-free sets of integers for general linear equations

DOI10.1016/J.DAM.2019.07.008MaRDI QIDQ2334046zbMATH OpenOpenAlexWikidataFDO

Authors Keith Edwards, Steven D. Noble

Publication date 6 November 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.09259, https://discovery.dundee.ac.uk/ws/files/35892025/sumfree_rev.pdf

zbMATH Keywords

computational complexitysolution-free set

Mathematics Subject Classification ID

Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a linear equation L, a set A of integers is L-free if A does not contain any non-trivial solutions to L. Meeks and Treglown showed that for certain kinds of linear equations, it is NP-complete to decide if a given set of integers contains a solution-free subset of a given size. Also, for equations involving three variables, they showed that the problem of determining the size of the largest solution-free subset is APX-hard, and that for two such equations (representing sum-free and progression-free sets), the problem of deciding if there is a solution-free subset with at least a specified proportion of the elements is also NP-complete. We answer a number of questions posed by Meeks and Treglown, by extending the results above to all linear equations, and showing that the problems remain hard for sets of integers whose elements are polynomially bounded in the size of the set. For most of these results, the integers can all be positive as long as the coefficients do not all have the same sign. We also consider the problem of counting the number of solution-free subsets of a given set, and show that this problem is #P-complete for any linear equation in at least three variables.

Recommendations

• On the complexity of finding and counting solution-free sets of integers
• On solution-free sets of integers
• Enumerating solution-free sets in the integers
• On solution-free sets of integers. II
• Solving a linear equation in a set of integers I

Cites work

• scientific article; zbMATH DE number 3232871 (Why is no real title available?)
• On Certain Sets of Integers
• On the complexity of finding and counting solution-free sets of integers
• Sets of integers with no large sum-free subset
• Some APX-completeness results for cubic graphs
• Some simplified NP-complete graph problems
• Systems of distinct representatives and linear algebra
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems

Cited in

(9)

• Upper bounds on the complexity of solving systems of linear equations
• On the complexity of finding and counting solution-free sets of integers
• Maximum \(k\)-sum \(\mathbf{n}\)-free sets of the 2-dimensional integer lattice
• On solution-free sets of integers
• On sets of linear forms of maximal complexity
• On solution-free sets for simultaneous quadratic and linear equations
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• Enumerating solution-free sets in the integers
• On solution-free sets of integers. II

This page was built for publication: The complexity of solution-free sets of integers for general linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334046)