Known algorithms for EDGE CLIQUE COVER are probably optimal

Details Known algorithms for EDGE CLIQUE COVER are probably optimal Known algorithms for EDGE CLIQUE COVER are probably optimal

2012-03-08

arxiv.org/abs/1203.1754v1

Computer Science

Data Structures and Algorithms

Scientific paper

In the EDGE CLIQUE COVER problem, given a graph G and an integer k, we ask 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] shown a set of simple rules that reduce the number of vertices of G to 2^k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent EDGE CLIQUE COVER instance (G,k) with k = O(log n) and |V(G)| = O(n + m).

Affiliated with

Also associated with

No associations

Rating

Known algorithms for EDGE CLIQUE COVER are probably optimal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Known algorithms for EDGE CLIQUE COVER are probably optimal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Known algorithms for EDGE CLIQUE COVER are probably optimal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17154