# Publications

Here is my publications list (hover over the elements to display an abstract). You can also consult a part of this list according to DBLP. Some of my publications are also available on arXiv or HAL.

## Journals

• First difference principle applied to modular/questionable-width, clique-width, and rank-width of binary structures. Laurent Lyaudet
[.pdf]
In this article, we study various widths/decompositions of binary structures under the light of first difference principle. We show the equality of modular-width and questionable-width, although questionable representation is more primitive/crude than modular/clan decomposition. Using first difference principle, we show that clique-decomposition of binary structures has a sequential equivalent, that we call clique-questionable representation. Last but not least, we give remarks on the true validity of rank-width of binary structures.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf] , [v5.pdf]
• On level-induced suborders. Laurent Lyaudet
[.pdf]
In this article, we characterize orders that are level-induced suborders anytime they are induced suborders of a superorder. We also characterize orders that are consecutive level-induced suborders anytime they are level-induced suborders of a superorder. Thus characterizing orders that are consecutive level-induced suborders anytime they are induced suborders of a superorder.
• Erratum to “On Operations and Linear Extensions of Well Partially Ordered Sets”. Laurent Lyaudet
[.pdf]
In this article, we give a counter-example to Lemma 12 of the article “On Operations and Linear Extensions of Well Partially Ordered Sets” by Maciej Malicki and Aleksander Rutkowski (2003).
• On finite width questionable representations of orders. Laurent Lyaudet
[.pdf]
In this article, we study "questionable representations" of (partial or total) orders, introduced in our previous article "A class of orders with linear? time sorting algorithm". (Later, we consider arbitrary binary functional/relational structures instead of orders.) A "question" is the first difference between two sequences (with ordinal index) of elements of orders/sets. In finite width "questionable representations" of an order O, comparison can be solved by looking at the "question" that compares elements of a finite order O'. A corollary of a theorem by Cantor (1895) is that all countable total orders have a binary (width 2) questionable representation. We find new classes of orders on which testing isomorphism or counting the number of linear extensions can be done in polynomial time. We also present a generalization of questionable-width, called balanced tree-questionable-width, and show that if a class of binary structures has bounded tree-width or clique-width, then it has bounded balanced tree-questionable-width. But there are classes of graphs of bounded balanced tree-questionable-width and unbounded tree-width or clique-width.
• A class of orders with linear? time sorting algorithm. Laurent Lyaudet
[.pdf]
In this article, we give a precise mathematical meaning to "linear? time" that matches experimental behaviour of the algorithm. The sorting algorithm is not our own, it is a variant of radix sort with counting sort as a subroutine. The true result of this article is an efficient universality result for lexicographic order, or more generally for some linear extensions of the partial order "Next": "if current items are equal, compare next items". We define new classes of orders: (Finite width) Tree Structured Orders. We show that an instance of a finite width tree structured order can be converted in linear time and space to an instance of lexicographic order. The constants implied by the "nextification" algorithm are small (around 3 for real world orders). The class of finite width tree structured orders contains finite orders ({0, 1}, int32, int64, ..., float, double, ...), and orders contructed from them on a tree structure. In particular, unbounded integers, strings with arbitrary collation, and all orders used for sorting SQL queries are finite width tree structured orders.
• Distance preserving subtrees in minimum average distance spanning trees. Laurent Lyaudet, Paulin Melatagia Yonta, Maurice Tchuenté, and René Ndoundam
Published in Discrete Mathematics, Algorithms and Applications Volume 5 Issue 3 (2013) 1350010. [.pdf]
Given an undirected graph G = (V, E) with n vertices and a positive length w(e) on each edge e ∈ E, we consider Minimum Average Distance (MAD) spanning trees i.e., trees that minimize the path length summed over all pairs of vertices. One of the first results on this problem is due to Wong who showed in 1980 that a Distance Preserving (DP) spanning tree rooted at a median vertex of G is a 2-approximate solution. On the other hand, Dankelmann has exhibited in 2000 a class of graphs where no MAD spanning tree is distance preserving from a vertex. We establish here a new relation between MAD and DP trees. We show that in a MAD spanning tree of G, each subtree T' = (V', E') consisting of a vertex r and the union of branches of r that are each of size less than or equal to √(n/2w+), where w+ is the maximum edge-length in G, is a distance preserving spanning tree of the subgraph of G induced by V'.
• Partitions versus sets : a case of duality. Laurent Lyaudet, Frédéric Mazoit, and Stéphan Thomassé.
Published in European Journal of Combinatorics 31 (2010) 681–687.[.pdf]
In a recent paper, Amini et al. introduced a general framework to prove duality theorems between tree decompositions and their dual combinatorial object. They unify all known ad-hoc proofs in one duality theorem based on submodular partition functions. This general theorem remains however a bit technical and relies on this particular submodularity property. Instead of partition functions, we propose here a simple combinatorial property of set of partitions which also gives these duality results. Our approach is both simpler, and a little bit more general. We also prove that, under a reasonnable assumption, the duality property is a sufficient condition for the exhibited combinatorial property.
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth. Uffe Flarup and Laurent Lyaudet.
Published in the journal Theory of Computing Systems Volume 46, Issue 4 (2010) 761-791.[.pdf]
Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) include the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the ex- pressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matri- ces of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.
• NP-hard and linear variants of hypergraph partitioning. Laurent Lyaudet.
Published in the journal Theoretical Computer Science 411(1) (2010) 10–21.[.pdf]
This article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems. We define problem Pkl as a purely constraint-driven variant of hypergraph partitioning with parameters k and l as follows: Given a hypergraph on n vertices and k sizes of colours t1, ..., tk of sum n, can we colour the vertices with k colours of given size such that each hyperedge intersects at most l colours? We show that, for fixed parameters k and l, Pkl is: polynomial when l = 1, and NP-complete when l ≠ 1 on the class of hypergraphs; NP-complete when l = 1, and linear when l ≠ 1 on the class of hypergraphs with pairwise disjoint hyperedges. This inversion of complexity is possible since hypergraphs with disjoint hyperedges can be encoded in a more compact way, namely Θ(m log(n)) instead of Θ(mn) bits (n and m are the numbers of vertices and edges of the hypergraph).

## International conferences

• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth. Uffe Flarup and Laurent Lyaudet.
Proceedings of CSR 2008 (Russia), LNCS 5010 : 180-193.[.pdf]
Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) include the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the ex- pressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matri- ces of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. Uffe Flarup, Pascal Koiran, and Laurent Lyaudet.
Proceedings of ISAAC 2007 (Japan), LNCS 4835 : 124-136. [.pdf]. Corrigendum [.pdf]. Corrected version [.ps].
Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and NP. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. In this paper we investigate the expressive power of easy special cases of these polyno- mials. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth both are equivalent to arithmetic formu- las. Also, arithmetic weakly skew circuits are shown to be equivalent to the sum of weights of perfect matchings of planar graphs.

## Thesis

• Ph.D. Thesis (French): Graphes et hypergraphes : complexités algorithmique et algébrique [.pdf].
Here you can read an extended abstract in English: [.pdf]
Beware, this abstract comports irony and humor.
In this dissertation, we defend the idea that, for any reasonnable model of computation, this is not the model that is important to caracterize important complexity classes. Instead, what matters is the complexity of the underlying combinatorial structure and, at the end, the underlying graph. If we take the example of boolean or algebraic circuits as models, all that matters is the complexity of the underlying digraph. By a reasonnable model of computation, we mean, as is requested, a model that when studied on a standard class of graphs will give the standard complexity class we expect, in order to statisfy the elementary rules of tautologies. One could also choose as reasonnable models the Turing-complete models (or another notion of completeness more suited to the computed objects), that can be formalized in a simple logic (in order to avoid "cheats" and models designed specialy to falsify this beautiful claim). Nevertheless, since this second option may be risky, we only propose it. The defended thesis is a more formalized and more mathematically precise version of this idea with hollow limits (and hence a little false as it is).
• Master Thesis (French): Largeur de branche des graphes de corde. [.ps]
In this dissertation, we study the complexity of computing the branchwidth of circle graphs. We show that an upper bound can be computed in polynomial time. We also study a hypergraph partitioning problem linked to our initial problem, and show that it can also be solved in polynomial time.

## Research reports

• Partitions versus sets : a case of duality. Laurent Lyaudet, Frédéric Mazoit, and Stéphan Thomassé. 2008.[.pdf]
In a recent paper, Amini et al. introduced a general framework to prove duality theorems between tree decompositions and their dual combinatorial object. They unify all known ad-hoc proofs in one duality theorem based on submodular partition functions. This general theorem remains however a bit technical and relies on this particular submodularity property. Instead of partition functions, we propose here a simple combinatorial property of set of partitions which also gives these duality results. Our approach is both simpler, and a little bit more general. We also prove that, under a reasonnable assumption, the duality property is a sufficient condition for the exhibited combinatorial property.
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth. Uffe Flarup, Laurent Lyaudet.
LIP research report n° RR2008-05, ENS Lyon, 2008.[.pdf]
Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) include the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the ex- pressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matri- ces of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. Uffe Flarup, Pascal Koiran, Laurent Lyaudet.
LIP research report n° RR2007-20, ENS Lyon, 2007.[.pdf]
Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and NP. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. In this paper we investigate the expressive power of easy special cases of these polyno- mials. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth both are equivalent to arithmetic formu- las. Also, arithmetic weakly skew circuits are shown to be equivalent to the sum of weights of perfect matchings of planar graphs.
• Threshold effect in algorithmic complexity: NP-hard and linear variants of hypergraph partitioning. Laurent Lyaudet.
LIP research report n° RR2005-46, ENS Lyon, 2005.[.ps]
This article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems. We define problem Pkl as a purely constraint-driven variant of hypergraph partitioning with parameters k and l as follows: Given a hypergraph on n vertices and k sizes of colours t1, ..., tk of sum n, can we colour the vertices with k colours of given size such that each hyperedge intersects at most l colours? We show that, for fixed parameters k and l, Pkl is: polynomial when l = 1, and NP-complete when l ≠ 1 on the class of hypergraphs; NP-complete when l = 1, and linear when l ≠ 1 on the class of hypergraphs with pairwise disjoint hyperedges. This inversion of complexity is possible since hypergraphs with disjoint hyperedges can be encoded in a more compact way, namely Θ(m log(n)) instead of Θ(mn) bits (n and m are the numbers of vertices and edges of the hypergraph).

## Unpublishables

• (French) Cadeau bonux. Bibi. [.pdf]
In this "cadeau bonux", we caracterize the families of subsets that can be defined as the level 0 of a submodular function.
• (French) Cadeau bonux 2 : le retour. Bibi. [.pdf]
In this "cadeau bonux", we caracterize the families of subsets that can be defined as the level 0 of a modular function.
• (French) Tout est explicite. Bibi. [.pdf]
A simple element of truth for those who care. The ideal is, in my opinion, to read the abstract of my thesis on this webpage when one hovers over the element, then to read "Tout est explicite", and last to read my thesis (or only the introduction and conclusion, of the original dissertation or of the extended abstract in english).
Sylvain Périfel was kind enough to give me feedback on this text and he confirmed me that the way model of computation to problem can be considered as "presque explicite / folklore".