31.12.2013 Dr. H. A. HELFGOTT proved the weak Goldbach conjecture.
http://arxiv.org/pdf/1312.7748.pdf
Open Problems on Scheduling 2010
**************************************************
Exact Even Set
Input: A set syetem $F$ over a universal saet $U$, and an integer $k$.
Question: Is there a subset $S$ of $U$ such that $|S|=k$ and $|S\cap A|$ is even for every $A\subseteq F$?
Exact Even Set is W[1]-hard.
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput. 24(4), 873–921 (1995).
Even Set is defined the same as Exact Even Set with the difference that $S$ is required to have at most $k$ element instead of exactly $k$ element.
Open question: Is Even Set W[1]-hard or FPT?
Minimum Bisection Problem
Input: A graph $G=(V, E)$ and an integer $k$.
Question: Is there a partition $(V_1, V_2$ of $V$ such that $||V_1|-|V_2||\leq 1$ and $|E(V_1, V_2)|\leq k$?
In the definition, $E(V_1, V_2)$ is the set of edges between $V_1$ and $V_2$ in $G$.
Minimum Bisection problem is NP-hard in general graphs [2] but FPT with respect to $k$ [2].
It is also proved that the Bisection problem remains NP-hard in several special graph classes such as unit disk graphs [3].
[1] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co., 1979.
[2] M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Mini- mum bisection is fixed parameter tractable. STOC 2014.
[3] Josep Dıaz and G> B. Mertzios. Minimum Bisection is NP-hard on Unit Disk Graphs, CORR 2017.
Open Question: Is the Minimum Bisection problem NP-hard in planar graphs?
A vertex $v$ dominates another vertex $u$ if $N(u)\subseteq N[v]$.
A domination graph $G$ is a graph such that in every induced subgraph of size at least two, there are two vertices $v$ and $u$ with $v$ dominating $u$.
Domination Graph Recognition (DGR)
Input: A graph $G$.
Question: Is $G$ a domination graph?
Open Question: Is DGR NP-hard or polynomial-time solvable?
Exact Matching
Input: A graph $G=(V, E)$, a subset $E'\subseteq E$ and a postive integer $k$.
Question: Is there a perfect matching which includes exactly $k$ edges from $E'$?
The problem was proposed in [1]. An RNC algorithm is known [2].
[1] CHRISTOS H. PAPADIMITRIOU, MIHALIS YANNAKAKIS. The Complexity of Restricted Spanning Tree Problems, JACM 1982.
[2] Mulmuley, K., Vazirani, U.V., Vazirani, V.V Matching is as Easy as Matrix Inversion. Combinatorica 7(1), 105–113, 1987.
Open Question: Is Exact Matching solvable in polynomial-time?
Blue-Red Matching
Input: A graph $G=(V, E)$ with edges being colored with blue or red, a postive integer $k$.
Question: Find a maximum matching which includes at most $k$ red edges and $k$ blue edges.
The problem was proposed in [1].
[1] Christos Nomikos, Aris Pagourtzis, and Stathis Zachos. Randomized and Approximation Algorithms for Blue-Red Matching.
Open Question: Is Blue-Red Matching solvable in polynomial-time?
Recognition of Odd-Hole-Free Graph
Input: A graph $G$.
Question: Is there an odd hole in $G$?
A hole is an induced cycle of length at least 4.
Recognition of even-hole-free graphs is polynomial-time solvable. However, the complexity of recognition of odd-hole-free graph has been open to date.
Open Question: Is Recognition of Odd-Hole-Free Graph solvable in polynomial-time?
Open Question: What is the parameterized complexity of Independent Set in C_4-free graphs?
reference: https://community.dur.ac.uk/konrad.dabrowski/fpt-iwoca-final.pdf
For a graph $G$, let $FVS(G)$ be the size of the minimum feedback vertex set of $G$, and $PAC(G)$ the size of the maximum number of vertex-disjoint cycles in $G$.
The following conjecture is due to Kloks et al. [1].
Conjecture: For every planar graph $G$, $FVS(G)\leq 2 PAC(G)$
The conjecture has been proved for some special cases. However ,whether the conjecture holds in general remains open.
[1] Kloks, Lee, Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs. 2002