polynomial algorithm

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

\begin{conjecture} It has been shown that a $k$-outerplanar embedding for which $k$ is minimal can be found in polynomial time. Does a similar result hold for $k$-edge-outerplanar graphs? \end{conjecture}

Keywords: planar graph; polynomial algorithm

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

\begin{conjecture} Is the approximation ratio for the \emph{Maximum Edge Disjoint Paths} (MaxEDP) or the \emph{Maximum Integer Multiflow} problem (MaxIMF) bounded by a constant in $k$-outerplanar graphs or tree-width graphs? \end{conjecture}

Keywords: approximation algorithms; planar graph; polynomial algorithm

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

\begin{conjecture} Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $\mathcal{APX}$-hardness? \end{conjecture}

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

P vs. NP ★★★★

Author(s): Cook; Levin

\begin{problem} Is P = NP? \end{problem}

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

Subset-sums equality (pigeonhole version) ★★★


\begin{problem} Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist distinct subsets $I,J \subseteq \{1,\ldots,n\}$ with $\sum_{i \in I} a_i = \sum_{j \in J} a_j$. Is it possible to find such a pair $I,J$ in polynomial time? \end{problem}

Keywords: polynomial algorithm; search problem

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

\begin{problem} Does there exist a \Def{polynomial time} algorithm which takes as input a graph $G$ and for every vertex $v \in V(G)$ a subset $\ell(v)$ of $\{1,2,3,4\}$, and decides if there exists a partition of $V(G)$ into $\{A_1,A_2,A_3,A_4\}$ so that $v \in A_i$ only if $i \in \ell(v)$ and so that $A_1,A_2$ are independent, $A_4$ is a clique, and there are no edges between $A_1$ and $A_3$? \end{problem}

Keywords: list partition; polynomial algorithm

Syndicate content