Parameterized Algorithms for Covering by Arithmetic Progressions

Ivan Bliznets; Jesper Nederlof; Krisztina Szilágyi

doi:10.1007/978-3-031-52113-3_9

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 proceeding › Chapter › Academic › peer-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 2^O^(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 Z_p, if p is a prime number part of the input.

Original language	English
Title of host publication	SOFSEM 2024: Theory and Practice of Computer Science
Subtitle of host publication	Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings
Editors	Henning Fernau, Serge Gaspers, Ralf Klasing
Place of Publication	Cham
Publisher	Springer
Pages	125–138
Number of pages	14
Edition	1
ISBN (Electronic)	978-3-031-52113-3
ISBN (Print)	978-3-031-52112-6
DOIs	https://doi.org/10.1007/978-3-031-52113-3_9
Publication status	Published - 21 Jan 2024

Publication series

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

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Funding

Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 853234).

Funders	Funder number
European Research Council
Horizon 2020 Framework Programme	853234
Horizon 2020 Framework Programme

Keywords

Arithmetic Progressions
Number Theory
Set Cover
parameterized complexity theory

Access to Document

10.1007/978-3-031-52113-3_9

978-3-031-52113-3_9Final published version, 375 KBLicence: Taverne

Cite this

Bliznets, I., Nederlof, J., & Szilágyi, K. (2024). Parameterized Algorithms for Covering by Arithmetic Progressions. In H. Fernau, S. Gaspers, & R. Klasing (Eds.), SOFSEM 2024: Theory and Practice of Computer Science: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings (1 ed., pp. 125–138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14519 LNCS). Springer. https://doi.org/10.1007/978-3-031-52113-3_9

Bliznets, Ivan ; Nederlof, Jesper ; Szilágyi, Krisztina. / Parameterized Algorithms for Covering by Arithmetic Progressions. SOFSEM 2024: Theory and Practice of Computer Science: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings. editor / Henning Fernau ; Serge Gaspers ; Ralf Klasing. 1. ed. Cham : Springer, 2024. pp. 125–138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{e4b1b10056234425992556af04ac0f10,

title = "Parameterized Algorithms for Covering by Arithmetic Progressions",

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{\textquoteright}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.",

keywords = "Arithmetic Progressions, Number Theory, Set Cover, parameterized complexity theory",

author = "Ivan Bliznets and Jesper Nederlof and Krisztina Szil{\'a}gyi",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.",

year = "2024",

month = jan,

day = "21",

doi = "10.1007/978-3-031-52113-3_9",

language = "English",

isbn = "978-3-031-52112-6",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "125–138",

editor = "Fernau, {Henning } and Gaspers, {Serge } and Klasing, {Ralf }",

booktitle = "SOFSEM 2024: Theory and Practice of Computer Science",

edition = "1",

}

Bliznets, I, Nederlof, J & Szilágyi, K 2024, Parameterized Algorithms for Covering by Arithmetic Progressions. in H Fernau, S Gaspers & R Klasing (eds), SOFSEM 2024: Theory and Practice of Computer Science: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14519 LNCS, Springer, Cham, pp. 125–138. https://doi.org/10.1007/978-3-031-52113-3_9

Parameterized Algorithms for Covering by Arithmetic Progressions. / Bliznets, Ivan; Nederlof, Jesper; Szilágyi, Krisztina.
SOFSEM 2024: Theory and Practice of Computer Science: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings. ed. / Henning Fernau; Serge Gaspers; Ralf Klasing. 1. ed. Cham: Springer, 2024. p. 125–138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14519 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Parameterized Algorithms for Covering by Arithmetic Progressions

AU - Bliznets, Ivan

AU - Nederlof, Jesper

AU - Szilágyi, Krisztina

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024/1/21

Y1 - 2024/1/21

N2 - 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.

AB - 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.

KW - Arithmetic Progressions

KW - Number Theory

KW - Set Cover

KW - parameterized complexity theory

UR - http://www.scopus.com/inward/record.url?scp=85185827783&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-52113-3_9

DO - 10.1007/978-3-031-52113-3_9

M3 - Chapter

SN - 978-3-031-52112-6

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 125

EP - 138

BT - SOFSEM 2024: Theory and Practice of Computer Science

A2 - Fernau, Henning

A2 - Gaspers, Serge

A2 - Klasing, Ralf

PB - Springer

CY - Cham

ER -

Bliznets I, Nederlof J, Szilágyi K. Parameterized Algorithms for Covering by Arithmetic Progressions. In Fernau H, Gaspers S, Klasing R, editors, SOFSEM 2024: Theory and Practice of Computer Science: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings. 1 ed. Cham: Springer. 2024. p. 125–138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-52113-3_9