-
Factoriser des nombres entiers avec des graphes
et autres idées liées.
Laurent Lyaudet 2022
[
.pdf]
In this article, I propose to look at the integer factorization problem as a counting problem,
then to factorize or more generally have a calculus model made of graphs and
non trivial matrix operations.
Last, I present a funny factorization heuristic called Fibolous.
Warning : free speech and non-academic style.
Archive :
[
v1.pdf]
,
[
v2.pdf]
,
[
v3.pdf]
-
Diviser n'est pas régner ?.
Laurent Lyaudet 2022
[
.pdf]
In first year of algorithmic courses, we discover examples of "Divide and conquer" schemes,
where a good division of the instance of the studied algorithmic problem
yields also an efficient algorithm to solve it.
In this article, I present a way to divide efficiently all graphs of bounded degree.
It yields the interesting fact that if P ≠ NP,
then « Diviser n’est pas régner / Dividing is not reigning/conquering. ».
Archive :
[
v1.pdf]
,
[
v2.pdf]
,
[
v3.pdf]
,
[
v4.pdf]
,
[
v4.php]
,
[
v5.pdf]
,
[
v5.php]
,
[
v6.pdf]
,
[
v6.php]
-
First difference principle applied to modular/questionable-width, clique-width, and rank-width of binary structures.
Laurent Lyaudet 2020
[
.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 2020
[
.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 2019
[
.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 2019
[
.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 2017
[
.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]
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 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).
-
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.
-
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).