5 problems

Hypermetric integrality-gap conjecture. The integrality gap is still $2-o(1)$ when we impose the condition that the solution is a Hypermetric.

For a graph $G=(V,E)$, let $\tau(G)$ be the minimum size of a vertex set meeting every edge, and call $G$ $\tau$-critical when $\tau(G)>\tau(G-e)$ for every $e\in E$. Define … If a…

Let $G=(V,E)$ be the graph in an instance of M-EPVCB, and let $\Delta(G)$ denote its maximum degree. The degree-deficit hardness conjecture. M-EPVCB is W[1]-hard with respect to th…

Let $G=(X,Y,E)$ be the edge-weighted bipartite graph in an instance of M-EPVCB, and let $|X|$ and $|Y|$ denote the sizes of its two bipartition classes. The minimum-side hardness c…

Minimum oriented diameter conjecture.