Author name cluster

Maximilien Gadouleau

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

I&C Journal 2025 Journal Article

Generalising the maximum independent set algorithm via Boolean networks

Maximilien Gadouleau
David C. Kutner

A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neighbours are already in the set. In this paper, we consider (the complexity of decision problems related to) the generalisation of this MIS algorithm wherein any starting set is allowed. Two main approaches are leveraged. Firstly, we view the MIS algorithm as a sequential update of a Boolean network according to a permutation of the vertex set. Secondly, we introduce the concept of a constituency of a graph: a set of vertices that is dominated by an independent set. Recognizing a constituency is NP-complete, a fact we leverage repeatedly in our investigation. Our contributions are multiple: we establish that deciding whether all maximal independent sets can be reached from some configuration is coNP-complete; that fixing words (which reach a MIS from any starting configuration) and fixing permutations (briefly, permises) are coNP-complete to recognize; and that permissible graphs (graphs with a permis) are coNP-hard to recognize. We also exhibit large classes of permissible and non-permissible graphs, notably near-comparability graphs which may be of independent interest. Lastly, we extend our study to digraphs, where we search for kernels. Since the natural generalisation of our approach may not necessarily find a kernel, we introduce two further Boolean networks for digraphs: one always finds an independent set, and the other always finds a dominating set.

Details DOI

TCS Journal 2025 Journal Article

Linear Programming complementation

Maximilien Gadouleau
George B. Mertzios
Viktor Zamaraev

In this paper we introduce a new operation for Linear Programming (LP), called LP complementation, which resembles many properties of LP duality. Given a maximisation (resp. minimisation) LP P, we define its complement Q as a specific minimisation (resp. maximisation) LP which has the same objective function as P. Our central result is the LP complementation theorem, that relates the optimal value Image 1 of P and the optimal value Image 2 of its complement by Image 3. The LP complementation operation can be applied if and only if P has an optimum value greater than 1. To illustrate this, we first apply LP complementation to hypergraphs. For any hypergraph H, we review the four classical LPs, namely covering K ( H ), packing P ( H ), matching M ( H ), and transversal T ( H ). For every hypergraph H = ( V, E ), we call Image 4 the complement of H. For each of the above four LPs, we relate the optimal values of the LP for the dual hypergraph Image 5 to that of the complement hypergraph Image 6 (e. g. Image 7 ). We then apply LP complementation to fractional graph theory. We prove that the LP for the fractional in-dominating number of a digraph D is the complement of the LP for the fractional total out-dominating number of the digraph complement Image 8 of D. Furthermore we apply the hypergraph complementation theorem to matroids. We establish that the fractional matching number of a matroid coincide with its edge toughness. As our last application of LP complementation, we introduce the natural problem Vertex Cover with Budget (VCB): for a graph G = ( V, E ) and a positive integer b, what is the maximum number t b of vertex covers S 1, …, S t b of G, such that every vertex v ∈ V appears in at most b vertex covers? The integer b can be viewed as a “budget” that we can spend on each vertex and, given this budget, we aim to cover all edges for as long as possible. We relate VCB with the LP Q G for the fractional chromatic number χ f of a graph G. More specifically, we prove that, as b → ∞, the optimum for VCB satisfies t b ∼ t f ⋅ b, where t f is the optimal solution to the complement LP of Q G. Finally, our results imply that, for any finite budget b, it is NP-hard to decide whether t b ≥ b + c for any 1 ≤ c ≤ b − 1.

Details DOI

TCS Journal 2024 Journal Article

Factorisation in the semiring of finite dynamical systems

Émile Naquin
Maximilien Gadouleau

Finite dynamical systems (FDSs) are commonly used to model systems with a finite number of states that evolve deterministically and at discrete time steps. Considered up to isomorphism, those correspond to functional graphs. As such, FDSs have a sum and product operation, which correspond to the direct sum and direct product of their respective graphs; the collection of FDSs endowed with these operations then forms a semiring. The algebraic structure of the product of FDSs is particularly interesting. For instance, an FDS can be factorised if and only if it is composed of two sub-systems running in parallel. In this work, we further the understanding of the factorisation, division, and root finding problems for FDSs. Firstly, an FDS A is cancellative if one can divide by it unambiguously, i. e. A X = A Y implies X = Y. We prove that an FDS A is cancellative if and only if it has a fixed point. Secondly, we prove that if an FDS A has a k-th root (i. e. B such that B k = A ), then it is unique. Thirdly, unlike integers, the monoid of FDS product does not have unique factorisation into irreducibles. We instead exhibit a large class of monoids of FDSs with unique factorisation. To obtain our main results, we introduce the unrolling of an FDS, which can be viewed as a space-time expansion of the system. This allows us to work with (possibly infinite) trees, where the product is easier to handle than its counterpart for FDSs.

Details DOI

I&C Journal 2020 Journal Article

Elementary, finite and linear vN-regular cellular automata

Alonso Castillo-Ramirez
Maximilien Gadouleau

Let G be a group and A a set. A cellular automaton (CA) τ over A G is von Neumann regular (vN-regular) if there exists a CA σ over A G such that τ σ τ = τ, and in such case, σ is called a weak generalised inverse of τ. In this paper, we investigate the vN-regularity of various kinds of CA. First, we establish that, except for trivial cases, there are always CA that are not vN-regular. Second, we obtain a partial classification of elementary vN-regular CA over { 0, 1 } Z by taking advantage of some symmetries among them. Next, when A and G are both finite, we obtain a full characterisation of vN-regular CA over A G. Finally, we study vN-regular linear CA when A = V is a vector space over and characterise them in certain situations.

Details DOI

TCS Journal 2020 Journal Article

Expansive automata networks

Florian Bridoux
Maximilien Gadouleau
Guillaume Theyssier

An Automata Network is a map f: Q n → Q n where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its neighbors in the network's graph, called interaction graph. In this work we introduce the following property called expansivity: the observation of the sequence of states at any given node is sufficient to determine the initial configuration of the whole network. A major trend in automata network theory is to understand how the interaction graph affects dynamical properties of f. Our first result is a characterization of interaction graphs that allow expansivity. Moreover, we show that this property is generic among linear automata networks over such graphs with large enough alphabet. We show however that the situation is more complex when the alphabet is fixed independently of the size of the interaction graph: no alphabet is sufficient to obtain expansivity on all admissible graphs, and only non-linear solutions exist in some cases. Besides, we show striking differences between the linear and the general non-linear case, in particular we prove that deciding expansivity is PSPACE-complete in the general case, while it can be done in polynomial time in the linear case. Finally, we consider a stronger version of expansivity where we ask to determine the initial configuration from any large enough observation of the system. We show that it can be achieved for any number of nodes and naturally gives rise to maximum distance separable codes.

Details DOI

I&C Journal 2020 Journal Article

Fixing monotone Boolean networks asynchronously

Julio Aracena
Maximilien Gadouleau
Adrien Richard
Lilian Salinas

The asynchronous automaton associated with a Boolean network f: { 0, 1 } n → { 0, 1 } n is considered in many applications. It is the finite deterministic automaton with set of states { 0, 1 } n, alphabet { 1, …, n }, where the action of letter i on a state x consists in switching the ith component if f i ( x ) ≠ x i or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f. In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix monotone networks. We prove that there exists a monotone network f with n components such that any word fixing f has length Ω ( n 2 ). Conversely, we construct a word of length O ( n 3 ) that fixes all monotone networks with n components. Secondly, we refine and extend our results to different classes of networks.

Details DOI

I&C Journal 2019 Journal Article

Max-flow min-cut theorems on dispersion and entropy measures for communication networks

Søren Riis
Maximilien Gadouleau

The paper presents four distinct new ideas and results for communication networks: 1) We show that relay-networks (i. e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, akin to Kripke's possible worlds. Changes in the network are modelled by considering a multiverse where different possible situations arise as worlds existing in parallel. 2) We introduce the term model, which is a simple, graph-free symbolic approach to communication networks. This model yields an algorithm to calculate the capacity of a given communication network. 3) We state and prove variants of a theorem concerning the dispersion of information in single-receiver communications. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks. The proof uses a very weak kind of network coding, called routing with dynamic headers. 4) We show that the solvability of an abstract multi-user communication problem is equivalent to the solvability of a single-target communication in a suitable relay network. In the paper, we develop a number of technical ramifications of these ideas and results. We prove a max-flow min-cut theorem for the Rényi entropy with order less than one, given that the sources are equiprobably distributed; conversely, we show that the max-flow min-cut theorem fails for order greater than one. We also show that linear network coding fails for relay networks, although routing with dynamic headers is asymptotically sufficient to reach capacity.

Details DOI

TCS Journal 2016 Journal Article

Simple dynamics on graphs

Maximilien Gadouleau
Adrien Richard

Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f: A n → A n with G as interaction graph has a “complex” dynamics? If | A | ≥ 3 we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph G there exists a system f: A n → A n with G as interaction graph that converges toward a unique fixed point in at most ⌊ log 2 ⁡ n ⌋ + 2 steps. The boolean case | A | = 2 is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.

Details DOI

TCS Journal 2015 Journal Article

Memoryless computation: New results, constructions, and extensions

Maximilien Gadouleau
Søren Riis

In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs are only allowed to update one variable at a time. We first consider programs which do not use any memory. We study the maximum and average number of updates required to compute functions without memory. We then derive the exact number of instructions required to compute any manipulation of variables. This shows that combining variables, instead of simply moving them around, not only allows for memoryless programs, but also yields shorter programs. Second, we show that allowing programs to use memory is also incorporated in the memoryless computation framework. We then quantify the gains obtained by using memory: this leads to shorter programs and allows us to use only binary instructions, which is not sufficient in general when no memory is used.

Details DOI