2026-07-26T02:11:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17372 2024-03-06T10:59:35Z ddc:004 open_access

A Fixed-Parameter Algorithm for the Schrijver Problem Haviv, Ishay Schrijver graph Kneser graph Fixed-parameter tractability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.16 urn:nbn:de:0030-drops-173721 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode