Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

DOI10.1007/S00453-016-0164-5MaRDI QIDQ527431zbMATH OpenOpenAlexWikidataFDO

Authors Isolde Adler, Mamadou Moustapha Kanté, O-joung Kwon

Publication date 11 May 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1081, http://eprints.whiterose.ac.uk/101097/7/16AKK.pdf

zbMATH Keywords

distance-hereditary graphslinear rank-widthmatroid branch-widthmatroid path-widthrank-widthvertex-minors

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every $n$-vertex distance-hereditary graph, equivalently a graph of rank-width at most $1$, can be computed in time $mathcalO(n^{2}cdotlo{g}_{2}n)$, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every $n$-element matroid of branch-width at most $2$ can be computed in time $mathcalO(n^{2}cdotlo{g}_{2}n)$, provided that the matroid is given by an independent set oracle. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50--79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of `limbs' of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization.

Recommendations

• Linear rank-width of distance-hereditary graphs
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Linear rank-width and linear clique-width of trees
• Linear rank-width and linear clique-width of trees
• Rank-width and vertex-minors

Cites work

• A Combinatorial Decomposition Theory
• Approximating clique-width and branch-width
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Branch-width and well-quasi-ordering in matroids and graphs.
• Circle graph obstructions under pivoting
• Constructive algorithm for path-width of matroids
• Distance labeling scheme and split decomposition
• Distance-hereditary graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Graph theory
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 952954 (Why is no real title available?)
• Lectures on matroids
• Linear rank-width and linear clique-width of trees
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Matroid Pathwidth and Code Trellis Complexity
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Rank-width and vertex-minors
• Solving Rota's conjecture
• The complexity of searching a graph
• The rank-width of edge-coloured graphs
• The vertex separation and search number of a graph
• Thread graphs, linear rank-width and their algorithmic applications
• Transforming trees by successive local complementations
• Upper bounds to the clique width of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Well-quasi-ordering of matrices under Schur complement and applications to directed graphs

Cited in

(16)

• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• Linear rank-width and linear clique-width of trees
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Linear rank-width and linear clique-width of trees
• Linear rank-width of distance-hereditary graphs
• Classifying rankwidth k-dh-graphs
• scientific article; zbMATH DE number 841632 (Why is no real title available?)
• Tree pivot-minors and linear rank-width
• Directed rank-width and displit decomposition
• A polynomial kernel for distance-hereditary vertex deletion
• Graphs of bounded depth‐2 rank‐brittleness
• Twin-distance-hereditary digraphs
• Tree pivot-minors and linear rank-width

This page was built for publication: Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527431)