Parameterized Algorithms for Covering by Arithmetic Progressions

Ivan Bliznets, Jesper Nederlof, Krisztina Szilágyi*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called Cover by Arithmetic Progressions (CAP) and Exact Cover by Arithmetic Progressions (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL’90]. We present a O(k2)poly(n) time algorithm for CAP and a 2O(k3)poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Zp, if p is a prime number part of the input.

Original languageEnglish
Title of host publicationSOFSEM 2024: Theory and Practice of Computer Science
Subtitle of host publicationTheory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings
EditorsHenning Fernau, Serge Gaspers, Ralf Klasing
Place of PublicationCham
PublisherSpringer
Pages125–138
Number of pages14
Edition1
ISBN (Electronic)978-3-031-52113-3
ISBN (Print)978-3-031-52112-6
DOIs
Publication statusPublished - 21 Jan 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14519 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Arithmetic Progressions
  • Number Theory
  • Set Cover
  • parameterized complexity theory

Fingerprint

Dive into the research topics of 'Parameterized Algorithms for Covering by Arithmetic Progressions'. Together they form a unique fingerprint.

Cite this