Document Open Access Logo

The Complexity of Finding Fair Independent Sets in Cycles

Author Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.4.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

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

Acknowledgements

We are grateful to Aris Filos-Ratsikas and Alexander Golovnev for helpful discussions.

Cite AsGet BibTex

Ishay Haviv. The Complexity of Finding Fair Independent Sets in Cycles. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.4

Abstract

Let G be a cycle graph and let V₁,…,V_m be a partition of its vertex set into m sets. An independent set S of G is said to fairly represent the partition if |S ∩ V_i| ≥ 1/2⋅|V_i| - 1 for all i ∈ [m]. It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al., A Journey through Discrete Math., 2017). We prove that the problem of finding such an independent set is PPA-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is PPA-complete as well. The work is motivated by the computational aspects of the "cycle plus triangles" problem and of its extensions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Graph theory
Keywords
  • Fair independent sets in cycles
  • the complexity class {PPA}
  • Schrijver graphs

Metrics

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

Related Versions

References

  1. Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, and Ran Ziv. Fair representation by independent sets. In M. Loebl, J. Nešetřil, and R. Thomas, editors, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 31-58. Springer, 2017. Google Scholar
  2. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. J. Comput. Syst. Sci., 108:92-103, 2020. Google Scholar
  3. Meysam Alishahi and Frédéric Meunier. Fair splitting of colored paths. Electron. J. Comb., 24(3):P3.41, 2017. Google Scholar
  4. Noga Alon. Combinatorial Nullstellensatz. Combinatorics, Probability and Computing, 8(1-2):7–-29, 1999. Google Scholar
  5. Noga Alon. Discrete mathematics: methods and challenges. In Proc. of the International Congress of Mathematicians (ICM'02), pages 119-135. Higher Education Press, 2002. Google Scholar
  6. Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125-134, 1992. Google Scholar
  7. Noga Alon and Douglas B. West. The Borsuk-Ulam theorem and bisection of necklaces. Proc. Amer. Math. Soc., 98(4):623-628, 1986. Google Scholar
  8. Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. On the polynomial parity argument complexity of the combinatorial nullstellensatz. In 32nd Computational Complexity Conference (CCC'17), pages 30:1-30:24, 2017. Google Scholar
  9. Kristóf Bérczi and Yusuke Kobayashi. An algorithm for identifying cycle-plus-triangles graphs. Discret. Appl. Math., 226:10-16, 2017. Google Scholar
  10. Alexander Black, Umur Cetin, Florian Frick, Alexander Pacun, and Linus Setiabrata. Fair splittings by independent sets in sparse graphs. Israel J. of Math., 236:603–-627, 2020. Google Scholar
  11. Karol Borsuk. Drei Sätze über die n-dimensionale euklidische sphäre. Fundamenta Mathematicae, 20(1):177-190, 1933. Google Scholar
  12. Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci., 410(44):4448-4456, 2009. Preliminary version in ICALP'06. Google Scholar
  13. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1-14:57, 2009. Preliminary version in FOCS'06. Google Scholar
  14. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. Preliminary version in STOC'06. Google Scholar
  15. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11), pages 790-804, 2011. Google Scholar
  16. Jesús A. De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil H. Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bull. Amer. Math. Soc., 56(3):415-511, 2019. Google Scholar
  17. Xiaotie Deng, Zhe Feng, and Rucha Kulkarni. Octahedral Tucker is PPA-complete. Electronic Colloquium on Computational Complexity (ECCC), 24:118, 2017. Google Scholar
  18. Xiaotie Deng, Qi Qi, and Amin Saberi. Algorithmic solutions for envy-free cake cutting. Oper. Res., 60(6):1461-1476, 2012. Google Scholar
  19. D. Z. Du, D. F. Hsu, and F. K. Hwang. The Hamiltonian property of consecutive-d digraphs. Math. and Computer Modelling, 17(11):61-63, 1993. Google Scholar
  20. Paul Erdös. On some of my favourite problems in graph theory and block designs. Matematiche, 45(1):61-73, 1990. Google Scholar
  21. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP'19), pages 56:1-56:15, 2019. Google Scholar
  22. Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness results for consensus-halving. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS'18), pages 24:1-24:16, 2018. Google Scholar
  23. 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
  24. 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
  25. Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. Consensus-halving: Does it ever get easier? In 21st ACM Conference on Economics and Computation (EC'20), pages 381-399, 2020. Google Scholar
  26. Herbert Fleischner and Michael Stiebitz. A solution to a colouring problem of P. Erdös. Discret. Math., 101(1-3):39-48, 1992. Google Scholar
  27. Herbert Fleischner and Michael Stiebitz. Some remarks on the cycle plus triangles problem. In The Mathematics of Paul Erdös II, volume 14, pages 136-142. Springer, 1997. Google Scholar
  28. Charles H. Goldberg and Douglas B. West. Bisection of circle colorings. SIAM J. Alg. Disc. Meth., 6(1):93-106, 1985. Google Scholar
  29. Paul W. Goldberg and Alexandros Hollender. The hairy ball problem is PPAD-complete. In 46th International Colloquium on Automata, Languages, and Programming (ICALP'19), pages 65:1-65:14, 2019. Google Scholar
  30. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. Preliminary version in FOCS'85. Google Scholar
  31. Martin Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2):27, 1955. Google Scholar
  32. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A, 25(3):319-324, 1978. Google Scholar
  33. Jiří Matoušek. A combinatorial proof of Kneser’s conjecture. Combinatorica, 24(1):163-170, 2004. Google Scholar
  34. Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer Publishing Company, Incorporated, 2007. Google Scholar
  35. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theor. Comput. Sci., 81(2):317-324, 1991. Google Scholar
  36. Frédéric Meunier. The chromatic number of almost stable Kneser hypergraphs. J. Comb. Theory, Ser. A, 118(6):1820-1828, 2011. Google Scholar
  37. Dömötör Pálvölgyi. 2D-Tucker is PPAD-complete. In 5th International Workshop on Internet and Network Economics (WINE'09), pages 569-574, 2009. Google Scholar
  38. 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
  39. Horst Sachs. Elementary proof of the cycle-plus-triangles theorem. In Combinatorics, Paul Erdős is eighty, volume 1, pages 347-359. Bolyai Soc. Math. Stud., 1993. Google Scholar
  40. Alexander Schrijver. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wiskd., 26(3):454-461, 1978. Google Scholar
  41. 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
  42. Günter M. Ziegler. Generalized Kneser coloring theorems with combinatorial proofs. Invent. math., 147(3):671-691, 2002. 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 Imprint Privacy Contact