Skip to main content

Research Repository

Advanced Search

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability

Gadouleau, Maximilien; Richard, Adrien; Fanchon, Eric

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability Thumbnail


Adrien Richard

Eric Fanchon


Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem to determining the number of fixed points of coding functions f : An ! An over a finite alphabet A (usually referred to as Boolean networks if A = f0; 1g) with a given interaction graph, that describes which local functions depend on which variables. In this paper, we generalise the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.


Gadouleau, M., Richard, A., & Fanchon, E. (2016). Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability. IEEE Transactions on Information Theory, 62(5), 2504-2519.

Journal Article Type Article
Acceptance Date Mar 5, 2016
Online Publication Date Mar 21, 2016
Publication Date May 1, 2016
Deposit Date Mar 17, 2016
Publicly Available Date Mar 18, 2016
Journal IEEE Transactions on Information Theory
Print ISSN 0018-9448
Publisher Institute of Electrical and Electronics Engineers
Peer Reviewed Peer Reviewed
Volume 62
Issue 5
Pages 2504-2519


Accepted Journal Article (379 Kb)

Copyright Statement
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

You might also like

Downloadable Citations