Access the full text.
Sign up today, get DeepDyve free for 14 days.
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.
ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery
Published: Mar 15, 2019
Keywords: Communication complexity
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.