Manuel Lafond
  • Member for 7 years
  • Last seen more than a month ago
Is $k$-CLIQUE W[1]-hard for parameter $n - k$?
4 votes

I believe this is FPT. FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the ...

View answer
Algorithm to place apples in boxes
Accepted answer
2 votes

Here is the reduction to a maximum matching, following the comments. We construct a graph $G$ with weighted edges as follows. The vertices of $G$ are $A$ and $B$. Each apple has a corresponding ...

View answer