Monadic dependence from reducts, and applications to twin-width of oriented graphs
For researchers in structural graph theory and parameterized complexity, this work extends the understanding of twin-width and monadic dependence to new classes of oriented graphs, enabling efficient FO model checking.
The paper provides sufficient conditions for proving monadic dependence of binary relational structures by considering their reducts, and applies this to twin-width of oriented graphs. It shows that twin-width boundedness is equivalent to being expandable by an oriented graph with bounded independence number, and establishes delineation by twin-width for oriented split graphs and local tournaments, yielding fixed-parameter tractability of FO-model checking.
We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a structure is monadically dependent by only considering some of its reducts, assuming they are structurally well-behaved and compatible enough. As an application, we consider some reorientation rules preserving monadic dependence of binary structures, as well as replacement of one antisymmetric relation with bounded independence number by another. Then, we apply our main (technical) result to the study of twin-width in two ways. First, generalizing the fact that twin-width boundedness is equivalent to being expandable by a linear order into a monadically dependent class, we prove that it is also equivalent to being expandable by an oriented graph with bounded independence number (for instance by a poset with bounded width or by a tournament), and that FO-model checking is fixed-parameter tractable on such an expansion. Second, we show delineation by twin-width for some new classes of oriented graphs, including oriented split graphs and local tournaments. In all these cases, we also obtain fixed-parameter tractability of FO-model checking.