Antti Röyskö
  • Member for 2 years, 3 months
  • Last seen more than 1 year ago
  • Helsinki, Finland
Relationship between two graph optimization problems
Accepted answer
17 votes

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 ...

View answer
Complexity of finding the largest induced subgraph with all even degrees
Accepted answer
5 votes

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 ...

View answer
Re-packing of integers into fixed-size bins
Accepted answer
5 votes

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$, ...

View answer
Meet of integer partitions
Accepted answer
4 votes

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 ...

View answer
Existence of graphs of every order related to Barnette’s conjecture
Accepted answer
2 votes

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 ...

View answer
What Is the Complexity of This Two-to-One Matching Problem?
Accepted answer
2 votes

EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity. The following is a reduction of minimum vertex cover to your problem. ...

View answer
Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$
1 votes

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, ...

View answer