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

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear n...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2016-05, Vol.62 (5), p.2504-2519
Main Authors: Gadouleau, Maximilien, Richard, Adrien, Fanchon, Eric
Format: Article
Language:English
Subjects:
Automata
Channel coding
Computer Science
Context
Discrete Mathematics
Dynamical Systems
Entropy
Graph theory
Information Theory
Linear codes
Mathematical problems
Mathematics
Network coding
Routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward 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 into determining the number of fixed points of coding functions f : A n → A n over a finite alphabet A (usually referred to as Boolean networks if A = {0, 1}) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize 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 the 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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2016.2544344