[PDF] Flip-width: Cops and Robber on dense graphs | Semantic Scholar (2024)

This paper bound the cop-width and flip-width of a graph by its strong colouring numbers, showing that for every graph $G$ every graph has $\text{copwidth}_r(G)\leq \text{scol}_{4r}(G)$.

It is proved that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth, and the existence of an efficient approximation algorithm for the stretch- width of unordered graphs is left as open.

It is NP-hard to decide if k cops are sufficient to catch the robber, even if every cop layer is a tree and a set of isolated vertices, and the existence of an infinite family of graphs whose multi-layer cop number is bounded from below by a constant times $n / \log n$, where $n$ is the number of vertices in the graph.

It is proved that many different types of geometric graphs have unbounded flip-width, including interval graphs, permutation graphs, circle graphs, intersection graphs of axis- aligned line segments or axis-aligned unit squares, unit distance graphs, unit disk graphs, visibility graphs of simple polygons, and 3d Delaunay triangulations.

This work gives a characterization of graph classes interpretable in graph classes of tree rank that generalizes the result of Gajarsk\'y et al.

If the subgraph-closed graph classes for which the model checking problem is fixed-parameter tractable with an elementary dependency on the formula size excludes a fixed tree as a topological minor, then first-order model checking for graphs in the class is fixed-parameter tractable with an elementary dependency on the formula size.

...

...

This paper presents 2 O ( k ) n -time algorithms for k -Independent Set, r -Scattered Set, k -Clique, and k -Dominating Set when an O (1)-sequence of the graph is given in input, and shows how breadth-first search can be mimicked, when replacing “traversing an edge” by “Traversing a biclique all at once”.

It is proved that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph) and unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets.

The generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, and yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures.

This paper defines an oriented version of twin-width, where appearing red edges are oriented away from the newly contracted vertex, and the mere red out-degree should remain bounded, and explores the concept of partial contraction sequences, where, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class.

A robust methodology of local types is introduced and their behavior in contraction sequences -- the decomposition notion underlying twin-width is described to show optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin- width.

It is proved that computing the minimum number of cops that can catch a robber on a given graph is NP-hard, and it is shown that the parameterized version of the problem is W[2]-hard.

This paper introduces the notion of parity and linear minors of a matrix, which consists of iteratively replacing consecutive rows or consecutive columns with a linear combination of them, and presents an ad hoc algorithm to efficiently multiply two matrices of bounded twin-width.

...

...