אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A well-known application of the celebrated color-coding technique is fast detection of paths in a distributed setting with limited bandwidth, by propagating a signal along colorful paths [Even et al., DISC 2017]. However, since vertices of the same color are indistinguishable by this procedure, it cannot detect induced paths, as they appear the same as cycles.

We present a distributed local-counting technique that allows us to design fast algorithms for detecting induced paths, improving upon the state of the art in several aspects (time complexity, detection variant, and more).

The following observation illustrates our key technical ingredient: For each edge, count the number of signals, over all permutations of the random coloring, that terminate at that edge. An induced path contributes one to that count, while a cycle contributes two. Refining and generalizing this idea lets us distinguish induced 4-paths from other 4-vertex subgraphs in constant time and yields fast algorithms for detecting paths of lengths 5 and 6.