Open Question Zoo

A polynomial reduction would give both recognition and tree construction for the remaining traversal-support case.

This isolates the difficulty of comparing evolutionary networks under a basic structural simplification.

The question separates easy spanning-forest existence from the constraints imposed by proper phylogenetic forest representations.

The diameter restriction targets a missing boundary in the structural complexity of perfect matching cuts.

This addresses a small-radius boundary for a matching that also acts as an edge separator.

The question asks whether one fewer distance layer crosses the tractability boundary for Matching Cut.

This resolves a missing radius case between known tractable and hard regions.

A result would determine the exact maximum-degree boundary for 2-Cut on claw-free graphs.

A hardness result would isolate the effect of deadlines in a highly uniform coupled-task scheduling model.

This tests whether a small uniform orientation constraint can encode Boolean computation without supplied constants.

Depth three is a boundary between simpler representations and known harder cases in intersection-graph recognition.

The question seeks the missing diameter boundary for Perfect Matching Cut.

This asks whether arithmetic matching remains hard when two lists are fixed consecutive integers and the remaining list is distinct.

The question concerns the cost of comparing compact representations of uncertain strings.

Real-algebraic hardness would strengthen ordinary NP-hardness and identify a deeper obstruction in robust low-rank fitting.

This addresses the complexity difference between parity conditions imposed on some cycles and on all cycles of a factor.

The question isolates assignment complexity after sequencing choices have been removed.

Hadamard factorization is a compact matrix representation; this asks whether deciding exact representability is computationally hard.

This targets the total rank cost used to measure Hadamard representation size, rather than a preassigned allocation of ranks.

This asks whether allowing a second alternation changes the complexity of a tightly constrained reconfigurable network model.

This addresses recognition when the alphabet is an input parameter, beyond fixed-alphabet structural results.

The d=2 case tests a missing boundary for degree-bounded cuts on line graphs.

Width-one recognition concerns the simplest nontrivial level of a width measure used for graph algorithms.

This tests recognition on a small host where branching and non-crossing constraints interact.

The question would distinguish arithmetic restrictions from real rank-two factorization in the smallest nontrivial matrix shape.

Nonuniform costs remove a symmetry exploited in sequential testing and may change the complexity of choosing an order.

The question connects a combinatorial marginal-consistency problem to a normalized polynomial representation.

This targets exact training complexity in two input dimensions under normalization, closer to a basic learning model than unrestricted constructions.

The question addresses a forbidden-path boundary for perfect matching cuts.

Together with P5-free tractability, hardness here would identify an exact forbidden-path boundary.

The question refines the structural boundary for finding small matching separators.

Multipacking links metric packing constraints to domination-type graph parameters; planar hardness would clarify how geometry affects its complexity.

This separates the complexity of order dimension from the complexity of obtaining a planar drawing.

Allowing new vertices changes the feasible extensions and is not automatically covered by edge-only augmentation hardness.

The question isolates the complexity contributed by choosing the partition in an ordering-based graph representation.

Does fitting just two nonnegative components already make exact global optimization NP-hard?

This tests the effect of connectivity requirements on a small fixed collection of coloring bundles.

Real-algebraic hardness would explain geometric recognition difficulty beyond ordinary combinatorial NP-hardness.

Visibility recognition is a central inverse problem in computational geometry: reconstruct geometry from pairwise visibility information.

The restriction asks how much complexity survives when the graph decomposes into a clique and an independent set.

This isolates existence complexity in a small-valued symmetric coalition model.

This tests whether fairness remains algorithmically accessible when feasibility conflicts and maximality interact, even for three identical agents.

This is a longstanding small-machine scheduling boundary with broad relevance to precedence-constrained computation.

The question asks whether a fixed number of job types suffices for exact scheduling tractability under compressed multiplicities.

The question isolates the effect of adding one required visit in a recurring scheduling model.

This asks whether the lowest nontrivial clearing threshold already supports computational hardness.

Removing teleportation tests whether local feature transitions alone create hardness in the puzzle model.

The question asks whether assignment flexibility causes hardness even with just two machines.

This addresses a remaining forbidden-induced-subgraph case for bounded-degree cuts.

This asks whether recognizing the next queue level inherits the difficulty of one-queue recognition.

The question asks whether choosing a mixed layout is hard even on a narrowly structured graph class.

The question combines geometric restrictions with a coloring rule that permits monochromatic cliques, beyond ordinary proper coloring.

This isolates the difference between recognizing a representation with supplied classes and discovering the classes.

The task reconstructs a usable hardness rule for lossless rectangle-based representation of binary images.

This reconstructs a rule for selecting reusable dictionary phrases under an explicit storage-cost model.

A reconstructed rule connects covering to reusable set representations and Boolean data decomposition.

Can two nearby matching markets be encoded so every satisfying Boolean assignment yields a matching stable in both?

The next host-switch distance after the polynomial case may change the cost of reconstructing host-parasite evolution.

Does requiring cluster centers to lie at approved graph locations make radius-sum clustering classically NP-hard?

Can a sparse directed network on plane points meet a prescribed round-trip stretch while keeping all straight edges crossing-free?

Can the interval order of overlapping jobs or channels compress a variable number of cluster-graph color classes into a polynomial flow model?

Does a multiplicative profit target remain hard when profit magnitudes are written out explicitly?

A narrow strip of wireless-network disks may be the boundary between easy and hard two-channel grouping.

Can ordered, prefix-shaped inhibition alone make molecule-preserving reaction reachability hard?

The interaction of release times and merging precedence on two processors is a long-standing scheduling threshold case.

Can weakly dominated choices be eliminated to one outcome when every player sees only the count choosing each action?

Does requiring one designated edge to survive on every s–t path make undirected network diversion NP-hard? A hardness reduction would settle one side of a long-open boundary in network interdiction.

Can three-terminal separation be encoded when each path must traverse temporal edges at strictly increasing times and meet a travel-time deadline?

Is finding a short conflict-serializable transaction schedule already NP-hard when only two shared objects can cause conflicts?

Can energy-autarkic scheduling become strongly NP-hard when every unit-length job has only two consecutive possible start times?

Could a flow formulation solve exact fair correlation clustering on a path when the minority-to-majority color ratio is 1:c and c is part of the input?

Can a compact flow model find an allocation of path-based service tasks that is simultaneously EF1, minimax-share fair and Pareto optimal, or certify none exists?

Do two distinct transplant weights already make fair selection among maximum-weight two-way kidney exchanges NP-hard when each country owns at most two patient–donor pairs?

Can a deterministic polynomial-size flow construction optimize a binary-weighted perfect matching subject to exactly k red edges?

Does independent scheduling of the two directions of each tree edge still leave total periodic travel waiting time NP-hard to minimize?

Can the unique nucleolus of a graph-encoded permutation game be recovered from a polynomial-size rational linear program?