
Erratum to “On Operations and Linear Extensions of Well Partially Ordered Sets”
Laurent Lyaudet
[
.pdf]
In this article, we give a counterexample 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
Work in progress.
[
.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".
A "question" is the first difference between two sequences (with ordinal index) of elements of orders.
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.

A class of orders with linear? time sorting algorithm.
Laurent Lyaudet
Work in progress.
[
.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 2approximate 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 edgelength 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 adhoc 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) 761791.[
.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,
VNPcomplete) 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.

NPhard and linear variants of hypergraph partitioning. Laurent Lyaudet.
Published in the journal Theoretical Computer Science 411(1) (2010) 10–21.[
.pdf]
A comment on this article
here.
This article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems.
We define problem P_{k}^{l} as a purely constraintdriven variant of hypergraph partitioning with parameters k and l as follows:
Given a hypergraph on n vertices and k sizes of colours t_{1}, ..., t_{k} 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,
P_{k}^{l} is: polynomial when l = 1, and NPcomplete when l ≠ 1 on the class
of hypergraphs; NPcomplete 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).

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 Turingcomplete 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.

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 adhoc 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° RR200805, 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,
VNPcomplete) 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° RR200720, 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, VNPcomplete) 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: NPhard and linear variants of
hypergraph partitioning. Laurent Lyaudet.
LIP research report n° RR200546, 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 P_{k}^{l} as a purely constraintdriven variant of hypergraph partitioning with parameters k and l as follows:
Given a hypergraph on n vertices and k sizes of colours t_{1}, ..., t_{k} 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,
P_{k}^{l} is: polynomial when l = 1, and NPcomplete when l ≠ 1 on the class
of hypergraphs; NPcomplete 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).