License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.73
URN: urn:nbn:de:0030-drops-181254
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18125/
Haviv, Ishay
On Finding Constrained Independent Sets in Cycles
Abstract
A subset of [n] = {1,2,…,n} is called stable if it forms an independent set in the cycle on the vertex set [n]. In 1978, Schrijver proved via a topological argument that for all integers n and k with n ≥ 2k, the family of stable k-subsets of [n] cannot be covered by n-2k+1 intersecting families. We study two total search problems whose totality relies on this result.
In the first problem, denoted by Schrijver(n,k,m), we are given an access to a coloring of the stable k-subsets of [n] with m = m(n,k) colors, where m ≤ n-2k+1, and the goal is to find a pair of disjoint subsets that are assigned the same color. While for m = n-2k+1 the problem is known to be PPA-complete, we prove that for m < d ⋅ ⌊n/(2k+d-2)⌋, with d being any fixed constant, the problem admits an efficient algorithm. For m = ⌊n/2⌋-2k+1, we prove that the problem is efficiently reducible to the Kneser problem. Motivated by the relation between the problems, we investigate the family of unstable k-subsets of [n], which might be of independent interest.
In the second problem, called Unfair Independent Set in Cycle, we are given ? subsets V_1, …, V_? of [n], where ? ≤ n-2k+1 and |V_i| ≥ 2 for all i ∈ [?], and the goal is to find a stable k-subset S of [n] satisfying the constraints |S ∩ V_i| ≤ |V_i|/2 for i ∈ [?]. We prove that the problem is PPA-complete and that its restriction to instances with n = 3k is at least as hard as the Cycle plus Triangles problem, for which no efficient algorithm is known. On the contrary, we prove that there exists a constant c for which the restriction of the problem to instances with n ≥ c ⋅ k can be solved in polynomial time.
BibTeX - Entry
@InProceedings{haviv:LIPIcs.ICALP.2023.73,
author = {Haviv, Ishay},
title = {{On Finding Constrained Independent Sets in Cycles}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {73:1--73:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18125},
URN = {urn:nbn:de:0030-drops-181254},
doi = {10.4230/LIPIcs.ICALP.2023.73},
annote = {Keywords: Schrijver graph, Kneser graph, Stable sets, PPA-completeness}
}
|
Keywords: |
|
Schrijver graph, Kneser graph, Stable sets, PPA-completeness |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
