---
id: major-open-problems
title: Open problems I care about
description: A living list of open problems.
numbering: global
blocks:
  problem:
    counter: problem
---

# Open problems I care about

A living list of open problems I care about. Intermediate lemmas, proof routes, and narrower subproblems belong in their project notes, not here. Project links are omitted for now.

## Graphs and directed cuts

::: {.problem #problem-ocdc title="Oriented cycle double cover"}
For every finite undirected multigraph $G$ with no bridge (an edge whose deletion increases the number of connected components), does there exist a multiset of connected 2-regular subgraphs of $G$, each given a cyclic orientation, such that every edge of $G$ is traversed exactly once in each direction? A pair of parallel edges may form a 2-cycle, but traversing one edge forward and immediately backward is not a cycle.
:::

::: {.problem #problem-global-dicut title="Global dicut complexity"}
Given a finite digraph $G=(V,E)$ with nonnegative arc weights $w$, let $\delta^+(S)=\{uv\in E:u\in S,\ v\notin S\}$. Minimize $\sum_{e\in\delta^+(X)\cup\delta^+(Y)}w(e)$ over sets $X,Y\subseteq V$ satisfying $X\setminus Y\ne\varnothing$ and $Y\setminus X\ne\varnothing$, with each arc in the union counted only once; does this optimization problem have a polynomial-time algorithm, or is it NP-hard?
:::

::: {.problem #problem-global-linear-3-cut title="Global linear 3-cut"}
Given a finite directed graph $G=(V,E)$, find a minimum-cardinality set $F\subseteq E$ of arcs such that $G-F$ has at least three strongly connected components, where a strongly connected component is a maximal vertex set in which every vertex can reach every other by a directed path; does this problem have a polynomial-time algorithm, or is it NP-hard?
:::

::: {.problem #problem-red-blue-cut title="Red-blue cut in digraphs"}
Given a finite digraph $G=(V,E)$ whose arcs are each colored red or blue, and nonnegative integers $r$ and $b$, decide whether there is a set $\emptyset\subsetneq S\subsetneq V$ such that the set of arcs leaving $S$ contains at most $r$ red arcs and at most $b$ blue arcs; is this decision problem solvable in polynomial time, or is it NP-hard? The undirected analogue is solvable in polynomial time even with weights. The fixed-terminal variant requiring $s\in S$ and $t\notin S$ is NP-complete in digraphs, polynomial in planar digraphs, NP-complete in undirected graphs with weights, and open in unweighted undirected graphs.
:::

::: {.problem #problem-rooted-connectivity-certificate title="Fast rooted connectivity certificates in digraphs"}
Let $G=(V,E)$ be a finite digraph with $n$ vertices, $m$ arcs, and a root $r\in V$, and let $\lambda(r,x,G)$ be the maximum number of arc-disjoint paths from $r$ to $x$. For an integer $k\ge1$, an $r$-rooted $k$-certificate is a subgraph $H$ of $G$ with $O(kn)$ arcs satisfying $\lambda(r,x,H)\ge\min(\lambda(r,x,G),k)$ for every $x\in V$. Such a subgraph always exists with at most $k(n-1)$ arcs: there are $k$ arc-disjoint branchings rooted at $r$ such that every vertex $x$ lies in $\min(\lambda(r,x,G),k)$ of them, and their union qualifies. Can an $r$-rooted $k$-certificate be computed in $O(km)$ time, or even $O(m)$ time? In undirected graphs a subgraph with at most $kn$ edges preserving every pairwise local edge connectivity up to $k$ can be found in $O(m)$ time by maximal spanning forest decomposition. In the rooted directed setting the fastest known exact constructions go through arborescence packings: when $\lambda(r,x,G)\ge k$ for every $x$, the packing takes $O(km\log n+nk^4\log^2n)$ time, which reaches $O(km)$ up to logarithmic factors only for $m$ above roughly $nk^3$; in the general nonuniform case only unspecialized polynomial bounds are known, and the known almost-linear-time algorithms are approximate.
:::

::: {.problem #problem-hedge-min-cut-derandomization title="Deterministic hedge min-cut with small hedges"}
Fix an integer $k\ge2$. Given a finite undirected multigraph $G=(V,E)$ together with a partition of $E$ into groups called hedges, each containing at most $k$ edges, find the minimum number of hedges whose removal disconnects $G$; is there a deterministic polynomial-time algorithm? A randomized polynomial-time algorithm is known for every fixed $k$ — indeed whenever every hedge induces a subgraph with at most $k$ connected components — via random contraction. The case $k=1$ is global min-cut, and the case where every hedge induces a connected subgraph is hypergraph min-cut; both are solvable deterministically in polynomial time. Without any bound on the hedges, the problem admits a randomized quasi-polynomial-time algorithm and has no polynomial-time algorithm under the exponential time hypothesis.
:::

## Cut counting

::: {.problem #problem-pareto-cut-count title="Pareto-optimal cut counting"}
Fix an integer $t\ge2$. Let $G=(V,E)$ be a finite undirected multigraph on $n$ vertices with $t$ cost functions $c_1,\ldots,c_t:E\to\mathbb R_{\ge0}$. A cut is an edge set of the form $E(P)$, the edges joining distinct classes of a partition $P$ of $V$ into at least two nonempty classes. A cut $F$ is pareto-optimal if no cut $F'$ satisfies $c_i(F')\le c_i(F)$ for all $i$ with strict inequality for some $i$. The number of pareto-optimal cuts is $O(n^{3t-1})$ and can be $\Omega(n^t)$; determine the correct exponent. In particular, for $t=2$, is the number of pareto-optimal cuts $O(n^2)$? A natural first step is to bound, for a fixed budget vector $b\in\mathbb R_{\ge0}^{t-1}$, the number of cuts minimizing $c_t$ subject to $c_i(F)\le b_i$ for all $i<t$.
:::

::: {.problem #problem-strict-approximate-min-cut-count title="Counting strictly small cuts"}
Fix a real $\alpha\ge1$. Let $G=(V,E)$ be a finite undirected multigraph on $n$ vertices with positive edge costs $c$, let a cut be an edge set of the form $E(P)$ as above, and let $\lambda$ be the minimum cost of a cut. Is the number of cuts $F$ with $c(F)<\alpha\lambda$ at most $O(n^{\lceil2\alpha\rceil-1})$? The bound is known for $\alpha\le3/2$. For the non-strict inequality $c(F)\le\alpha\lambda$ the count is $O(n^{\lfloor2\alpha\rfloor})$ with a constant depending on $\alpha$, and the cycle shows $\binom{n}{\lfloor2\alpha\rfloor}$ is attainable, so the conjecture is equivalent to a matching non-strict upper bound whose constant does not depend on $\alpha$.
:::

::: {.problem #problem-approximate-k-cut-count title="Floor in the approximate k-cut count"}
Fix an integer $k\ge2$ and a real $\alpha\ge1$. Let $G=(V,E)$ be a finite undirected multigraph on $n$ vertices with positive edge costs $c$, and let $\lambda_k$ be the minimum cost of an edge set of the form $E(P)$ over partitions $P$ of $V$ into at least $k$ nonempty classes. Is the number of edge sets $E(P)$, over partitions $P$ into at least two nonempty classes, of cost at most $\alpha\lambda_k$ bounded by $O(n^{\lfloor\alpha k\rfloor})$? The known upper bound is $n^{\alpha k}k^{O(\alpha k^2)}$, the cycle gives a lower bound of $\Omega(n^{\lfloor\alpha k\rfloor})$, and the case $\alpha=1$ is settled at $\Theta(n^k)$.
:::

::: {.problem #problem-hypergraph-k-cut-set-count title="Hypergraph minimum k-cut-sets"}
Fix an integer $k\ge2$. Let $H=(V,E)$ be a finite hypergraph on $n$ vertices with positive hyperedge costs. For a partition $P$ of $V$ into at least $k$ nonempty classes, its cut-set is the set of hyperedges not contained in any single class, and $\lambda_k$ is the minimum cost of such a cut-set. The number of distinct minimum-cost $k$-cut-sets is $O(n^{2(k-1)})$, while for graphs it is $\Theta(n^k)$. Is the number of minimum $k$-cut-sets in a hypergraph $O(n^k)$ for every fixed $k$? Counting $\alpha$-approximate cut-sets for $\alpha>1$ is provably hopeless at unbounded rank, so the exact count is the right question.
:::

## Routing and traveling salesman

::: {.problem #problem-tsp-bounded-fvs title="TSP with bounded feedback vertex set"}
For every fixed integer $k\ge2$: given a finite digraph $G=(V,E)$ with binary-encoded nonnegative integer arc weights $w$, a vertex $r\in V$, and a set $F\subseteq V$ with $|F|\le k$ such that the subgraph induced by $V\setminus F$ has no directed cycle, find a closed walk that starts and ends at $r$, visits every vertex of $V$ at least once, and minimizes the total weight of its arcs counted with multiplicity; is this optimization problem solvable in polynomial time? A shortest such walk uses each arc at most $|V|$ times, so the decision version is in NP, and feasibility is a reachability check. The case $k=1$ reduces to minimum-cost flow; the case $k=2$ is open. Equivalently: the tour decomposes into walks in the acyclic part whose endpoints attach to $F$, and everything except the connectivity of the resulting $k$-vertex endpoint-pairing multigraph is an integral flow problem.
:::

::: {.problem #problem-tsp-bounded-directed-treewidth title="TSP with bounded directed treewidth"}
A set $S\subseteq V$ is guarded by $Z\subseteq V$ if every directed walk of $G$ that starts and ends in $S$ and avoids $Z$ stays inside $S$. An arboreal decomposition of a finite digraph $G=(V,E)$ is a rooted tree $R$ with edges directed away from the root, a partition $(W_t)_{t\in V(R)}$ of $V$, and a set $X_e\subseteq V$ for each edge $e$ of $R$, such that for every edge $e=(s,t)$ of $R$ the union of the sets $W_{t'}$ over nodes $t'$ in the subtree rooted at $t$ is guarded by $X_e$; its width is $\max_t\,\lvert W_t\cup\bigcup_{e\sim t}X_e\rvert-1$ over nodes $t$ and their incident edges, and the directed treewidth of $G$ is the minimum width of an arboreal decomposition. For every fixed integer $w$: given a finite digraph $G$ with binary-encoded nonnegative integer arc weights, an arboreal decomposition of $G$ of width at most $w$, and a vertex $r$, find a closed walk from $r$ visiting every vertex at least once and minimizing total arc weight counted with multiplicity; is this solvable in polynomial time? Deleting a feedback vertex set of size $k$ leaves an acyclic digraph, which has directed treewidth $0$, so directed treewidth is at most $k$ there and this question generalizes the bounded-feedback-vertex-set one. Hamiltonian cycle is polynomial-time solvable for every fixed directed treewidth (Johnson–Robertson–Seymour–Thomas), but that dynamic program does not obviously extend to walks with repeated visits.
:::

::: {.problem #problem-ttp2-complexity title="Traveling tournament with tour length two"}
Given an even integer $n\ge4$ and symmetric nonnegative distances $d(i,j)$ satisfying the triangle inequality between the home venues of $n$ teams, a double round-robin schedule consists of $2(n-1)$ ordered rounds in which every team plays exactly one game per round and every unordered pair of teams meets exactly twice, once hosted by each of the two. A team is located at its own venue in rounds where it hosts, at the host's venue in rounds where it is away, starts at home before the first round, returns home after the last, and travels directly between consecutive locations; the cost of the schedule is the sum over teams of total distance traveled. The schedule must have no team playing more than two consecutive home games or more than two consecutive away games, and no pair of teams meeting in two consecutive rounds. Is finding a minimum-cost such schedule polynomial-time solvable, or is it NP-hard? With the bound two replaced by any fixed bound at least three the problem is NP-hard, and the unconstrained version is APX-hard, while this tour-length-two case admits a polynomial-time approximation scheme.
:::

## Constraint satisfaction and graph mappings

::: {.problem #problem-s-tractability-dichotomy title="Dichotomy for surjective minimum violation"}
Fix a finite pattern digraph $H=(D,F)$, with loops allowed. Given a finite digraph $G=(V,E)$ with $|V|\ge|D|$ and binary-encoded nonnegative integer arc weights $w$, a feasible solution is a surjection $\phi:V\twoheadrightarrow D$, whose violation is the total weight $\sum_{uv\in E:(\phi(u),\phi(v))\notin F}w(uv)$ of arcs not mapped to arcs of $H$. Call $H$ s-tractable if a minimum-violation surjection can be found in polynomial time. Can one characterize the s-tractable patterns and prove that, for every fixed $H$, this optimization problem is either polynomial-time solvable or NP-hard? The objective can be viewed as a weighted surjective valued CSP built from the binary $0$-$1$ violation function of $H$. In the unit-weight special case, deciding whether the optimum is zero is ordinary surjective $H$-coloring, a surjective CSP; thus the two dichotomy questions are related, but their classifications are not asserted to be equivalent.
:::

## Submodular optimization

::: {.problem #problem-separated-submodular-3-partition title="Minimum separated submodular 3-partition"}
Let $U$ be a finite set with $|U|\ge3$, let $s,t\in U$ be distinct, and suppose a value oracle returns $f(S)$ for every queried $S\subseteq U$, where $f:2^U\to\mathbb R$ is submodular, meaning $f(A)+f(B)\ge f(A\cap B)+f(A\cup B)$ for all $A,B\subseteq U$. Can one use polynomially many oracle calls and polynomial additional computation to find three nonempty pairwise disjoint sets $A,D,C$ whose union is $U$, with $s\in A$ and $t\in D$, and that minimize $f(A)+f(D)+f(C)$?
:::

::: {.problem #problem-ranked-submodular-3-partition title="Ranked enumeration of submodular 3-partitions"}
Let $U$ be a finite set with $|U|\ge3$, and suppose a value oracle returns $f(S)$ for every queried $S\subseteq U$, where $f:2^U\to\mathbb R$ is submodular, meaning $f(A)+f(B)\ge f(A\cap B)+f(A\cup B)$ for all $A,B\subseteq U$. A 3-partition is an unordered family $\mathcal P=\{P_1,P_2,P_3\}$ of three nonempty pairwise disjoint sets whose union is $U$, and its value is $\Phi_f(\mathcal P)=\sum_{P\in\mathcal P}f(P)$. Can one output every 3-partition exactly once in nondecreasing order of $\Phi_f$, with ties in any order, after polynomial preprocessing and with amortized polynomial delay? Concretely, is there a polynomial $p$ such that, for every $r$ up to the total number of outputs, producing the first $r$ partitions takes at most $(r+1)p(|U|)$ oracle calls and additional computation, and termination is certified within another $p(|U|)$ oracle calls and additional computation after the final output?
:::

::: {.problem #problem-submodular-5-partition title="Minimum submodular 5-partition"}
Let $U$ be a finite set with $|U|\ge5$, and suppose a value oracle returns $f(S)$ for every queried $S\subseteq U$, where $f:2^U\to\mathbb R$ is submodular, meaning $f(A)+f(B)\ge f(A\cap B)+f(A\cup B)$ for all $A,B\subseteq U$. Can one use polynomially many oracle calls and polynomial additional computation to find five nonempty pairwise disjoint sets $P_1,\ldots,P_5$ whose union is $U$ and that minimize $\sum_{i=1}^5f(P_i)$?
:::

## Matroids and delta-matroids

::: {.problem #problem-destroying-rigidity title="Destroying rigidity"}
Call an edge set $F$ of a finite simple graph sparse if $|F'|\le 2|V(F')|-3$ for every nonempty $F'\subseteq F$, where $V(F')$ is the set of endpoints of $F'$. A graph $G=(V,E)$ with $|V|\ge2$ is rigid in the plane if some sparse $F\subseteq E$ has $|F|=2|V|-3$; this characterizes generic rigidity of bar-and-joint frameworks in the plane. Given a rigid graph $G$, can the minimum number of edges whose deletion leaves a non-rigid graph be computed in polynomial time? Equivalently, compute a minimum-size cocircuit of the two-dimensional rigidity matroid of $G$. This is a special case of minimum cocircuit in count matroids; for transversal matroids the minimum cocircuit is polynomial while the minimum circuit is NP-hard, so neither answer is predictable from the general matroid picture.
:::

::: {.problem #problem-gabow title="Gabow's serial symmetric exchange conjecture"}
Let $M$ be a finite rank-$r$ matroid with disjoint bases $B_1$ and $B_2$. Is it always possible to write $B_1=\{x_1,\ldots,x_r\}$ and $B_2=\{y_1,\ldots,y_r\}$ so that, for every $i\in\{0,\ldots,r\}$, both $(B_1\setminus\{x_1,\ldots,x_i\})\cup\{y_1,\ldots,y_i\}$ and $(B_2\setminus\{y_1,\ldots,y_i\})\cup\{x_1,\ldots,x_i\}$ are bases of $M$?
:::

::: {.problem #problem-even-delta-proximity title="Finite-forbidden-set proximity for even delta-matroids"}
Let $E$ be finite and let $\mathcal D\subseteq2^E$ be a nonempty family whose members all have the same parity and which satisfies symmetric exchange: for every $X,Y\in\mathcal D$ and $e\in X\mathbin\triangle Y$, some $f\in X\mathbin\triangle Y$ satisfies $X\mathbin\triangle\{e,f\}\in\mathcal D$; such a pair $(E,\mathcal D)$ is an even delta-matroid, and the members of $\mathcal D$ are its feasible sets. Fix an abelian group $\Gamma$, elements $\gamma_0,\gamma_e\in\Gamma$, real numbers $c_0,c_e$, and define $\lambda(X)=\gamma_0+\sum_{e\in X}\gamma_e$ and $c(X)=c_0+\sum_{e\in X}c_e$. Given a finite forbidden set $F\subseteq\Gamma$ and assuming some feasible set $X$ has $\lambda(X)\notin F$, must every minimizer $A$ of $c$ over all feasible sets admit a minimizer $B$ of $c$ over the feasible sets with $\lambda(B)\notin F$ such that $\tfrac12|A\mathbin\triangle B|\le|F|$?
:::

## Strings and sequences

::: {.problem #problem-commonest-subsequence title="Commonest subsequence"}
Given a string $s$ of length $n$ over a finite alphabet, an occurrence of a nonempty string $p$ as a subsequence of $s$ is a strictly increasing tuple of $|p|$ positions of $s$ that spell out $p$. Find a string $p$ maximizing the number of occurrences of $p$ as a subsequence of $s$; is this optimization problem solvable in polynomial time, or is it NP-hard? For a fixed $p$ the number of occurrences is computable by dynamic programming with $O(n\,|p|)$ arithmetic operations, and some optimal $p$ has length at most $n$, so the decision version is in NP; no polynomial-time algorithm and no hardness result is known, and the optimum is not understood even for periodic strings.
:::

## Permutations and sorting

::: {.problem #problem-couples-seating-swaps title="Seating couples with fewest swaps"}
Let $n$ distinct people occupy $n$ seats arranged in a cycle, and let $2k$ of them form $k$ couples, with $k$ part of the input. A swap exchanges the occupants of any two seats. Find, in polynomial time, a shortest sequence of swaps after which the two members of every couple occupy adjacent seats. Equivalently, over all target arrangements in which some $k$ pairwise disjoint pairs of adjacent seats host the $k$ couples, minimize the number of people whose seat changes minus the number of nontrivial cycles of the displacement permutation. The special case $n=2k$ reduces to minimizing over the two adjacent-pair matchings of an even cycle with all seats coupled, which is solvable in polynomial time by cycle counting; the presence of singles and the free choice of the couples' seat pairs make the general complexity open.
:::

## Geometry of numbers and integer programming

::: {.problem #problem-relaxation-complexity-2d title="Relaxation complexity in the plane"}
Let $V\subseteq\mathbb Z^2$ be a finite set with binary-encoded coordinates whose convex hull is full-dimensional, and let $X=\operatorname{conv}(V)\cap\mathbb Z^2$. A relaxation of $X$ is a polyhedron $Q\subseteq\mathbb R^2$ with $Q\cap\mathbb Z^2=X$, and the relaxation complexity $\operatorname{rc}(X)$ is the minimum number of facets of a relaxation of $X$. Can $\operatorname{rc}(X)$ be computed in time polynomial in the binary encoding size of $V$, and even in strongly polynomial time, meaning a number of arithmetic operations bounded by a polynomial in $|V|$ alone? The known algorithm runs in time polynomial in $|V|$ and the number of observers of $X$ — the integer points $z\notin X$ with $\operatorname{conv}(X\cup\{z\})\cap\mathbb Z^2=X\cup\{z\}$ — and the number of observers can be exponential in the encoding size, so that algorithm is only pseudopolynomial. In dimension at least four even the computability of $\operatorname{rc}(X)$ is open.
:::

## Matching, allocation, and games

::: {.problem #problem-exact-matching title="Exact matching complexity"}
Given a finite undirected graph $H=(V,E)$, a designated set $F_{\mathrm{red}}\subseteq E$ of red edges, and an integer $r$, decide whether there is a set $M\subseteq E$ such that every vertex is incident with exactly one edge of $M$ and $|M\cap F_{\mathrm{red}}|=r$; does this decision problem have a deterministic polynomial-time algorithm? A randomized polynomial-time algorithm is known. If every edge also has a nonnegative integer cost $c(e)$ encoded in binary, the min-cost variant asks for such an $M$ minimizing $\sum_{e\in M}c(e)$; when the costs are not polynomially bounded, does this optimization problem have any polynomial-time algorithm?
:::

::: {.problem #problem-labelled-bin-filling title="Labelled-bin filling complexity"}
For bins $i=1,\ldots,n$ and item types $j=1,\ldots,m$, the input consists of positive integer weights $0<w_1<\cdots<w_m$ satisfying $w_1\mid w_2\mid\cdots\mid w_m$, nonnegative integer preferred counts $a_{ij}$, global supplies $B_j$, and target values $h_i$, all binary-encoded; one must choose counts $x_{ij}\in\mathbb Z_{\ge0}$ satisfying $\sum_jw_jx_{ij}=h_i$ for every bin $i$ and $\sum_ix_{ij}\le B_j$ for every type $j$, while minimizing $\sum_{i,j}|x_{ij}-a_{ij}|$. For every fixed number of bins $n\ge3$, can this optimum be computed in polynomial time when the number of types and all numerical data are part of the input; more strongly, is there an algorithm running in $g(n)\operatorname{poly}(N)$ time, where $N$ is the input bit length, or is the problem W[1]-hard parameterized by $n$? The first unresolved slice already has $n=3$ and weights $(1,2,4,\ldots,2^{m-1})$. Separately, when $m$ is unbounded, is there an exact algorithm running in $\operatorname{poly}(N,w_m)$ time?
:::