Broadcasting Time Cannot be Approximated Within a Factor of 57/56-epsilon

TitleBroadcasting Time Cannot be Approximated Within a Factor of 57/56-epsilon
Publication TypeTechnical Report
Year of Publication2000
AuthorsSchindelhauer, C.
Other Numbers1177
Abstract

In the beginning the information is available only at some sources of a given network. The aim is to inform all nodes of the given network. Therefore, every node can inform its neighborhood sequentially and newly informed nodes can proceed in parallel within their neighborhoods. The process of informing one node needs one time unit. The broadcasting problem is to compute the minimum length of such a broadcasting schedule.The computational complexity of broadcasting is investigated and for the first time a constant lower inapproximability bound is stated, i.e. it is NP-hard to distinguish between graphs with broadcasting time smaller than b and larger than (57/56-?)b for any ?>0. This improves on the lower bounds known for multiple and single source broadcasting, which could only state that it is NP-hard to distinguish between graphs with broadcasting time b and b+1, for any b >= 3. This statement is proven by reduction from E3-SAT, the analysis of which needs a carefully designed book-keeping and counting argument.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/2000/tr-00-002.pdf
Bibliographic Notes

ICSI Technical Report TR-00-002

Abbreviated Authors

C. Schindelhauer

ICSI Publication Type

Technical Report