English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Counting the number of independent sets for a bipartite graph (#BIS) plays acrucial role in the study of approximate counting. It has been conjectured thatthere is no fully polynomial-time (randomized) approximation scheme(FPTAS/FPRAS) for #BIS, and it was proved that the problem for instances with amaximum degree of $6$ is already as hard as the general problem. In this paper,we obtain a surprising tractability result for a family of #BIS instances. Wedesign a very simple deterministic fully polynomial-time approximation scheme(FPTAS) for #BIS when the maximum degree for one side is no larger than $5$.There is no restriction for the degrees on the other side, which do not evenhave to be bounded by a constant. Previously, FPTAS was only known forinstances with a maximum degree of $5$ for both sides.

FPTAS for #BIS with Degree Bounds on One Side