Search

The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47-66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2 w, in time $$2^{O(w^2\log w)} \cdot n^2$$ . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known. [ABSTRACT FROM AUTHOR]

Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O( n+ m) α( n+ m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205-240, ), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper (Gioan et al. in , ) uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fully dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs. [Copyright &y& Elsevier]

This paper considers the problem of maintaining a compact representation ( O( n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O( n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs. [ABSTRACT FROM AUTHOR]

Abstract: Modular decomposition is a technique that applies to (but is not restricted to) graphs. The notion of a module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to solve a large number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 1970’s, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research. [Copyright &y& Elsevier]

Abstract: This paper revisits the ‘branchwidth territories’ of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called -troikas: three sets of size at most each are a -troika of set , if any two have union . We give a straightforward algorithm, computing branchwidth for an interval graph on edges, vertices and maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees. [Copyright &y& Elsevier]

Abstract: Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most have well-known alternative characterizations as subgraphs of chordal graphs and as partial -trees. In this paper we give analogous alternative characterizations for graphs of branchwidth at most . We first show that they are the subgraphs of chordal graphs where every maximal clique has three subsets of size at most each such that any two subsets have union , with the property that every minimal separator contained in is contained in one of the three subsets. Secondly, we give a characterization of the edge-maximal graphs of branchwidth , that we call -branches. [Copyright &y& Elsevier]

Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as P4-reducible, P4-sparse, and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition. [ABSTRACT FROM AUTHOR]