Question 4.4 in Homework
1 view
Skip to first unread message
Indigon
Jun 22, 2010, 12:23:36 PM6/22/10
to Computational Complexity, Spring 2010
Can anyone supply the solution for this question? I'm having trouble
using k-wise here.
"Let n be an integer and let K = ( n 20 ) / 2^190 . Provide a
deterministic polynomial time algorithm that given a number n (in
unary representation) finds an undirected graph on n vertices with no
more than K cliques of size 20 and no more than K independent sets of
size 20 if such a graph exists."
using k-wise here.
"Let n be an integer and let K = ( n 20 ) / 2^190 . Provide a
deterministic polynomial time algorithm that given a number n (in
unary representation) finds an undirected graph on n vertices with no
more than K cliques of size 20 and no more than K independent sets of
size 20 if such a graph exists."
Anat
Jun 23, 2010, 11:23:00 AM6/23/10
to Computational Complexity, Spring 2010
Bump? anyone?
Reply all
Reply to author
Forward
0 new messages