Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?
Let the input graph be $G=(V,E)$ and let $k$ be the (maximum) size of the vertex cover of $G$ we are searching for. Proceed as follows:

If $E=\emptyset$ return the trivial empty solution.
Otherwise, if $k&gt;0$:

Pick an arbitrary edge $(u,v) \in E$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G - u$. If $S$ exists return $S \cup \{u \}$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G-v$. If $S$ exists return $S \cup \{v \}$.


Return &quot;no solution exists&quot;.

The time complexity of the above algorithm can be described by the following recurrence relation, where $n$ is the number of vertices of the input graph for your problem.
$$
T(k) \le 2T(k-1) + O(\mbox{poly}\, n) \quad \mbox{and} \quad T(0)=O(1).
$$
Therefore $T(k) = O( 2^k \cdot  \mbox{poly}\, n )$.
In your case $k=\lceil \log n \rceil$, therefore the overall time needed is $O( \mbox{poly}\, n )$.