Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a circle graph, and let I(G) be its independence complex. The size of the input is measured by the number of vertices of G. Polynomial-time homotopy-type conjecture. The homotopy type of I(G) can be found in polynomial time with…
Let G be a planar graph with maximum degree 4. Its linear arboricity rm la(G) is the minimum number of linear forests whose union is the edge set of G. Planar degree-four linear arboricity complexity conjecture. It is NP-complete to…
Let t∈N be a constant and let G be a graph. Write AC(G) for the acquaintance time of G. One-versus-t hardness conjecture. It is NP-hard to decide whether AC(G)=1 or AC(G)≥ t. This is proposed as a stronger hardness result than the paper's…
Let d,m,n∈N. The real symmetric spaces S^n(R), real rectangular spaces R^m× n, complex symmetric spaces S^n(C), and complex rectangular spaces C^m× n be equipped with the corresponding Grothendieck d-norms. NP-hardness conjecture. The…
A polyomino is a finite union of edge-connected unit squares in the plane. A set of queens is independent when no two queens attack each other, and it is maximal dominating when it dominates every square and no queen can be added while…
Assume that G and H are 2-connected and 2-edge connected graphs of genus at least two. Choose a base edge e that is not a series edge, and consider the lifting process that tests rigidity and, when rigidity is detected, reconstructs the…
For a finite set S and target k, let g_k(S) denote the first subset of S whose elements add up to k, when such a subset exists. The associated search procedure is a partial function because no such subset need exist, and it searches the…
A polyomino is a finite union of edge-connected unit squares in the plane. It is convex if every row and every column has at most one connected component. A set of queens is non-attacking when no two queens attack each other, and the…
Let G be a graph. A graph is balanceable if it admits a balanced signing, namely an assignment of signs to its edges such that every cycle has equally many positive and negative edges. Balanceability NP-completeness conjecture. The problem…
A DNF is a disjunction of conjunctive terms; its width is the maximum number of literals in a term, its size is its number of terms, and two Boolean functions are ε-close when Pr[f(x)≠ g(x)]≤ε under uniformly random x∈ 0,1 ^n. Improved…
Given an approval profile P and a target committee size k, determine whether there exists a polynomial-time algorithm that outputs a committee W of size k satisfying both justified representation and Pareto optimality for every such…
Let p≥ 3 and k≥ 1 be integers. For a digraph D, let sinv_k^≤ p(D) denote the optimization problem of making D k-arc-strong using inversions of size at most p. Bounded-size inversion approximation hardness conjecture. There exists ε>0 such…
A graph is a generic-radii sphere-packing contact graph if it is the contact graph of a sphere packing whose radii are generic. NP-hardness conjecture. Determining whether a graph is a generic-radii sphere-packing contact graph is NP-hard.…
Given a digraph D=(V,A), determine whether there is a partition A=A_1mathbindot∪A_2 such that one of the following holds: (i) D[A_1] is a perfect matching and D[A_2] has no odd directed cycle; (ii) D[A_1] is a perfect matching and D[A_2]…
A regular oriented matroid is an oriented matroid whose underlying matroid is regular. For integers m,n≥ 2 with m+n odd, let vecK_m,n denote the complete bipartite graph with its natural orientation, let M^*(vecK_m,n) be its cographic…
Let n be the dimension and d the degree. Consider a system of n degree-d Chebyshev polynomials in n variables, and suppose that d is sufficiently large. Second-step complexity conjecture. The cost of subdivision is greatest on the second…
Let G be a finite solvable group. An n-input G-program is a sequence of group elements selected according to the values of input bits, and it computes the n-input AND function when membership in some subset of G agrees with the function's…
Let a lattice be a discrete subgroup of Euclidean space, and let its shortest nonzero integer vector length be the relevant lattice parameter. Lattice shortest-vector hardness conjecture. Proving that a lattice's shortest integer vector…
Let T be a tree of maximum degree Δ. For d≥Δ, let overlineT_d be a d-regular graph obtained from T by adding semi-edges or loops so that every vertex of overlineT_d has degree d; this graph is not uniquely determined. Regular-tree…
Let N be a closed hyperbolic 3-manifold. A finite-sheeted Haken covering of N is a finite-sheeted covering space of N that is Haken. Effective virtual Haken conjecture. Every closed hyperbolic manifold N has a finite-sheeted Haken…