TWIN-WIDTH, ANR JCJC project (21-CE48-0014-01)

Open questions:

  • Is there an FPT approximation to compute twin-width?
    Formally, is there an algorithm A and two integer functions f and g such that, given a graph G and an integer k, A runs in time f(k)|G|O(1) and correctly reports that the twin-width of G is more than k, or outputs a g(k)-sequence of G? Such an algorithm exists for ordered graphs. That is the missing piece to claim fast parameterized algorithms on classes of bounded twin-width.

    Update: approximation is indeed required; deciding if a graph has twin-width 4 or 5 is NP-complete.

  • Find an explicit construction of bounded-degree graphs with unbounded twin-width.
    These graphs do exist, and are abundant, by a counting argument. Although this question may look innocuous, it is already open when replacing twin-width by the more restrictive queue or stack number. It showcases that lowerbounding the twin-width is an elusive issue.

    Update: The 3-dimensional grid with diagonals has been shown of unbounded stack number.

  • Do classes of polynomial expansion have bounded twin-width?
    If this is true, we are quite far from proving it. For instance, the following particular case is open: Does every class of Kt,t-free string graphs have twin-width at most some function of t? String graphs excluding a large clique can have arbitrarily large twin-width, even triangle-free unit segment graphs (see Section 3.6 and Figure 5 of this paper). Biclique-free segment graphs have bounded twin-width, but pure axis-parallel segment graphs without a half-graph of height 4 have unbounded twin-width. However, axis-parallel unit segment graphs without arbitrarily large half-graphs have bounded twin-width. See this paper.

  • Which classes are delineated by twin-width?
    Delineation of a class (by twin-width) roughly (but not exactly) means that every of its subclasses has bounded twin-width if and only if it cannot first-order interpret the class of all graphs. Effective delineation further requires an efficient algorithm that computes a contraction sequence or reports a witness of monadic independence (the fact that all graphs can be created from the subclass by means of a first-order transduction). Effective delineation of C implies that we have a complete understanding of exactly which subclasses of C admit an FPT first-order model checking algorithm; which for all subgraph-closed classes have already been settled, and for all the hereditary classes is an active ongoing research program. See this paper for formal definitions. Are unit segment graphs delineated? Are visibility graphs of 1.5D terrains delineated? Are there non-delineated classes that are not transduction equivalent to the class of all subcubic graphs? [Samuel Braunfeld has observed that there are.]

  • Known to be delineated: bounded twin-width classes, permutation graphs, ordered graphs, interval graphs, circle graphs, tournaments.

    Known to be non-delineated: bounded-degree graphs, split graphs, axis-parallel segment graphs, visibility graphs of simple polygons.

  • Are classes of bounded twin-width polynomially 𝛘-bounded? [Solved]
    By a rather simple argument, those classes are 𝛘-bounded (see Section 5 of this paper). If so, this would generalize the same result for classes of bounded clique-width. If not, this would refute an intriguing conjecture (see Polynomial 𝛘-boundedness) by Louis Esperet.

  • Update: On the one hand, Esperet's conjecture was disproved by Briański, Davies, and Walczak. On the other hand, Mi. Pilipczuk and Sokołowski have shown that classes of bounded twin-width are quasipolynomially 𝛘-bounded. Finally, Bourneuf and Thomassé have established the polynomial 𝛘-boundedness.

  • Give a better upper bound to the twin-width of planar graphs. [Essentially solved]
    There are several ways of bounding the twin-width of planar graphs: directly using the mixed-minor-freeness equivalence (see Section 6.3 of this paper), by bounding the twin-width of graphs with bounded stack or queue number (see Section 7.3 of this paper) since planar graphs have stack number at most 4, while the queue number of planar graphs was recently proved to be bounded (see this paper), similarly by bounding the twin-width of the strong product of two graphs in terms of their twin-width and the degree of one of them (see Theorem 38 of this paper), then invoking the product structure theorem (see Theorem 1 of this survey) and the boundedness of the twin-width of graphs with low treewidth, or finally via the functionally-equivalent oriented twin-width and the fact that every planar graph admits a pair of false twins or a pair of neighbors with small degree (see Lemma 2.2 of this paper). None of these proofs give a particularly good bound.

    Update: Jacob and Ma. Pilipczuk prove that planar graphs have twin-width at most 183, and B., Kwon, and Wood show that planar graphs have reduced-bandwidth (where the bound on the red graphs is on the bandwidth rather than on the degree) at most 466, and that classes of genus g have reduced-bandwidth O(g). Then, Bekos, Da Lozzo, Hliněný, and Kaufmann bring the twin-width upper bound for planar graphs down to 37. Hliněný further improves the upper bound to 9. (The 1-digit bound has been reached!) Now, Hliněný and Jedelský obtain the upper bound of 8, while Král and Lamaison get a lower bound of 7.
  • open questions