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

Keith Edwards (Lead / Corresponding author), Steven D. Noble

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
10 Downloads (Pure)

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 (2018) 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.

Original languageEnglish
Pages (from-to)115-133
Number of pages19
JournalDiscrete Applied Mathematics
Volume270
Early online date23 Jul 2019
DOIs
Publication statusPublished - 1 Nov 2019

Keywords

  • solution-free set
  • computational complexity
  • Solution-free set
  • Computational complexity

Fingerprint Dive into the research topics of 'The complexity of solution-free sets of integers for general linear equations'. Together they form a unique fingerprint.

Cite this