Unrooted Quartet Consistency → Mim-width at most one Complexity open
Unsolved
Why this question matters
Width-one recognition concerns the simplest nontrivial level of a width measure used for graph algorithms.
The cited width-recognition question concerns induced matchings across decomposition cuts. Results about related width measures cannot be substituted for mim-width one.
The reduction to construct
The source is a finite collection of labelled quartet trees. Its outputs are unrooted trees displaying every prescribed quartet, or NO-SOLUTION.
The source asks for a tree displaying a collection of prescribed unrooted quartets. The target asks for a branch decomposition of a graph such that every cut has bipartite induced matching number at most one.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
A construction must force a compatible decomposition tree rather than only exhibit one for positive instances.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.