Communication Complexity of Pairs of Graph Families with Applications

Authors Sudeshna Kolay, Fahad Panolan, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.13.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Sudeshna Kolay
Fahad Panolan
Saket Saurabh

Cite AsGet BibTex

Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. Communication Complexity of Pairs of Graph Families with Applications. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.13

Abstract

Given a graph G and a pair (\mathcal{F}_1,\mathcal{F}_2) of graph families, the function {\sf GDISJ}_{G,{\cal F}_1,{\cal F}_2} takes as input, two induced subgraphs G_1 and G_2 of G, such that G_1 \in \mathcal{F}_1 and G_2 \in \mathcal{F}_2 and returns 1 if V(G_1)\cap V(G_2)=\emptyset and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ_G,\cal F_1,\cal F_2. A concept related to communication protocols is that of a (\mathcal{F}_1,\mathcal{F}_2)-separating family of a graph G. A collection \mathcal{F} of subsets of V(G) is called a (\mathcal{F}_1,\mathcal{F}_2)-separating family} for G, if for any two vertex disjoint induced subgraphs G_1\in \mathcal{F}_1,G_2\in \mathcal{F}_2, there is a set F \in \mathcal{F} with V(G_1) \subseteq F and V(G_2) \cap F = \emptyset. Given a graph G on n vertices, for any pair (\mathcal{F}_1,\mathcal{F}_2) of hereditary graph families with sublinear communication complexity for GDISJ_G,\cal F_1,\cal F_2, we give an enumeration algorithm that finds a subexponential sized (\mathcal{F}_1,\mathcal{F}_2)-separating family. In fact, we give an enumeration algorithm that finds a 2^{o(k)}n^{\Oh(1)} sized (\mathcal{F}_1,\mathcal{F}_2)-separating family; where k denotes the size of a minimum sized set S of vertices such that V(G)\setminus S has a bipartition (V_1,V_2) with G[V_1] \in {\cal F}_1 and G[V_2]\in {\cal F}_2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms as well as exact and FPT algorithms for several problems.
Keywords
  • Communication Complexity
  • Separating Family
  • FPT algorithms

Metrics

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

References

  1. Kazuyuki Amano. Some improved bounds on communication complexity via new decomposition of cliques. Discrete Applied Mathematics, 166:249-254, 2014. URL: http://dx.doi.org/10.1016/j.dam.2013.09.015.
  2. Nicolas Bousquet, Aurélie Lagoutte, and Stéphan Thomassé. Clique versus independent set. Eur. J. Comb., 40:73-92, 2014. URL: http://dx.doi.org/10.1016/j.ejc.2014.02.003.
  3. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  4. Marek Cygan and Marcin Pilipczuk. Split vertex deletion meets vertex cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett., 113(5-6):179-182, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.01.001.
  5. R. Diestel. Graph Theory. Springer, Berlin, second ed., electronic edition, February 2000. Google Scholar
  6. Tomas Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. Complexity of graph partition problems. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC'99, pages 464-472, New York, NY, USA, 1999. ACM. URL: http://dx.doi.org/10.1145/301250.301373.
  7. Mika Göös. Lower bounds for clique vs. independent set. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1066-1076, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.69.
  8. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. Electronic Colloquium on Computational Complexity (ECCC), 22:169, 2015. URL: http://eccc.hpi-web.de/report/2015/169.
  9. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1077-1088, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.70.
  10. Vince Grolmusz and Gábor Tardos. A note on non-deterministic communication complexity with few witnesses. Theory Comput. Syst., 36(4):387-391, 2003. URL: http://dx.doi.org/10.1007/s00224-003-1158-7.
  11. Hao Huang and Benny Sudakov. A counterexample to the Alon-Saks-Seymour conjecture and related problems. Combinatorica, 32(2):205-219, 2012. URL: http://dx.doi.org/10.1007/s00493-012-2746-4.
  12. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  13. László Lovász. Communication complexity: a survey. Paths, flows, and VLSI-layout, pages 235-265, 1990. Google Scholar
  14. László Lovász. Stable sets and polynomials. Discrete Mathematics, 124(1-3):137-153, 1994. URL: http://dx.doi.org/10.1016/0012-365X(92)00057-X.
  15. Manami Shigeta and Kazuyuki Amano. Ordered biclique partitions and communication complexity problems. Discrete Applied Mathematics, 184:248-252, 2015. URL: http://dx.doi.org/10.1016/j.dam.2014.10.029.
  16. Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441-466, 1991. URL: http://dx.doi.org/10.1016/0022-0000(91)90024-Y.
  17. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC'79, pages 209-213, New York, NY, USA, 1979. ACM. URL: http://dx.doi.org/10.1145/800135.804414.
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