chaoxu.prof

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.

Problem1Oriented cycle double cover

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.

See Gáborik et al. (p. 9).

Problem2Deterministic hedge min-cut

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).

Problem3Global edge-bicut

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).

Problem4Global linear 3-cut

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).

Problem5Dichotomy for surjective minimum violation

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.

Problem6Fast rooted connectivity certificates

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).

Problem7Minimum submodular k-partition

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).

Problem8Minimum separated submodular 3-partition

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).

Problem9Ranked enumeration of submodular 3-partitions

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).

Problem10Deterministic Exact Matching

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).

Problem11Minimum-cost Exact Matching

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).

Problem12Gabow’s serial symmetric exchange conjecture

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.

Problem13Finite-forbidden-set proximity for even delta-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).

Problem14Labelled-bin filling

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.

Problem15Covering a square by six unit squares

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).