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/

Zendy Plus

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

Zendy Tools

Zendy Open

In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, weask whether the edges of G can be covered with k complete subgraphs of G or,equivalently, whether G admits an intersection model on k-element universe.Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the numberof vertices of G to 2^k, and no algorithm is known with significantly betterrunning time bound than a brute-force search on this reduced instance. In thispaper we show that the approach of Gramm et al. is essentially optimal: wepresent a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formulawith n variables and m clauses to an equivalent ECC instance (G,k) with k =O(log n) and |V(G)| = O(n + m). Consequently, there is no 2^{2^{o(k)}}poly(n)time algorithm for the ECC problem, unless the Exponential Time Hypothesisfails. To the best of our knowledge, these are the first results for a natural,fixed-parameter tractable problem, and proving that a doubly-exponentialdependency on the parameter is essentially necessary.

Known algorithms for EDGE CLIQUE COVER are probably optimal