Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Communication Complexity and Graph Families

Communication Complexity and Graph Families Given a graph G and a pair (F1, F2) of graph families, the function GDISJG,F1,F2 takes as input, two induced subgraphs G1 and G2 of G, such that G1 F1 and G2 F2 and returns 1 if V(G1) V(G2)= 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 GDISJG, F1, F2. A concept related to communication protocols is that of a (F1, F2)-separating family of a graph G. A collection F of subsets of V(G) is called a (F1,F2)-separating family for G, if for any two vertex disjoint induced subgraphs G1 F1,G2 F2, there is a set F F with V(G1) F and V(G2) F = . Given a graph G on n vertices, for any pair (F1,F2) of hereditary graph families with sublinear communication complexity for GDISJG,F1,F2, we give an enumeration algorithm that finds a subexponential sized (F1,F2)-separating family. In fact, we give an enumeration algorithm that finds a 2o(k)nO(1) sized (F1,F2)-separating family, where k denotes the size of a minimum sized set S of vertices such that V(G) S has a bipartition (V1,V2) with G[V1] F1 and G[V2] F2. 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Communication Complexity and Graph Families

Download PDF
28 pages

Loading next page...
 
/lp/association-for-computing-machinery/communication-complexity-and-graph-families-WviHbOAaoW
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3313234
Publisher site
See Article on Publisher Site

Abstract

Given a graph G and a pair (F1, F2) of graph families, the function GDISJG,F1,F2 takes as input, two induced subgraphs G1 and G2 of G, such that G1 F1 and G2 F2 and returns 1 if V(G1) V(G2)= 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 GDISJG, F1, F2. A concept related to communication protocols is that of a (F1, F2)-separating family of a graph G. A collection F of subsets of V(G) is called a (F1,F2)-separating family for G, if for any two vertex disjoint induced subgraphs G1 F1,G2 F2, there is a set F F with V(G1) F and V(G2) F = . Given a graph G on n vertices, for any pair (F1,F2) of hereditary graph families with sublinear communication complexity for GDISJG,F1,F2, we give an enumeration algorithm that finds a subexponential sized (F1,F2)-separating family. In fact, we give an enumeration algorithm that finds a 2o(k)nO(1) sized (F1,F2)-separating family, where k denotes the size of a minimum sized set S of vertices such that V(G) S has a bipartition (V1,V2) with G[V1] F1 and G[V2] F2. 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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Mar 15, 2019

Keywords: Communication complexity

References

  • Some improved bounds on communication complexity via new decomposition of cliques
    Amano, Kazuyuki
  • Parameterized complexity dichotomy for (r, l)-vertex deletion
    Baste, Julien; Faria, Luerbio; Klein, Sulamita; Sau, Ignasi
  • Clique versus independent set
    Bousquet, Nicolas; Lagoutte, Aurélie; Thomassé, Stéphan
  • Exact algorithms for graph colouring and exact satisfiability
    Byskov, J. M.
  • Improved upper bounds for vertex cover
    Chen, Jianer; Kanj, Iyad A.; Xia, Ge
  • Parameterized Algorithms
    Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
  • Split vertex deletion meets vertex cover: New fixed-parameter and exact exponential-time algorithms
    Cygan, Marek; Pilipczuk, Marcin
  • Graph Theory (2nd ed
    Diestel, R.
  • Complexity of graph partition problems
    Feder, Tomas; Hell, Pavol; Klein, Sulamita; Motwani, Rajeev
  • On the minimum feedback vertex set problem: Exact and enumeration algorithms
    Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem V.; Razgon, Igor
  • Planar F-deletion: Approximation, kernelization and optimal FPT algorithms
    Fomin, Fedor V.; Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket
  • Lower bounds for clique vs
    Göös, Mika
  • Randomized communication versus partition number
    Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
  • Deterministic communication vs
    Göös, Mika; Pitassi, Toniann; Watson, Thomas
  • A note on non-deterministic communication complexity with few witnesses
    Grolmusz, Vince; Tardos, Gábor
  • Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds
    Gupta, Sushmita; Raman, Venkatesh; Saurabh, Saket
  • A counterexample to the Alon-Saks-Seymour conjecture and related problems
    Huang, Hao; Sudakov, Benny
  • A near-optimal planarization algorithm
    Jansen, Bart M. P.; Lokshtanov, Daniel; Saurabh, Saket
  • Faster deterministic feedback vertex set
    Kociumaka, Tomasz; Pilipczuk, Marcin
  • Parameterized algorithms for deletion to (r,l)-graphs
    Kolay, Sudeshna; Panolan, Fahad
  • Communication complexity of pairs of graph families with applications
    Kolay, Sudeshna; Panolan, Fahad; Saurabh, Saket
  • Communication Complexity
    Kushilevitz, Eyal; Nisan, Noam
  • Faster parameterized algorithms using linear programming
    Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket
  • Communication complexity: A survey
    Lovász, László
  • Stable sets and polynomials
    Lovász, László
  • On cliques in graphs
    Moon, J. W.; Moser, L.
  • An efficient fixed-parameter algorithm for 3-hitting set
    Niedermeier, Rolf; Rossmanith, Peter
  • Finding a maximum induced degenerate subgraph faster than 2 n
    Pilipczuk, Marcin; Pilipczuk, Michal
  • Ordered biclique partitions and communication complexity problems
    Shigeta, Manami; Amano, Kazuyuki
  • Expressing combinatorial optimization problems by linear programs
    Yannakakis, Mihalis
  • Some complexity questions related to distributive computing (preliminary report)
    Yao, Andrew Chi-Chih