Document Open Access Logo

A Fixed-Parameter Algorithm for the Schrijver Problem

Author Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.16.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Ishay Haviv
  • School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel

Funding

Research supported in part by the Israel Science Foundation (grant No. 1218/20).

Acknowledgements

We thank Gabriel Istrate for clarifications on [Gabriel Istrate et al., 2021] and the anonymous reviewers for their useful suggestions.

Cite As Get BibTex

Ishay Haviv. A Fixed-Parameter Algorithm for the Schrijver Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.16

Abstract

The Schrijver graph S(n,k) is defined for integers n and k with n ≥ 2k as the graph whose vertices are all the k-subsets of {1,2,…,n} that do not include two consecutive elements modulo n, where two such sets are adjacent if they are disjoint. A result of Schrijver asserts that the chromatic number of S(n,k) is n-2k+2 (Nieuw Arch. Wiskd., 1978). In the computational Schrijver problem, we are given an access to a coloring of the vertices of S(n,k) with n-2k+1 colors, and the goal is to find a monochromatic edge. The Schrijver problem is known to be complete in the complexity class PPA. We prove that it can be solved by a randomized algorithm with running time n^O(1) ⋅ k^O(k), hence it is fixed-parameter tractable with respect to the parameter k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Schrijver graph
  • Kneser graph
  • Fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Imre Bárány. A short proof of Kneser’s conjecture. J. Comb. Theory, Ser. A, 25(3):325-326, 1978. Google Scholar
  2. Karol Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae, 20(1):177-190, 1933. Google Scholar
  3. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  4. Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Constant inapproximability for PPA. In Proc. of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC'22), pages 1010-1023, 2022. Google Scholar
  5. Xiaotie Deng, Zhe Feng, and Rucha Kulkarni. Octahedral Tucker is PPA-complete. Electronic Colloquium on Computational Complexity (ECCC), 24:118, 2017. Google Scholar
  6. Paul Erdös, Chao Ko, and Richard Rado. Intersection theorems for systems of finite sets. Quart. J. Math., 12(1):313-320, 1961. Google Scholar
  7. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus halving is PPA-complete. In Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18), pages 51-64, 2018. Google Scholar
  8. Aris Filos-Ratsikas and Paul W. Goldberg. The complexity of splitting necklaces and bisecting ham sandwiches. In Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC'19), pages 638-649, 2019. Google Scholar
  9. Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. A topological characterization of modulo-p arguments and implications for necklace splitting. In Proc. of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA'21), pages 2615-2634, 2021. Google Scholar
  10. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  11. Peter Frankl and Andrey Kupavskii. Maximal degrees in subgraphs of Kneser graphs. arXiv, abs/2004.08718, 2020. URL: http://arxiv.org/abs/2004.08718.
  12. David Gale. Neighboring vertices on a convex polyhedron. In H. W. Kuhn and A.W. Tucker, editors, Linear Inequalities and Related Systems, volume 38 of Annals of Math. Studies, pages 255-263. Princeton University Press, 1956. Google Scholar
  13. Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. Consensus halving for sets of items. In Proc. 16th Web and Internet Economics International Conference (WINE'20), pages 384-397, 2020. Google Scholar
  14. Ishay Haviv. The complexity of finding fair independent sets in cycles. In 12th Innovations in Theoretical Computer Science Conference (ITCS'21), pages 4:1-4:14, 2021. Google Scholar
  15. Ishay Haviv. A fixed-parameter algorithm for the Kneser problem. In 49th International Colloquium on Automata, Languages, and Programming (ICALP'22), pages 72:1-72:18, 2022. Google Scholar
  16. Anthony J. W. Hilton and Eric Charles Milner. Some intersection theorems for systems of finite sets. Quart. J. Math., 18(1):369-384, 1967. Google Scholar
  17. Charles R. Hobby and John R. Rice. A moment problem in L₁ approximation. Proc. Amer. Math. Soc., 16(4):665-670, 1965. Google Scholar
  18. Gabriel Istrate, Cosmin Bonchis, and Adrian Craciun. Kernelization, proof complexity and social choice. In 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), pages 135:1-135:21, 2021. Google Scholar
  19. Martin Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2):27, 1955. Google Scholar
  20. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A, 25(3):319-324, 1978. Google Scholar
  21. Pasin Manurangsi and Warut Suksompong. Computing a small agreeable set of indivisible items. Artif. Intell., 268:96-114, 2019. Preliminary versions in IJCAI'16 and IJCAI'17. Google Scholar
  22. Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer Publishing Company, Incorporated, 2007. Google Scholar
  23. Colin McDiarmid. Concentration. In Probabilistic methods for algorithmic discrete mathematics, volume 16 of Algorithms Combin., pages 195-248. Springer, Berlin, 1998. Google Scholar
  24. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theor. Comput. Sci., 81(2):317-324, 1991. Google Scholar
  25. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. Google Scholar
  26. Alexander Schrijver. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wiskd., 26(3):454-461, 1978. Google Scholar
  27. Forest W. Simmons and Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Soc. Sci., 45(1):15-25, 2003. Google Scholar
  28. John Talbot. Intersecting families of separated sets. J. London Math. Soc., 68(1):37-51, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact