Antti Röyskö
• Member for 2 years, 3 months
• Last seen more than 1 year ago
• Helsinki, Finland

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the ...

The problem is NP-complete. We'll make a series of reductions from max-cut to show this. Problem 0 (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such ...

We can show there's an upper bound based only on B. Fix B, then i and j. Let the tuple $(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k}$ denote the packing where we have $x_{t}$ bins of type $t$, ...

The problem is strongly NP-complete. Reduction from 3-partition, a strongly NP-complete problem. The multiset $S$, $|S| = 3m$, $\sum_{x \in S} x = n$ can be partitioned into tuples of size three of ...

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$. Here are constructions for $n = 8$ and $n = 14$. These generalise to ...

Consider the function $f(x, y) = 1 - e^{-(x + y)}$. Now $f(0, 0) = 0$, $f$ is increasing and concave, since $g(t) = -e^{-t}$ is concave. But \$f(1, 0) + f(0, 1) = 2(1 - e^{-1}) > 1 - e^{-2} = f(1, ...