Open problems
These questions remain open to my knowledge. Last status check: 16 November 2026. Solved problems will be removed, and no history of this list will be maintained here.
Does every finite bridgeless multigraph admit a multiset of oriented circuits traversing every edge exactly once in each direction? Parallel edges may form a -cycle, whereas traversing one edge forward and immediately back is not a circuit.
Fix an integer . Let be a finite connected undirected multigraph with , with partitioned into nonempty hedges such that the subgraph formed by each hedge and its incident vertices has at most connected components. Can a minimum-cardinality set of hedges whose removal disconnects be found in deterministic polynomial time?
Randomized polynomial time is known (Chandrasekaran et al., Theorem 1.1).
Given a finite digraph with and binary-encoded nonnegative rational arc costs, find a minimum-cost arc set such that has two distinct vertices with no directed path between them in either direction. Unlike - bicut, the separated pair is not prescribed. Is this problem polynomial-time solvable or NP-hard?
Stated as open in Bérczi et al. (p. 413).
Given a finite digraph with and no prescribed terminals, find a minimum-cardinality arc set such that has at least three strongly connected components. Is this problem polynomial-time solvable or NP-hard?
See my thesis (Definition 1.2 and Table 1.2).
Fix a finite digraph with , allowing loops. Given a finite digraph with and binary-encoded weights , minimize over surjections . Characterize the patterns for which this problem is polynomial-time solvable, and determine whether it is polynomial-time solvable or NP-hard for every .
Formulated in Kawarabayashi and Xu (§1, §7), which settles reflexive trees.
Let be a finite -vertex, -arc digraph with root , and for let be the maximum number of arc-disjoint directed -to- paths. Given an integer , can one construct a spanning subgraph with , , and for all in time, or even time?
Existence of such subgraphs follows from Szeszlér (Theorem 8).
For every fixed integer , is there a polynomial such that, given an arbitrary submodular function via a value oracle on an -element set with , one can partition into nonempty parts minimizing using at most oracle calls and arithmetic and comparison operations?
For background on fixed- submodular partitioning, see Hirayama et al. (§7).
Is there a polynomial such that, given an arbitrary submodular function via a value oracle on an -element set with and distinct , one can partition into three nonempty parts with and minimizing using at most oracle calls and arithmetic and comparison operations?
Approximation and variable-part variants are studied in Bérczi et al. (§1.1.1).
Is there a polynomial such that, given any submodular function via a value oracle on an -element set with , one can output every unordered partition of into three nonempty parts once in nondecreasing order of (ties broken arbitrarily), where producing the first outputs takes at most oracle calls and arithmetic and comparison operations for each up to the number of such partitions, and reporting termination takes at most more?
Ranked enumeration of submodular -partitions appears in Hirayama et al. (Lemma 5.2).
Given a finite undirected graph , a set of red edges, and an integer , is there a deterministic polynomial-time algorithm deciding whether has a perfect matching with ?
Randomized polynomial time is known (see Sebő, p. 6).
Given a finite undirected graph , a set of red edges, an integer , and binary-encoded costs , can one find a perfect matching minimizing subject to , or report that none exists, in time polynomial in the input bit length (allowing randomized algorithms with success probability at least on every input)?
Open even for bipartite graphs (Armbruster et al., §§5.2–5.3).
Let and be disjoint bases of a finite rank- matroid. Can their elements be ordered as and so that and are both bases for every ?
Stated in Akrami et al. (Conjecture 1.14) and proved for split and regular matroids.
Let be a finite even delta-matroid, an abelian group, , , and a finite forbidden set. Set and , and suppose is nonempty. For every minimizer of over , must there exist a minimizer of over with symmetric difference ?
Proved for matroid bases in Liu et al. (Theorem 1).
Given bins, item types (), and binary-encoded integers with , targets , supplies , and preferred counts (of total input bit length ), find integers minimizing subject to or report infeasibility.
Is this problem solvable in polynomial time for each fixed (even when and )? More strongly, is it solvable in time for some computable , or is the decision version with a binary-encoded cost threshold W[1]-hard parameterized by ? For unrestricted and , is there an exact -time algorithm?
See my question on filling bins with minimum moves.
Can six closed unit squares in the Euclidean plane, translated and rotated independently with overlaps allowed, cover an entire square of side length strictly greater than ?
Five unit squares cannot, while seven suffice (Dósa et al., Conjecture 1.1 and Theorem 1.3).