BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph H as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when H is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when H is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the t-vertex cycle, Ct [Gartland et al., STOC '21] and the disjoint union of t triangles, tC3 [Bonamy et al., SODA '23]. We give, for every integer t, a polynomial-time algorithm running in nO(t5) when H is the friendship graph K1+tK2 (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in nO(t2logn)+f(t), with f a single-exponential function, when H is tC3⊎C4 (the disjoint union of t triangles and a 4-vertex cycle). The former extends a classical result on graphs excluding tK2 as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.'s result.
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometry. Thus, through Cayley graphs, it defines a group invariant. We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits. The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing 2O(n)⋅n! graphs on vertex set {1,…,n}, settling a question asked in a previous work.
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time f(d,k)n for n-vertex graphs given with a witness that the twin-width is at most d, called d-contraction sequence or d-sequence, and formulas of size k [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that f is a tower of exponentials of height roughly k. In this paper, we show that algorithms based on twin-width need not be impractical. We present 2O(k)n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence is provided. We further show how to solve weighted k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time 2O(klogk)n. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are χ-bounded. This significantly extends the χ-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time O(nlogn) and time O(n2logn), respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.
The twin-width of a graph G is the minimum integer d such that G has a d-contraction sequence, that is, a sequence of ∣V(G)∣−1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G. We show that if a graph admits a d-contraction sequence, then it also has a linear-arity tree of f(d)-contractions, for some function f. First this permits to show that every bounded twin-width class is small, i.e., has at most n!cn graphs labeled by [n], for some constant c. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an O(logn)-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that logΘ(loglogd)n-subdivisions of Kn (a small class when d is constant) have twin-width at most d. We obtain a rather sharp converse with a surprisingly direct proof: the logd+1n-subdivision of Kn has twin-width at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from K4~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.