1

Reduction and Fixed Points of Boolean

Networks and Linear Network Coding
Solvability
arXiv:1412.5310v1 [[Link]] 17 Dec 2014

Maximilien Gadouleau, Member, IEEE, Adrien Richard, and Eric Fanchon

Abstract
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 = {0, 1}) 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.

M.

Gadouleau

is

with

School

of

Engineering

and

Computing

Sciences,

Durham

University,

UK.

[Link]@[Link]
A. Richard is with Laboratoire I3S, CNRS & Universite de Nice-Sophia Antipolis, France. richard@[Link]
E. Fanchon is with Universite de Grenoble - CNRS, TIMC-IMAG UMR 5525, Grenoble, France. [Link]@[Link]
This work is partially supported by CNRS and The Royal Society through the International Exchanges Scheme grant Boolean
networks, network coding and memoryless computation.

December 18, 2014

DRAFT

I. I NTRODUCTION
A. Background: network coding solvability and coding functions
Network coding is a technique to transmit information through networks, which can significantly
improve upon routing in theory [1], [2]. At each intermediate node v , the received messages xu1 , . . . , xuk
are combined, and the combined message fv (xu1 , . . . , xuk ) is then forwarded towards its destinations.
The main problem is to determine which functions fv can transmit the most information. In particular,
the network coding solvability problem tries to determine whether a certain network situation, with a
given set of sources, destinations, and messages, is solvable, i.e. whether all messages can be transmitted
to their destinations. This problem being very difficult, different techniques have been used to tackle it,
including matroids [3], Shannon and non-Shannon inequalities for the entropy function [4], [5], errorcorrecting codes [6], and closure operators [7], [8]. As shown in [5], [9], the solvability problem can be
recast in terms of fixed points of (non-necessarily Boolean) networks.
Boolean networks have been used to represent a network of interacting entities as follows. A network
of n automata has a state x = (x1 , . . . , xn ) {0, 1}n , represented by a Boolean variable xi on each
automaton i, which evolves according to a deterministic function f = (f1 , . . . , fn ) : {0, 1}n {0, 1}n ,
where fi : {0, 1}n {0, 1} represents the update of the local state xi . Boolean networks have been used
to model gene networks [10], [11], [12], [13], neural networks [14], [15], [16], social interactions [17],
[18] and more (see [19], [20]). Their natural generalisation where each variable xi can take more than two
values in some finite alphabet A has been investigated since this can be a more accurate representation
of the phenomenon we are modelling [12], [21]. In order to avoid confusion, and despite the popularity
of the term Boolean network, we shall refer to any function f : An An as a coding function.
The structure of a coding function f : An An can be represented via its interaction graph G(f ),
which indicates which update functions depend on which variables. More formally, G(f ) has {1, . . . , n}
as vertex set and there is an arc from j to i if fi (x) depends essentially on xj . In different contexts,
the interaction graph is knownor at least well approximated, while the actual update functions are not.
One main problem of research on (non-necessarily Boolean) coding functions is then to predict their
dynamics according to their interaction graphs.
Among the many dynamical properties that can be studied, fixed points are crucial because they
represent stable states; for instance, in the context of gene networks, they correspond to stable patterns
of gene expression at the basis of particular biological processes. As such, they are arguably the property
which has been the most thoroughly studied. The study of the number of fixed points and its maximisation

December 18, 2014

DRAFT

in particular is the subject of a stream of work, e.g. in [22], [23], [24], [25], [26], [27], [28]. In particular,
a lot of literature is devoted to determining when a Boolean coding function admits multiple fixed points
(see [29] for a survey).
The network coding solvability problem can be recast in terms of fixed points of coding functions as
follows [5], [9]. The so-called guessing number [5] of a digraph G is the logarithm of the maximum
number of fixed points over all coding functions f whose interaction graph is a subgraph of G: G(f ) G.
The guessing number is always upper bounded by the size of a minimum feedback vertex set of G; if
equality holds, we say that G is solvable and the coding function f reaching this bound is called a
solution. Then, a network coding instance N is solvable if and only if some digraph GN (to be defined
later) related to the instance N is solvable.
Linear network coding is the most popular kind of network coding, where the intermediate nodes
can only perform linear combinations of the packets they receive [30]. The network coding instance N
is then linearly solvable if and only if GN admits a linear solution. Many interesting classes of linearly
solvable digraphs have been given in the literature (see [31], [6]). However, as we shall explain in Section
IV, all the linearly solvable undirected graphs G known so far are easily solved, because they are all
vertex-full: the vertex set can be partitioned into (G) cliques, where (G) is the independence number
of G [32].
B. Our approach and contribution
Fixed points of coding functions and network coding are very closely linked; for instance [28] uses
techniques from network coding and coding theory to derive bounds on the number of fixed points of
specific coding functions. As such, in this paper we will derive results of interest for both communities.
More precisely, we expand a new technique to study the number of fixed points of coding functions and
we apply it to the solvability problem. Recently, [33] introduced the reduction of coding functions in
order to reduce the number of interacting automata while preserving some key dynamical properties.
More precisely, for any loopless vertex v of G(f ) the v -reduction of f is obtained by evaluating fv
and then replacing its expression instead of xv into all the other local functions fi . The v -reduction
notably preserves the number of fixed points [33]. A very similar reduction procedure was proposed in
the context of systems of differential equations [34]; this procedure is also based on variable elimination
and preserves the number of fixed points.
In this paper, we generalise the concept of reduction of a coding function by a vertex in two fashions.
We consider successive reductions vertex per vertex, and we prove in Theorem 1 that this is equivalent
December 18, 2014

DRAFT

to reducing all these vertices at once, provided that they induce an acyclic subgraph of the interaction
graph. Since the reduction of a coding function has the same number of fixed points as the original
coding function, we can then study the number of fixed points of fully reduced coding functions. We
also introduce the concept of reduction of digraphs; again this can be done one vertex at a time or all at
once, according to Theorem 2. The interaction graph of a reduced coding function is then a subgraph of the
reduction of its interaction graph. In particular, reducing an entire maximal acyclic set of a digraph yields
a digraph with a loop on each vertex. Similarly, we can always successively reduce a coding function to
one whose interaction graph has a loop on each vertex. We then fully determine the maximum number of
fixed points of coding functions for a given interaction graph with a loop on each vertex in Theorem 3.
We then apply this reduction approach to network coding solvability and derive four main results.
1) We consider solvability by non-decreasing coding functions, which naturally extend routing. We
show in Theorem 4 that a digraph is solvable by a non-decreasing coding function if and only if
it is solvable by routing.
2) We derive some important classification results for undirected graphs. We exhibit in Theorem 5
the first example of a non-vertex-full linearly solvable graph. We obtain in Theorem 6 a necessary
condition for a graph G to be strictly linearly solvable, i.e. to have a linear solution f with G(f ) =
G. Using this condition, we then prove in Theorem 7 that a triangle-free undirected graph is linearly

solvable if and only if it is vertex-full; we also prove that all strictly linearly solvable complements
of triangle-free graphs are vertex-full in Theorem 8. For triangle-free graphs, our results indicate
that the instance is linearly solvable if and only if it is solvable by routing; in other words, linear
network coding does not help to solve these graphs.
3) Using Theorem 6, we exhibit in Theorem 9 a new class of digraphs which are not linearly solvable.
This is significant because few non-linearly solvable classes of digraphs are known so far, and
proving non-linear solvability usually requires different techniques, such as graph entropy [31],
[32] or digraph closure [8].
4) We show in Theorem 10 that a large class of digraphs are strictly linearly solvable. Strictly
linearly solvable digraphs are not only interesting for some applications of coding functions (see
Section IV-E), but they also represent network coding instances where no arc is detrimental to the
transmission of information.
The rest of the paper is organised as follows. Section II studies the reduction of coding functions and
the reduction of graphs and relates these two notions. Reductions of coding functions are then related to

December 18, 2014

DRAFT

their fixed points in Section III. Finally, we apply the theory of coding function and graph reductions to
the problem of linear network coding solvability in Section IV.
II. R EDUCTION

OF CODING FUNCTIONS

A. Definitions
We first review some concepts relating to coding functions. Let V be a finite set, possibly empty, of
cardinality n. Let A be a finite set, referred to as the alphabet, of cardinality q 2; depending on the
context, we will consider A = GF(q) or A = Zq or A = [q] := {0, . . . , q 1}. Let f : AV AV be
a coding function of dimension

DIM (f )

= n. We shall usually simplify notation and identify AV with

An . We can then view f : An An as f = (f1 , . . . , fn ) where fv : An A. For any x An and any

I V , we also denote xV \I as xI ; we will usually identify a vertex v with its corresponding singleton
{v}.

A digraph with vertex set V is a pair G = (V, E) where E V 2 ; we set

DIM (G)

= |V | = n. If E

is a symmetric set, we say that G is undirected (i.e. we identify undirected and bidirected graphs). We
associate with f the digraph G(f ), referred to as the interaction graph of f , defined by: the vertex set
is V ; and for all u, v V , there exists an arc (u, v) if and only if fv depends essentially on xu , i.e. there
exist x, y An that only differ by xu 6= yu such that fv (x) 6= fv (y). We denote the set of all coding
functions f : An An for some A of size q with interaction graph G as F (G, q).
We now review some basic concepts and introduce some notation for digraphs G = (V, E) [35]. An
induced subgraph of G is obtained by removing vertices of G; a spanning subgraph of G is obtained by
removing arcs. If I V , we denote by G[I] the subgraph of G induced by I , and we set G\I = G[V \I].
If G[I] has no cycle, then we say that I is an acyclic set. An acyclic set I = {i1 , . . . , im } can be sorted
in topological order, where (ik , il ) G only if k < l. Thus if I is an acyclic set of G(f ), then fik
does not depend on the variables il with l > k and we can write fik (x) = fik (xI , xi1 , . . . , xik1 ). The
complement of an acyclic set is a feedback vertex set. We denote the size of a minimum feedback vertex
set of G as k(G) and the size of a maximum acyclic set of G as (G); we then have (G) = n k(G).
The in-neighbourhood of a vertex i in G is denoted as inG (i) := {u V : (u, i) G}; its indegree is indG (i) = |inG (i)|; when there is no ambiguity, we shall remove the dependence in G. The
out-neighbourhood and out-degree are defined similarly. Paths and cycles are always supposed to be
directed. If s = (s1 , . . . , sk ) is a sequence of distinct vertices of G, then {s} = {s1 , . . . , sk } denotes the
support of s.

December 18, 2014

DRAFT

Definition 1 ([33]). For any v V without a loop in G(f ), the v -reduction of f is the coding function
f v : AV \v AV \v , where for all i 6= v and x AV
fiv (xv ) := fi (xv , fv (xv )).

If G(f ) has a loop on v then f v = f by convention.

Thus

DIM (f v )

= DIM (f ) 1 if and only if G(f ) has no loop on v . Let s = (s1 , s2 , . . . , sk ) be a

sequence of distinct vertices of V of length |s| = k > 0. We write

f s = f s1 s2 ...sk = (f s1 )s2 )... )sk .

The sequence s is a reduction sequence of f if: G(f ) has no loop on s1 , and G(f s1 ...sr1 ) has no
loop on sr for each 1 < r k. So s is a reduction sequence if and only if
DIM (f

) = DIM (f ) |s|.

By convention the empty sequence is a reduction sequence, and f = f .

Definition 2. Let I = {i1 , . . . , im } be an acyclic set of G(f ) in topological order. We denote the
cumulative f -coding function on I as F I : AV \I AI defined as
FiI1 (xI ) := fi1 (xI )
FiI2 (xI ) := fi2 (xI , FiI1 (xI ))

..
.
I
FiIm (xI ) := fim (xI , FI\i
(xI )).
m

The I -reduction of f : AV AV is defined as the coding function f I : AV \I AV \I such that

fiI (xI ) := fi (xI , F I (xI )).

Theorem 1. If I is an acyclic set of G(f ), then any enumeration s of I is a reduction sequence of f

such that f s = f I .
Proof: We prove that if there is no arc from v to u and no loop on either vertex, then f uv = f vu .
By direct application of the reduction rule, we have for all i
/ {u, v},
fiuv (xuv ) = fiu (xuv , fvu (xuv ))
= fi (xuv , fvu (xuv ), fu (xuv , fvu (xuv )))
= fi (xuv , fv (xuv , fu (xuv )), fu (xuv , fvu (xuv )))
December 18, 2014

DRAFT

and since there is no arc from v to u we get

fiuv (xuv ) = fi (xuv , fv (xuv , fu (xuv )), fu (xuv )).

Again by direct application of the reduction rule, we have for all i

/ {u, v},
fivu (xuv ) = fiv (xuv , fuv (xuv ))
= fi (xuv , fuv (xuv ), fv (xuv , fuv (xuv )))

and since there is no arc from v to u we have fuv (xuv ) = fu (xuv ) thus
fivu (xuv ) = fi (xuv , fu (xuv ), fv (xuv , fu (xuv ))).

Thus fiuv = fivu and the claim is proved.

Let I = {i1 , . . . , im } in topological order and let s and t be enumerations of I . Firstly, suppose that
s and t only differ by a transposition of adjacent vertices, say s = (s1 , . . . , sm ) and t = (s1 , . . . , sk2 ,
sk , sk1 , sk+1 , . . . , sm ). We then have
f s1 ...sk = hsk1 sk = hsk sk1 = f t1 ...tk ,

where h = f s1 ...sk2 , and hence f s = f t. Secondly, in the general case, it is well known that t can
be obtained from s by transposing adjacent vertices: indeed the Coxeter generators of I generate the
symmetric group on I . Thus f s = f t ; in particular, if s is a topological order of I , then we obtain
f I described above.

Corollary 1. If s and t are two reduction sequences of f with the same acyclic support then f s = f t .
A coding function h is a reduced form of f if there exists a reduction sequence s such that f s = h.
A minimal reduced form of f is a reduced form h such that every vertex of G(h) has a loop. The set
of reduced forms of f is denoted

RED (f ).

We are particularly interested in finding, according to G(f ),

reduced forms of dimension as small as possible. In the ideal case, we would like to obtain reduced
forms of dimension
MINDIM (f )

:=

min DIM (h).

hRED(f )

B. Graph reduction
Definition 3. If G has no loop on v , we call v -reduction of G, and we denote by Gv , the graph
obtained from G \ v by adding an arc (u, w) (not already present) whenever (u, v) and (v, w) are arcs
of G. By convention, if G has a loop on v , then Gv = G.
December 18, 2014

DRAFT

We shall use similar notation to that of the reduction of coding functions. A sequence s = (s1 , . . . , sk )
of vertices of G is a reduction sequence of G if: G has no loop on s1 , and Gs1 ...sr1 has no loop on
sr for each 1 < r k. So s is a reduction sequence if and only if Gs has |V | k vertices.

Definition 4. For any acyclic set I of G, the I -reduction of G is the digraph GI := (V \ I, E ), where
(u, w) E if and only if either (u, w) E or there is a path in G from u to w through I (that is, a

path from u to w whose internal vertices are all in I ).

Theorem 2. If I is an acyclic set of G, then any enumeration s of I is a reduction sequence of G such
that Gs = GI .
Proof: The structure of the proof is similar to that of Theorem 1. We first prove that if u, v V
induce an acyclic subgraph, then Guv = Gvu . Say that there is no arc from v to u and that there is
no loop on either u or v . Let us simplify notation and denote the proposition (x, y) G as xy and the
proposition (x, y) Gz as xy z for any vertices x, y , and z . Then for any a, b
/ {u, v},
abu ab (au ub) ,
(a, b) Guv abu av u vbu

ab (au ub) {[av (au uv)] vb}

ab (au ub) (av vb) (au uv vb) .

Similarly,
abv ab (av vb) ,
(a, b) Gvu abv auv ubv

ab (av vb) {au [ub (uv vb)]}

ab (av vb) (au ub) (au uv vb) .

Now let I = {i1 , . . . , im } in topological order and let s and t be enumerations of I . Firstly, suppose that
s and t only differ by a transposition of adjacent vertices, say s = (s1 , . . . , sm ) and t = (s1 , . . . , sk2 ,
sk , sk1 , sk+1 , . . . , sm ). We then have
Gs1 ...sk = H sk1 sk = H sk sk1 = Gt1 ...tk ,

where H = Gs1 ...sk2 , and hence Gs = Gt . Secondly, in the general case, it is well known that t
can be obtained from s by transposing adjacent vertices: indeed the Coxeter generators of I generate the
December 18, 2014

DRAFT

symmetric group on I ; thus Gs = Gt .

In particular, we prove that if s is the topological order, then we obtain GI described above. The
proof is by induction on |I|. For |I| = 1, the result is obvious. Suppose the result holds for all induced
acyclic subgraphs of size m 1. Let s = i1 , . . . , im be a topological order of I . By definition, we
have (u, v) Gs if and only if (u, v) Gi1 ,...,im1 or (u, im ), (im , v) Gi1 ,...,im1 . Thus, by
induction hypothesis, (u, v) Gs if and only if (u, v) G(I\im ) or (u, im ), (im , v) G(I\im ) . This
is equivalent to

either, (u, v) G;

or G has a path from u to v through I \ im ;

or (u, im ), (im , v) G;

or G has a path from u to im through I \ im and (im , v) G;

or (u, im ) G and G has a path from im to v through I \ im (impossible, since out(im ) I = );

or G has a path from u to im through I \im and a path from im to v through I \im (also impossible).

This is clearly equivalent to either (u, v) G or there is a path in G from u to v through I . Thus
(u, v) Gs if and only if (u, v) GI .

We make three remarks on the reduction of digraphs.

1) If s and t are two reduction sequences of G with the same acyclic support then Gs = Gt .
2) GI has a loop on each vertex if and only if I is a maximal acyclic set. Therefore, there is a
bijection between the set of minimal reduced forms of G and the set of its minimal feedback
vertex sets. Since it is well known that finding a minimum feedback vertex set is an NP-Complete
problem, finding a minimum reduced form is also NP-Complete.
3) For any G and any acyclic set I , we have G \ I GI . We prove below a converse to this result:
depending on the initial digraph G, the reduced form GI of G may add any possible arc to G \ I .
Proposition 1. For any digraph D with vertex set J and any spanning subgraph H of D , there exists a
set I and a digraph G with vertex set I J such that G \ I = G[J] = H and GI = D .
Proof: Let I be the set of arcs in D but not in H and let G be the graph on I J such that G[J] = H
and for any arc e = (u, v) I , G contains the arcs (u, e) and (e, v). Then it is clear that GI = D .
C. Interaction graph of the reduced coding function
The reduction of digraphs yields an estimate on the interaction graph of the reduction of coding
functions.
December 18, 2014

DRAFT

10

Proposition 2. If I is an acyclic set of G(f ) then G(f I ) is a subgraph of G(f )I .

Proof: We only prove that if G(f ) has no loop on v , then G(f v ) is a subgraph of G(f )v ; the
result is an easy consequence. We have
fwv (x) = fw (xv , fv (xv )),

hence (u, w) is an arc in G(f v ) only if either (u, w) is already in G(f ) or (u, v), (v, w) G(f ), i.e.
(u, w) G(f )v .

Corollary 2. Every reduction sequence of G(f ) is a reduction sequence of f .

According to Proposition 2, we have

MINDIM (f )

k(G(f )). We show that this bound on MINDIM (f )

is the best possible as a function of G(f ). The min-net of a digraph G over [q] = {0, . . . , q 1} (q 2)
is the coding function f := min(G, q) defined as
fi (x) := min{xj : j inG (i)}

with the convention that min() = q 1.

Proposition 3. For any digraph G and any acyclic set I of G, min(G, q)I = min(GI , q). Therefore,
MINDIM (min(G, q))

= k(G).

Proof: Again, we only prove the case where I is only one vertex v . If f = min(G, q), we have for
all i 6= v
fiv (x) = min{xj : j inG (i) \ v, min{xk : k inG (v)}} = min{xk : k inGv (i)}.

Thus min(G, q)v = min(Gv , q).

Note that according to the preceding, finding a minimum reduced form of a min-net is equivalent to
finding a minimum vertex set in a digraph. So finding a minimum form of a coding function is NP-Hard.
Although there exists a coding function (the min-net) whose reductions follow the reductions of its
interaction graph, we prove in the following two propositions that in general we cannot say much about
the interaction graph of the reduced coding function. First, we derive the analogue of Proposition 1 for
the interaction graphs of coding functions.
Proposition 4. Let D and H be any digraphs with vertex set J . Then for any q 2 there exists a set I
and a coding function f : AIJ AIJ such that G(f )[J] = D and G(f )I = H .

December 18, 2014

DRAFT

11

Proof: Let I = ID IH , where ID is the set of all arcs in D but not in H and IH is the set of
all arcs in H but not in D . Then let G be the graph with vertex set I J such that G[J] = D and for
any (u, v) I , (u, (u, v)), ((u, v), v) G. For any (u, v) ID and any x [q]n (with n = |I J|), we
denote
y(u,v) = xu + q 1 x(u,v)

and for any j J , y j as the state with coordinates y(u,j) for all u inD (j) \ inH (j).
Finally, let f : [q]n [q]n be defined as
fj (xinD (j)\inH (j) , xID , xinD (j)inH (j) , xIH ) = min(y j , xinD (j)inH (j) , xIH inG (j) )

for all j J and

f(u,v) (x) = xu

for all (u, v) I . It is clear that f F (G, q), hence G(f )[J] = D . Moreover, reducing ID yields
fjID (xinD (j) , xIH ) = min(q 1, . . . , q 1, xinD (j)inH (j) , xIH inG (j) ) = min(xinD (j)inH (j) , xIH inG (j) ),

and then reducing IH yields

fjI (xJ ) = min(xinD (j)inH (j) , xinH (j)\inD (j) ) = min(xinH (j) ),

thus G(f I ) = H .
Second, we prove that even reducing a single vertex may in fact remove any set of arcs from the
original interaction graph.
Proposition 5. Let G be a digraph with a vertex v such that in(v) = out(v) = V \ v , and let G have
minimum in-degree at least 2. Then for any q 2 and any spanning subgraph H of G \ v , there exists
a coding function f F (G, q) such that G(f ) = G and G(f v ) = H .
Proof: Say v = n and for all i, let yi = min{xi , 1} {0, 1}. We define the function for the vertex
n:
fn (x) =

n1
_

yi .

i=1

That way, we can focus on each vertex of H separately; without loss we only consider the vertex 1. Let

December 18, 2014

DRAFT

12

N = inG (1) \ n, P = inH (1) and Q = N \ P ; then

^
_
f1 (x) =
y p y n
yq ,
pP

f1n (x) =

pP

qQ

yp

n1
_

yi

i=1

qQ

yq =

yp ,

pP

with the convention that an empty conjunction is equal to 1 and an empty disjunction is equal to 0.
We finish this section with an example illustrating the reduction of graphs and coding functions.
Example 1. Consider the following coding function f : {0, 1}4 {0, 1}4 given by
f1 (x) = x3 (x2 x4 )
f2 (x) = x1 x4
f3 (x) = x2
f4 (x) = x3 .

Then f 4 is given by:

f14 (x4 ) = x3 (x2 x3 ) = x3
f24 (x4 ) = x1 x3
f34 (x4 ) = x2 .

Thus G(f 4 ) is a strict subgraph of G(f )4 , as seen on Figure 1. However, f 34 = f 43 is given by

f134 (x1 , x2 ) = x2
f234 (x1 , x2 ) = x1 x2 ,

and hence G(f 34 ) = G(f )34 . Finally, f 134 = f 431 is given by

f2134 (x2 ) = x2 x2 = x2

and G(f 134 ) only has one vertex with a loop.

December 18, 2014

DRAFT

13

(a) G(f )

2
(b) G(f 4 )

2
(c) G(f )4

(d)

G(f 34 )

G(f )

34

Fig. 1: Example of coding function and graph reduction.

III. F IXED

POINTS OF CODING FUNCTIONS

A. Maximum number of fixed points

The q -guessing number [5] and q -strict guessing number of G are respectively defined as
g(G, q) := logq max{|Fix(f )| : f F (G , q), G G},
h(G, q) := logq max{|Fix(f )| : f F (G, q)}.

The guessing number of loopless digraphs was thoroughly investigated in [5], [36], [6], [32], [37], [38];
the strict guessing number is new. We first relate h(G, q) to g(G, q).
Lemma 1. If g(G, q) 1, then h(G, q) 1.
Proof: If g(G, q) 1, then G has a cycle. Say that the vertices 0 up to l 1 form a chordless cycle
and consider the coding function f F (G, q) defined by

xi1 mod l
if xj xi1
fi (x) =

xi1 mod l + 1 otherwise

mod l

for all j in(i)

if 0 i l 1 and

fj (x) = min{xk : k in(j)}

otherwise. Then it is clear that if G is of minimal in-degree at least one then for any a [q], (a, . . . , a)
is fixed by f . Thus h(G, q) logq |Fix(f )| 1. Otherwise, let I0 be the set of vertices of in-degree 0,
and for 0 < k < n, let Ik be the set of vertices i such that in(i) I0 Ik1. Then, for any a [q],
the point xa [q]n such that xai = q 1 if i Ik for some k and xai = a otherwise is a fixed point of
f , thus h(G, q) logq |Fix(f )| 1.
December 18, 2014

DRAFT

14

Proposition 6. For all q 2 and any digraph G,


g(G, q) h(G, q) g(G, q 1) logq (q 1) g(G, q) n logq 1 +

1
q1

Proof: The first inequality is trivial. We now prove the second. Let f : [q 1]n [q 1]n with
interaction graph G G and with (q 1)g(G,q1) fixed points. Let f F (G, q) such that

fv (x) if xin(v) [q 1]ind(v)

fv (x) =

q
otherwise.

Then Fix(f ) Fix(f ) and hence (q 1)g(G,q1) = |Fix(f )| |Fix(f )| q h(G,q) .

Let us now prove the third inequality. Let f : [q]n [q]n with interaction graph G G and with
q g(G,q) fixed points. Then for any vertex v and any permutation of [q], consider the coding function
f v, defined as
fuv, (x) =

(fv ( 1 (xv ), xv ))

fu ( 1 (xv ), xv )

if u = v
otherwise.

Then x Fix(f ) if and only if ((xv ), xv ) Fix(f v, ) and hence |Fix(f v, )| = q g(G,q) . Denote
R(v, a) := |{x Fix(f ) : xv = a}| = |{x Fix(f v, ) : xv = (a)}|,
r(v) := min R(v, a) q 1 q G(G,q) .
a[q]

Consider a permutation of [q] such that r(v) = R(v, 1 (q 1)); we then obtain
|{x Fix(f v, ) : xv [q 1]}| = |{x Fix(f ) : xv 1 ([q 1])}|
X
=
R(v, a)
a6=1 (q1)

= |Fix(f )| R(v, 1 (q 1))

(1 q 1 )q g(G,q) .

Thus, f v, has at least (1 q 1 )q G(G,q) fixed points with xv [q 1]. Applying this strategy recursively
for all n vertices, we find that there exists a coding function with at least (1 q 1 )n q g(G,q) fixed points
in [q 1]n . By considering the restriction of this coding function to [q 1]n , we obtain (q 1)g(G,q1)
(1 q 1 )n q g(G,q) .

Corollary 3. We have limq h(G, q) = limq g(G, q) = H(G) for all G, where H(G) is the entropy
of G [31].

December 18, 2014

DRAFT

15

B. Fixed points and reduction

Proposition 7 (See [33]). Let f be a coding function and h be a reduced form of f . With the convention
that f has a unique fixed point if

DIM (f )

= 0, f and h have the same number of fixed points.

Proof: Again, we can assume that h = f v for some vertex v without a loop in G(f ). We then
have fi (x) = xi for all i if and only if fv (x) = xv and fiv (x) = fi (xv , fv (x)) = fi (x) = xi for all
i 6= v .

Example 2. Let f be the coding function in Example 1. The fixed points of f and its successive reductions
are respectively given by
Fix(f ) = {(0, 0, 0, 0), (1, 1, 1, 1)},
Fix(f 4 ) = {(0, 0, 0), (1, 1, 1)},
Fix(f 34 ) = {(0, 0), (1, 1)},
Fix(f 134 ) = {0, 1},

and successive reductions preserve the number of fixed points. In particular, since k(G(f )) = 1 and
f 134 is the identity of Ak(G(f )) , Proposition 7 indicates that f is indeed a solution for G(f ).

Let S = V \ I be a feedback vertex set of G(f ). Then according to Proposition 2, f has a reduced
form f I with dimension |S|. So f I has obviously at most q |S| fixed points, and since f and f I have
the same number of fixed points, f has at most q |S| fixed points. This provides an alternative proof of
(a modified form of) a theorem of Aracena [25] (see Riis [31]): If S is a feedback vertex set of G(f ),
then f has at most q |S| fixed points. In other words, h(G, q) k(G); by obvious extension, we obtain
g(G, q) k(G) as well.

In particular, if G(f ) has no cycle, then f has a reduced form f V of dimension zero. Then f V has
a unique fixed point and we deduce that f has a unique fixed point. This provides an alternative proof
of a theorem of Robert [39]: If G(f ) is acyclic, then f has a unique fixed point.
As seen below, we cannot say anything interesting about the guessing number of reduced digraphs in
general.
Proposition 8. The guessing number of G and that of its reduction Gv are related as follows.
1) Let G be a digraph and v a vertex of G, then g(G, q) g(Gv , q) for all q 2.
2) If G is acyclic, then h(G, q) = g(G, q) = g(Gv , q) = h(Gv , q) = 0.
December 18, 2014

DRAFT

16

3) For any n 3 there exists G on n vertices such that g(G, q) = h(G, q) = 1, h(Gv , q) =
logq (q n1 1) and g(Gv , q) = n 1 for all q .

Proof: The first two statements are clear. Now consider the complete bipartite graph G = Kn1,1 ,
also called the star on n vertices, where n is the centre of the star. Then this vertex forms a feedback
vertex set and hence g(G, q) = 1, and by Lemma 1, h(G, q) = 1. Then Gn is the complete graph on
n 1 vertices with a loop on each vertex, and we have g(Gn , q) and h(Gn , q) from Theorem 3 and

Example 3 below.
C. Fixed points of fully reduced coding functions
We are then interested in studying the number of fixed points of coding functions which are fully
reduced, i.e. whose interaction graphs have a loop on each vertex. For any loopless digraph G, we denote
. Clearly, g(G,
q) = n; moreover,
the graph obtained from G by adding a loop on each vertex as G
q) = n if and only if G is empty (this is the interaction graph of the identity function).
h(G,

For any loopless G, an in-dominating set (IDS) is a set of vertices X V such that for all v V
with positive in-degree, either v X or in(v) X 6= . Denote the number of IDSs of G of size k as
Ik (G); clearly, In (G) = 1.

Theorem 3. For any loopless graph G,

q) = logq
h(G,

n
X

(q 1)k Ik (G).

k=0

Proof: For any property P , we denote the function which returns 1 if P is satisfied and 0 otherwise
as 1{P}. Also, we write in(i) and out(i) for inG
(i) and outG
(i) so that i in(i) out(i). We define
q) as
the coding function g F (G,

xi
gi (x) :=

xi + 1{x
in(i) = (0, . . . , 0)}

if ind(i) = 1
mod q

otherwise.

For any x, x = g(x) if and only if {v V : xv 6= 0} is an in-dominating set. This proves the lower
bound.

and q h(G,q) fixed points. Any local function of f is expressed as

Now let f with G(f ) = G

a(xi )
if ind(i) = 1
fi (x) =

xi + ei (x
in(i) ) mod q otherwise,
December 18, 2014

DRAFT

17

where ei (xin(i) ) = fi (x) xi mod q . It is clear that the optimal choice for the function a is simply
a(xi ) = xi . Therefore, we only focus on the case where ind(i) 2 henceforth.

We now show that we can always assume that ei takes a non-zero only once. Let Y = {y Aind(i) :
ei (y) 6= 0} and let y i Y . Now, let f such that fj = fj for all j 6= i and
fi (x) = xi + 1{xin(i) = y i } mod q.

Suppose f (x) = x, then fj (x) = fj (x) = xj for all j 6= i; moreover, xin(i)

/ Y hence xin(i) 6= y i and
fi (x) = fi (x) = xi . Therefore, |Fix(f )| |Fix(f )|.

Hence we can consider f instead. We now show that choosing y i = (0, . . . , 0) for any vertex i
maximises the number of fixed points. Consider a vertex k and define a new function f as
fj = fj

j
/ out(k),

fi (x) = xi + 1{xin(i) = z i } mod q

i out(k),

where zji = yji if j 6= k and zki = 0. Let x Fix(f ) \ Fix(f ). Then there exists i out(k)
such that z i = xin(i) 6= y i . Defining x by only changing the k-coordinate of x to xk := yki we obtain
z i 6= xin(i) = y i and z j 6= xin(j) for all j out(k)\i (because xk > 0 = zkj ). Thus x Fix(f )\Fix(f ).

Hence, there is an injection from Fix(f ) \ Fix(f ) to Fix(f ) \ Fix(f ), thus f has at least as many
fixed points as f .
Thus, we can always choose zki = 0 for all i and all k, which yields the coding function g.
Corollary 4. For any loopless G, we have


h(G, q) n logq (q 1) + logq 1 +

n
q1

q) = n.
and hence limq h(G,

Proof: For any v V , V \ v is an IDS. Therefore, In1 (G) = n and since V is also an IDS,


q) logq n(q 1)n1 + (q 1)n .
In (G) = 1. Therefore, h(G,
Example 3. In general, computing the sum

k
k (q 1) Ik (G)

is #P-Complete. However, we can exhibit

five special cases for which the formula is easy to derive; all graphs have vertex set V = {1, . . . , n}.

For the clique Kn (with arcs (i, j) for all i 6= j ),

n , q) = logq (q n 1).
h(K

December 18, 2014

DRAFT

18

For the transitive tournament Tn (with arcs (i, j) for all i < j ),
1 , q) = 1 and
h(T

n , q) = n 2 + logq (q 2 1) n 2.
h(T

For the inward directed star iSn (with arcs (i, n) for all 1 i n 1),
n , q) = logq (q n 1).
h(iS

For the outward directed star oSn (with arcs (n, i) for all 1 i n 1),
n , q) = logq (q n q n1 + (q 1)n1 ).
h(oS

For the undirected star (with arcs (i, n) and (n, i) for all 1 i n 1),
n , q) = logq (q n q n1 + (q 1)n1 ).
h(S

Proof: For Kn , we have I0 (Kn ) = 0 and Ik (Kn ) =

n

k

for all 1 k n. Therefore,

k (q

1)k Ik (Kn ) = q n 1. For Tn (n 2), a set of vertices X is an in-dominating set if and only if it contains




P
and k (q 1)k Ik (Tn ) = q n q n2 .
either the first or the second vertex. Therefore, Ik (Tn ) = nk n2
k


The proof for the stars is similar: we have I0 (iSn ) = 0 and Ik (iSn ) = nk for all 1 k n; we also


have In1 (Sn ) = In1 (oSn ) = n and Ik (Sn ) = Ik (oSn ) = n1
k1 otherwise.

IV. A PPLICATION

TO LINEAR NETWORK CODING SOLVABILITY

A. Network coding solvability and guessing number

We now apply the theory of coding function reduction to linear network coding solvability. The network
coding solvability problem asks whether a given network coding instance is solvable, i.e. whether all
messages can be transmitted to their destinations simultaneously. In particular, if the local functions fv
are linear, then the instance is linearly solvable. For the study of solvability, any network coding instance
can be converted into a multiple unicast without any loss of generality [40], [5]. A multiple unicast
instance consists of an acyclic network N and a finite alphabet A of cardinality q , where

each arc in the network carries an element of A;

the instance is given in its so-called circuit representation, i.e. the same message flows on every arc
coming out of the same vertex;

the network has k sources s1 , . . . , sk , k destinations d1 , . . . , dk , and intermediate nodes ik+1 , . . . , ik+ ;

each destination di (1 i k) requests an element from A from a corresponding source si .

This network coding instance is solvable over A if all the demands of the destinations can be satisfied
at the same time.
December 18, 2014

DRAFT

19

s1

s2

sends x1
x1

x1

sends x2

x2

i3

f1 = x2 x3

f2 = x1 x3

x2

x3 = x1 x2

3
d2

wants x2
x1 x3 = x2

d1

wants x1
x2 x3 = x1

(a) Butterfly Network coding instance

f3 = x1 x2
(b) Corresponding graph K3

Fig. 2: The butterfly network.

The solvability of a multiple unicast instance can be decided by determining the guessing number
of a related digraph. By merging each source with its corresponding destination node into one vertex,
we form the digraph GN on n := k + vertices. In general, we have g(GN , q) k for all q and the
original network coding instance is solvable over A if and only if k(GN ) = k (this condition is purely
graph-theoretic and does not involve coding functions; as such, we assume it is always satisfied) and
g(GN , q) = k, in which case we say that GN is solvable over A [5] (an analogous result holds for

linear solvability). Therefore, while network coding considers how the information flows from sources
to destinations, the guessing number captures the intuitive notion of how much information circulates
through the digraph.
We illustrate the conversion of a network coding instance to a guessing number problem for the
famous butterfly network in Figure 2 below. It is well-known that the butterfly network is solvable over
all alphabets, and conversely the clique K3 has guessing number 2 over any alphabet. The solutions are
shown in Figure 2 and indeed the operations done in the butterfly network correspond to the fixed point
equations on the clique.
B. Solvability by non-decreasing coding functions
We first apply the reduction approach to network coding solvability by non-decreasing coding functions.
Here, we consider A = [q] = {0, . . . , q 1} with the usual linear order. We then say that a local function
December 18, 2014

DRAFT

20

fv is non-decreasing if it is non-decreasing in every variable xu ; the coding function is non-decreasing

if all its local functions are non-decreasing. For instance, the min-net introduced in Section II-C is a
non-decreasing coding function. Non-decreasing coding functions have been widely studied (see [25],
[29], [28]); they are usually represented by an interaction graph with positive signs on all arcs (see [29]
and the references therein for a survey of the work on signed interaction graphs).
More closely related to network coding, routing can be viewed as a non-decreasing coding function.
Indeed, routing corresponds to local functions of the form fv (xu ) for some u in(v). Routing then
achieves a guessing number of c(G), where c is the maximum number of disjoint cycles in G; thus a
graph is solvable by routing if and only if c(G) = k(G). It is shown in [28] that general non-decreasing
coding functions can significantly outperform routing in terms of guessing number: for instance, on
the clique Kn , routing achieves a guessing number of c(Kn ) = n/2, while non-decreasing functions
achieve n 3 when the alphabet is large enough [28, Proposition 6]. However, Theorem 4 below
proves that non-decreasing functions do not outperform routing in terms of solvability.
Theorem 4. For any digraph G, the following are equivalent:
1) G is solvable by a non-decreasing coding function over some alphabet.
2) G is solvable by a non-decreasing coding function over any alphabet.
3) G is solvable by routing.
4) c(G) = k(G).
Proof: We only have to prove that the first property implies the fourth one. Let f : [q]n [q]n be
a non-decreasing coding function with G(f ) G and q k(G) fixed points. Let I be a maximal acyclic
set of G such that |V \ I| = k(G). Since f I and f have the same number of fixed points, f I is the
identity on [q]V \I .
For every vertex v
/ I , let ev [q]V \I be the v -th unit vector defined by (ev )v = 1 and (ev )u = 0 for
all u 6= v ; we set ev = 1 ev . Consider
Cv := {v} {i I : FiI (ev ) > FiI (ev )}.

Claim. For all distinct u, v

/ I , Cu Cv = .
Proof: For any i I , FiI is a non-decreasing function of xI . Since eu ev , we obtain for any
i Cu Cv :
FiI (eu ) > FiI (eu ) FiI (ev ) > FiI (ev );

December 18, 2014

DRAFT

21

yet ev eu implies FiI (ev ) FiI (eu ), which is the desired contradiction.
Claim. For all v
/ I , Cv contains a cycle.
Proof: We only need to show that for all i Cv , Cv in(i) 6= . Firstly, let i Cv \ {v}, and
I
I
suppose that Cv in(i) = , then Fin(i)I
(ev ) Fin(i)I
(ev ) and (ev )v (ev )v . Hence




I
I
(ev ) = FiI (ev ),
(ev ) fi (ev )v , Fin(i)I
FiI (ev ) = fi (ev )v , Fin(i)I

which contradicts the fact that i Cv . Secondly, let i = v , and again suppose that Cv in(v) = ; thus
I
I
Fin(v)I
(ev ) Fin(v)I
(ev ). Recall that f I is the identity, hence




I
I
I
I
I
(e
(e
)
,
F
(e
)
= fvI (ev ) = 1.
0 = fv (ev ) = fv
v v
v )v , Fin(v)I (ev ) fv
in(v)I v

By the claims above, we have n |I| = k(G) disjoint cycles in the graph G.
C. Linearly solvable undirected graphs
We are now interested in linear coding functions. A linear coding function is any coding function
P
f : RV RV , where R is a commutative ring of order q and such that fi (x) = uin(i) ai,u xu for

some ai,u invertible in R. For any G we denote the set of linear coding functions with interaction graph
G over a commutative ring of order q as L(G, q). The set of fixed points of a linear coding function

forms a submodule of RV , hence we denote the q -linear guessing number [5], [6], [41] and q -strict
linear guessing number of G respectively as
gL (G, q) = max{dim Fix(f ) : f L(G , q), G G},
hL (G, q) = max{dim Fix(f ) : f L(G, q)}.

We say that a digraph G is linearly solvable if gL (G, q) = g(G, q) = k(G) for some q . We say it is
strictly linearly solvable if hL (G, q) = h(G, q) = k(G). It is easy to prove that G is linearly solvable
if and only if G has a strictly linearly solvable spanning subgraph H with k(G) = k(H).
The minimum number of parts in any partition of the vertex set of G into cliques is denoted as cp(G);
, the chromatic number of its complement. We say that a digraph
if G is undirected, then cp(G) = (G)
G is vertex-full (edge-full, respectively) if all its vertices (arcs, respectively) can be covered by (G)

cliques. In other words, G is vertex-full if and only if cp(G) = (G). Clearly, if G is edge-full, then
it is undirected; a characterisation of edge-full graphs is given in [42] and we shall give another one in
Proposition 10 below.
December 18, 2014

DRAFT

22

We can easily obtain a classical lower bound on the guessing number. Firstly, the clique Kn is always
linearly solvable over all alphabets by the following coding function f (see Figure 2):
fi (xi ) =

xj

mod q.

j6=i

Indeed, all states summing to zero mod q are fixed by f and hence gL (Kn , q) = g(Kn , q) = n 1.
(For n = 1, we simply set f (x) = 0.) Therefore, if we partition the vertex set of G into cp(G) cliques
and apply the corresponding coding function on each clique, we obtain a linear coding function with
q ncp(G) fixed points, thus yielding [32]
gL (G, q) n cp(G).

This lower bound implies that vertex-full graphs are linearly solvable over all alphabets. On the other
hand, many classes of linearly solvable digraphs are not vertex-full, e.g. the directed cycle (see [6]
for more striking examples). Until now, however, the only known linearly solvable undirected graphs
are vertex-full. Based on the results in [38], we can construct the first example of a linearly solvable
undirected graph which is not vertex-full. Firstly, for two digraphs G1 and G2 on disjoint vertex sets of
G2 where G1 and G2 are linked by
sizes n1 and n2 respectively, their bidirectional union is G := G1

all possible edges between them. The linear guessing number then satisfies for all q [6]
gL (G, q) = min{n1 + gL (G2 , q), n2 + gL (G1 , q)}.

Theorem 5. There exists an undirected graph which is linearly solvable, and yet it is not vertex-full.
Proof: Let G1 := E6 denote the empty graph on n1 := 6 vertices and with linear guessing number
0 for any q . Let G2 := C denote the Clebsch graph: C has n2 := 16 vertices, independence number
(C) = 5, and gL (C, 3) 10 [38]. Since C is triangle-free but not vertex-full, it is not linearly solvable
C is linearly solvable but not vertex-full, since
as we shall see below. Nonetheless, the graph G := E6
n = 22, (G) = 6 and gL (G, 3) = 16.

Definition 5. Let I be a non-empty acyclic set I of a digraph G.

I is strongly compatible if for all u, v

/ I , (u, v) G if and only if there is a path from u to v

through I .

I is weakly compatible if for all u, v

/ I , the following holds: if (u, v) is an arc, then there is a

path from u to v through I ; otherwise, there is either no path from u to v through I or there are at
least two paths from u to v through I .
December 18, 2014

DRAFT

23

Theorem 6. If G is strictly linearly solvable over some alphabet, then all maximum acyclic sets of G
are weakly compatible.
The proof of the theorem is based on the following lemma: if we consider the interaction graph G(f )
of a linear coding function f , we can only erase an arc from G(f ) if we use a path through I .
Lemma 2. Let f be a linear coding function and I be an acyclic set of G(f ), and any vertices u, v
outside of I such that (u, v) G(f ) but (u, v)
/ G(f I ). Then there exists a path in G(f ) from u to v
through I .
Proof: Suppose (u, v) G(f ) but (u, v)
/ G(f I ) and that there is no path in G(f ) from u to v
P
through I . Denote fv (x) = jin(v) aj xj . Denote N = in(v) I , then there is no path in G(f ) from u

to N through I ; as such there is no arc from u to N in G(f (I\N ) ). Thus, we have

fvI (x) = au xu +

bj x j ;

j6=u

the only occurrence of the variable xu is due to the original fv (x).

Proof of Theorem 6: Suppose that I is a maximum acyclic set of G which is not weakly compatible.
There are two ways weak compatibility can be violated.
1) Let u, v
/ I such that (u, v) G and yet there is no path from u to v through I . Then by Lemma
2 for any linear coding function f L(G, q), (u, v) is an arc in G(f I ), thus by Theorem 3 f
has fewer than q k(G) fixed points.
2) Let u, v
/ I such that (u, v)
/ G and yet there is a unique path from u to v through I . If
P
fa (x) = b ca,b xb for all a and b in(a) and if the path is u0 = u, u1 , . . . , uk = v , it is easy to
Q
check that the xu term in fvI is ki=1 cui ,ui1 6= 0. Again f I is not the identity and f has fewer
than q k(G) fixed points.

Not all undirected graphs G where all the maximum independent sets are weakly compatible are vertex of an independent set of size three E3 with the
G
full. For instance, the bidirectional union G = E3
is a counter-example. The Grotzsch graph is illustrated in Figure
complement of the Grotzsch graph G
) = 2
3; it is triangle-free and has chromatic number 4. Therefore, its complement is not vertex-full: (G
) = 4. In G, E3 then forms a maximum independent set, which is clearly weakly compatible;
while cp(G

however (G) = 3 while cp(G) = 4, thus G is not vertex-full.

Nonetheless, we can classify linearly solvable triangle-free undirected graphs. A matching in a digraph

December 18, 2014

DRAFT

24

10
4

1
9

6
11

Fig. 3: The Grotzsch graph G.

is a union of disjoint undirected edges in the digraph. We denote the number of edges in a maximum
matching in the digraph G as (G). If G is undirected, then it is easily seen that c(G) = (G); hence G
is solvable by routing if and only if (G) = k(G). Moreover, if G is triangle-free, then these properties
are in turn equivalent to G being vertex-full. Theorem 7 then proves that if an undirected triangle-free
graph is solvable by linear network coding, then it is solvable by routing.
Theorem 7. Let G be an undirected triangle-free graph. The following are equivalent:
1) G is linearly solvable over some alphabet.
2) G is linearly solvable over all alphabets.
3) G is solvable by routing.
4) G is vertex-full.
5) (G) = k(G).
Proof: We first remark that a triangle-free graph G is vertex-full if and only if it has a matching of
size (G) = k(G), in which case G is linearly solvable (by routing) over all alphabets. Now, suppose G
is triangle-free and linearly solvable over some alphabet. Then there exists a subgraph H of G such that
H is strictly linearly solvable and k(H) = k(G). H is not necessarily undirected, hence we denote the
; thus H
is a spanning
undirected graph obtained from H by adding any arc (u, v) if (v, u) H as H
December 18, 2014

DRAFT

25

= k(G). Let I be a maximum independent set of G, then I is also a maximum

subgraph of G with k(H)

acyclic set of H ; by Theorem 6, it is weakly compatible in H . Then if (u, v) is an arc in H outside of

, which is impossible. Thus H
is bipartite
I , there exists i I such that u, i, and v form a triangle in H
= k(H)
= k(G). Since (G) (H)
, we obtain that
and by the Konig-Egervary theorem [43], (H)
(G) = k(G).

We now prove that strictly linearly solvable complements of triangle-free graphs are vertex-full as well.
Theorem 8. Let G be an undirected graph with (G) = 2. If G is strictly linearly solvable over some
alphabet, then G is vertex-full (or equivalently, G is the complement of a bipartite graph).
Proof: If G is strictly linear solvable over some alphabet, then by Theorem 6, every non-edge is
weakly compatible, and we prove that this implies that G is vertex-full, i.e. that the vertex set of G can
be partitioned into two cliques. Let ab be a non-edge in G, let Ca be a maximal clique containing a, and
let Cb be a maximal clique containing b. If Ca and Cb cover all vertices, we are done. Otherwise, there
exists c which does not belong to either clique.
Claim 1. There exist d Ca , e Cb , disjoint from a and b, such that a, b, c, d, e induce a graph with
exactly 7 edges and the following 3 non-edges: ab, cd and ce.
Proof: Since a, b, c cannot form an independent set, without loss ac is an edge. By maximality of
Ca , there exists d Ca such that ad is an edge and cd is a non-edge. Then ab is weakly compatible,
cd is a non-edge, and they have a common neighbour (namely, a) in ab: cd must have another common

neighbour, namely b, which means that bc and bd are edges. In turn, there exists e Cb such that be
is an edge and ce is not an edge; as above, ae is also an edge. Finally, since c, d, e cannot form an
independent set, de is an edge.
Claim 2. If c and f do not belong to Ca or Cb , then cf is an edge.
Proof: The vertices corresponding to c are a to e as in Claim 1; let f not in Ca or Cb either and
suppose that cf is not an edge. Since c, d, f cannot form an independent set, f d is an edge. Thus there
exists g Ca with q 6= d such that f g is not an edge, and similarly there exists h Cb with h 6= e
such that f h is not an edge. Now, cd is weakly compatible, f g is not an edge and they only have d as
common neighbour in cd, which is a contradiction.
Therefore, the vertices outside of Ca or Cb form a clique, which we shall refer to as Cc .

December 18, 2014

DRAFT

26

Claim 3. Let f Cc and g Ca such that f g is not an edge. Then for any i Cb , gi is an edge.
Proof: Suppose that gi is not an edge. Since f, g, i cannot form an independent set, f i is an edge.
Then using the notation above, gi is weakly compatible, f h is not an edge and they only have i as a
common neighbour in gi, which is a contradiction.
By the above, the following two sets of vertices induce disjoint cliques and cover all vertices:
1) Cc and all the vertices in Ca connected to all the vertices in Cc ;
2) Cb and all the remaining vertices of Ca .

D. Non linearly solvable digraphs

Theorem 6 yields and easy way to construct digraphs that are not strictly linearly solvable. Indeed, let
I = {i1 , . . . , im } in topological order be a maximum acyclic set of G and let (u, v) be an arc outside of
I such that the out-neighbourhood of u in I is after (in topological order) than the in-neighbourhood of
v . Then there is no path from u to v through I and I is not weakly compatible.

More interestingly, based on Theorem 6, we can construct digraphs which are not linearly solvable.
The strategy to construct such a digraph G uses two main ideas. Firstly, we force any possible linear
solution to use an arc (u, v) in a minimum feedback vertex set J . This can be done by ensuring that
the graph obtained by removing (u, v) has a smaller feedback vertex set than G. Secondly, we make
sure that there is no path from u to v through the corresponding maximum acyclic induced subgraph
I = V \ J . Thus, I is not weakly compatible and by Theorem 6, the graph is not linearly solvable.

Let Gk = (I J, E) be any digraph such that

I = {i1 , . . . , ik1 } and J = {j1 , . . . , jk } are disjoint;

I is acyclic;

J \ {jk } is acyclic;

J contains a path from j1 to jk ;

jk only has one out-neighbour in J , namely j1 ;

I and J are connected using undirected edges as follows: i1 j1 , ia jb for all 1 a k 1 and
2 b k 1, and ic jk for all 2 c k 1.

A graph G3 is illustrated in Figure 4, where we have chosen the graph which included all possible arcs.
Theorem 9. For any k 2, k(Gk ) = k and gL (Gk , q) = k 1 for all q .

December 18, 2014

DRAFT

27

j1

i1

i2

j2

j3

Fig. 4: Example of a non linearly solvable digraph: G3 .

Proof: We first verify that I is a maximum acyclic set, i.e. that no set of k vertices is acyclic. Let S
be a set of k vertices. If S = J , S is not acyclic. Now suppose S contains a vertex i I . Firstly, suppose
i = i1 , then if S contains jb for 1 b k 1, S contains the cycle i1 jb , otherwise the only case left is
S = I {jk }, which again has a cycle ik1 jk . Secondly, suppose i = ia for 2 a k 1, then if S

contains jb for 2 b k, S contains the cycle ia jb , otherwise the only case left is S = I {j1 }, which
has a cycle i1 j1 .
Now suppose that gL (Gk , q) = k, that is, G is linearly solvable for some q . Then it has a strictly
linearly solvable subgraph H such that k(H) = k. Then we force (jk , j1 ) H because if (jk , j1 )
/ H,
then I becomes a feedback vertex set of H of size k 1. Now, by construction, H has no path from jk
to j1 through I ; thus I is a maximum acyclic set of H which is not weakly compatible, thus by Theorem
6 H is not strictly linearly solvable, a contradiction. Thus gL (Gk , q) k 1. Conversely, G contains a
matching of size k 1, namely {ia ja : 1 a k 1}, thus gL (Gk , q) = k 1 for all q .
E. Strictly linearly solvable graphs
The reduction of coding functions also allows to construct strictly linearly solvable digraphs. Theorem 6
and its applications to Theorems 7 and 9 already illustrated how to use strictly linearly solvable digraphs
as a means to study linearly solvable graphs. Nonetheless, we would like to motivate the study of strictly
(linearly) solvable digraphs. Firstly, in the context of (Boolean) coding functions used as models of gene
networks, an arc (u, v) in the interaction graph illustrates the fact that the gene u directly influences the
gene v : such an influence may not be ignored. Secondly, studying strictly solvable digraphs indicates
which arcs must be ignored in order to correctly transmit information by network coding. Indeed, suppose

December 18, 2014

DRAFT

28

s1

s2

i3

i4

d1

d2

(a) Network coding instance

(b) Corresponding graph

Fig. 5: A non-strictly solvable network coding instance.

G is solvable but not strictly solvable, then there exists an arc in G which must not be used in any solution

of G. Therefore, that arc is not only useless, but it is actually detrimental to network coding. An example
is given in Figure 5; the graph is clearly solvable, yet the thick arc makes it non-strictly solvable. Thirdly,
by focusing on strictly linearly solvable digraphs, we show in Theorem 10 that a large class of digraphs
are linearly solvable.
Theorem 10. If G has a strongly compatible maximum acyclic set and no loop, then G is strictly linearly
solvable.
Proof: The reader is reminded of the 1{P} notation used in the proof of Theorem 3. Let I be a
strongly compatible maximum acyclic set, say I = {i1 , . . . , im } in topological order. For all vertices
u, v V \ I , the number of path from u to v through I is denoted NI (u, v). Let q be a prime number

greater than maxu,vV \I NI (u, v), and f L(G, q) as follows:

fi (x) =

xu ,

i I

uin(v)

fv (x) =

iin(v)I

1
xi
NI (v, v)

jin(v)\I

NI (j, v)
xj
NI (v, v)

v
/ I.

Remark that NI (v, v) 6= 0 since V \ I is a minimal feedback vertex set and that NI (j, v) 6= 0 since I
is strongly compatible. The inverse of NI (v, v) then exists since q is a prime; since q is larger than any
NI (j, v), we have NI (j, v) 6= 0 mod q either. Therefore, G(f ) = G.

We shall prove that f I is the identity. For that purpose, we prove the following by induction on

December 18, 2014

DRAFT

29

0 b m. Let I0 = and Ib = {i1 , . . . , ib }, then

fiIb (x) =

(NIb (u, i) + 1{(u, i) G})xu ,

i I \ Ib

uI
/ b

fvIb (x) =

X NI (u, v)
b
xu +
NI (v, v)

uI
/ b

iin(v)(I\Ib )

1
xi
NI (v, v)

jin(v)\I

NI (j, v)
xj
NI (v, v)

v
/ I.

This clearly holds for b = 0. We have f Ib+1 = f Ibib+1 . Let i I \ Ib+1 ; by induction hypothesis,
the xu term in fiIb is
fiIb (xu ) = NIb (u, i) + 1{(u, i) G};

(1)

the xib+1 term in fiIb is

fiIb (xib+1 ) = NIb (ib+1 , i) + 1{(ib+1 , i) G} = 1{(ib+1 , i) G};
b
and the xu term in fiI
is
b+1
b
fiI
(xu ) = NIb (u, ib+1 ) + 1{(u, ib+1 ) G}.
b+1

Ib+1

By applying the reduction, we obtain that the xu term in fi

Ib+1

fi

is

(xu ) = 1{(u, i) G} + NIb (u, i) + 1{(ib+1 , i) G} (NIb (u, ib+1 ) + 1{(u, ib+1 ) G})
= 1{(u, i) G} + NIb+1 (u, i).
Ib+1

Now let v
/ I : we have two cases to consider for fv

. First, let i I \ Ib ; by induction hypothesis,

the xi term in fvIb is

fvIb (xi ) =

1
1{(i, v) G}
[NIb (i, v) + 1{(i, v) G}] =
,
NI (v, v)
NI (v, v)

(2)

b
since there is no path from i to v through Ib ; and the xi term in fiI
is
b+1
b
fiI
(xi ) = NIb (i, ib+1 ) + 1{(i, ib+1 ) G} = 0,
b+1

Ib+1

for similar reasons. By applying the reduction, we obtain that the xi term in fv
fvIb+1 (xi ) =

1{(i, v) G}
NI (v, v)

is

Secondly, let u
/ I ; by induction hypothesis, the xu term in fvIb is
fvIb (xu ) =

1
[NIb (u, v) NI (u, v)1{(u, v) G}] ;
NI (v, v)

the xib+1 term in fvIb is

fvIb (xib+1 ) =
December 18, 2014

1{(ib+1 , v) G}
NI (v, v)
DRAFT

30
b
(similarly to (2)) and the xu term in fiI
is
b+1
b
fiI
(xu ) = NIb (u, ib+1 ) + 1{(u, ib+1 ) G}
b+1

Ib+1

(similar to (1)). By applying the reduction, we obtain that the xu term in fv

is

1
[NIb (u, v) + 1{(ib+1 , v) G} (NIb (u, ib+1 ) + 1{(u, ib+1 ) G}) NI (u, v)1{(u, v) G}]
NI (v, v)
NIb+1 (u, v) NI (u, v)1{(u, v) G}
.
=
NI (v, v)

fvIb+1 (xu ) =

Having proved the claim, we can use it for b = m: this yields

fvI (x) =

X NI (u, v) 1{(u, v) G}NI (u, v)

NI (v, v)

uI
/

xu .

The xv term in fvI (x) is then 1 (since G has no loop on v ); if u in(v), the term is (NI (u, v)
NI (u, v))/NI (v, v) = 0; if u
/ in(v), we have NI (u, v) = 0 since I is strongly compatible and hence

the term in xu also vanishes. Thus, fvI (x) = xv .

Corollary 5. For any loopless digraph D , there exists a strictly linearly solvable graph G such that D
is an induced subgraph of G.
Proof: We shall use a construction similar to that in the proof of Proposition 1. Let J be the vertex
set of D , then let G be the graph with G[J] = D and such that, for any arc (u, v) of D , G contains |J|+1
vertices (u, v, 1), . . . , (u, v, |J| + 1) and the arcs (u, (u, v, i)) and ((u, v, i), v) for all 1 i |J| + 1.
Then the vertices outside of J form a strongly compatible maximum acyclic set and G is strictly linearly
solvable.
Corollary 5 indicates that non-solvability is not a local property. One cannot isolate an induced subgraph
of a graph and decide that this graph is not solvable.
Note that the converse of Theorem 10 is not true: the complete bipartite graph K2,2 , illustrated in
Figure 6 is strictly linearly solvable but does not have any strongly compatible maximum independent
set. The strict solution for K2,2 is given, for any odd field, by
x3 + x4
,
2
x3 x4
f2 (x3 , x4 ) =
,
2
f1 (x3 , x4 ) =

f3 (x1 , x2 ) = x1 + x2 ,
f4 (x1 , x2 ) = x1 x2 .

December 18, 2014

DRAFT

31

Fig. 6: K2,2 : a strictly linear solvable graph which is not edge-full.

Notably, the graph G on Figure 5 is a subgraph of K2,2 . Therefore, the thick arc, which is detrimental
in G, becomes useful in K2,2 .
We generalise this observation to all balanced complete bipartite graphs.
Proposition 9. The complete bipartite graph Kk,k with k 1 is strictly linearly solvable over all
sufficiently large finite fields.
Proof: The case k = 1 being clear, we assume k 2 henceforth. We first prove that for all prime
power q 3k2 , there exists a k k nonsingular matrix M GL(k, q) such that M and M 1 have no
zero entry. Denote the set of k k matrices over GF(q) with no zero entry as Z(k, q); we then have


2 2
k2
k2
k2
qk ,
|Z(k, q)| = (q 1) q
1
q
3
while the number of nonsingular matrices is famously lower bounded by

X
Y
9 2
2
2
2
(1 q j ) = q k
|GL(k, q)| q k
(1)l q l(3l1)/2 q k (1 q 1 q 2 ) q k ,
10
j=1

lZ

using Eulers pentagonal number theorem. We obtain



1
2
1 2
9
k2
+ 1 > q k > |GL(k, q)|.
|GL(k, q) Z(k, q)| q
10 3
2
2
Hence |GL(k, q)Z(k, q)| > |GL(k, q)\Z(k, q)|. Thus, inversion cannot be an injection from GL(k, q)
Z(k, q) to GL(k, q) \ Z(k, q) and such a matrix M exists.

Now let q 3k2 and M such that M, M 1 Z(k, q). Let the vertex set of Kk,k be L R and
consider the following linear coding function on Kk,k :
fR (xL ) = xL M,

fL (xR ) = xR M 1 .

Then clearly every vector of the form (xL , xR = xL M ) is fixed by f .

We make a note on edge-full undirected graphs. An intersection model for an undirected graph G is
an ordered pair (S, X), where S is a set and X = (X1 , . . . , Xn ) is a collection of n subsets of S such
December 18, 2014

DRAFT

32

that for all vertices u, v of G, uv is an edge if and only if Xu Xv 6= . The size of the intersection
model is simply the size of S ; the minimum size of an intersection model for G is denoted as (G).
Then (G) (G) i(G), where i(G) is the number of isolated vertices of G. Indeed, any non-isolated
vertex in a maximum independent set needs at least a singleton in the model; all these are disjoint, hence
any intersection model must have at least that many elements.
Proposition 10. Let G be an undirected graph. Then the following are equivalent.
1) An independent set of G is strongly compatible.
2) A maximum independent set of G is strongly compatible.
3) All maximum independent sets of G are strongly compatible.
4) G is edge-full.
5) (G) = (G) i(G).
Proof: Clearly, Property 3 implies 2, which in turn implies 1. Moreover, if I = {i1 , . . . , im } is a
strongly compatible independent set (non necessarily maximum), then the neighbourhood of each il is a
clique. We claim that these m cliques cover all edges in G. Indeed, there are no edges in I ; any edge
with one vertex in I is clearly covered by these cliques; finally, for any edge uv outside of I , then there
is i I such that uv is in the clique corresponding to i. Conversely, it clearly takes at least (G) cliques
to cover all the vertices of G, and hence at least (G) cliques to cover all edges of G. This shows that
any strongly compatible independent set is maximum and that Property 1 implies 4.
We now show that Property 4 implies 3. Suppose all edges of G are covered by (G) cliques c1 , . . . , c ,
then any maximum independent set I contains one vertex i1 , . . . , i per clique; clearly, each il belongs
to exactly one clique cl . Suppose u and v are vertices outside of I . If uv is an edge, then it belongs
to some clique c and hence ui , i v are edges in G. Conversely, if uv is not an edge, then u and v
cannot belong to a common clique and hence there is no vertex i I such that ui, iv are edges. Thus,
I is strongly compatible.

Clearly, Property 2 implies 5: if I is a strongly compatible maximum independent set, then let S = I \U ,
with U the set of isolated vertices of G, and Xv = (v in(v)) S . Conversely, if G has a model
(S = {s1 , . . . , s }, X) of size = (G) i(G), then if I is a maximum independent set, we must have

an enumeration {i1 , . . . , i } of I \ U such that Xi1 = s1 , . . . , Xi = s . Thus, for any u, v

/ I , uv is an
edge if and only if s Xu Xv for some , which is equivalent to ui and i v being edges, and I is
strongly compatible.
We give an example of a digraph which is not edge-full and yet is strictly linearly solvable in Figure 7.
December 18, 2014

DRAFT

33

Fig. 7: Example of a non edge-full digraph which is strictly linearly solvable.

The set {1, 2} is a strongly compatible maximum acyclic set, hence by Theorem 10 the graph is strictly
linearly solvable. Since the graph is not undirected, it is not edge-full; moreover, we remark that {1, 5}
is a maximum acyclic set which is not strongly compatible.
V. ACKNOWLEDGMENT
The authors would like to thank George Mertzios for interesting discussions leading to Proposition 10.
R EFERENCES
[1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, Network information flow, IEEE Transactions on Information
Theory, vol. 46, no. 4, pp. 12041216, July 2000.
[2] R. W. Yeung, S.-Y. R. Li, N. Cai, and Z. Zhang, Network Coding Theory, ser. Foundation and Trends in Communications
and Information Theory.

Hanover, MA: now Publishers, 2006, vol. 2, no. 4-5.

[3] R. Dougherty, C. Freiling, and K. Zeger, Unachievability of network coding capacity, IEEE Transactions on Information
Theory, vol. 52, no. 6, pp. 23652372, June 2006.
[4] , Networks, matroids, and non-Shannon information inequalities, IEEE Transactions on Information Theory, vol. 53,
no. 6, pp. 19491969, June 2007.
[5] S. Riis, Information flows, graphs and their guessing numbers, The Electronic Journal of Combinatorics, vol. 14, pp.
117, 2007.
[6] M. Gadouleau and S. Riis, Graph-theoretical constructions for graph entropy and network coding based communications,
IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 67036717, October 2011.
[7] M. Gadouleau, Closure solvability for network coding and secret sharing, IEEE Transactions on Information Theory,
no. 12, pp. 78587869, December 2013.
[8] , Entropy of closure operators and network coding solvability, Entropy, vol. 16, no. 9, pp. 51225143, September
2014.
[9] S.

Riis.

(2007,

November)

Graph

entropy,

network

coding

and

guessing

games.

[Online].

Available:

[Link]
December 18, 2014

DRAFT

34

[10] S. A. Kauffman, Metabolic stability and epigenesis in randomly connected nets, Journal of Theoretical Biology, vol. 22,
pp. 437467, 1969.
[11] R. Thomas, Boolean formalization of genetic control circuits, Journal of Theoretical Biology, vol. 42, pp. 563585, 1973.
[12] R. Thomas and M. Kaufman, Multistationarity, the basis of cell differentiation and memory. I. Structural conditions of
multistationarity and other nontrivial behavior, Chaos, vol. 11, no. 1, pp. 170179, 2001.
[13] H. De Jong, Modeling and simulation of genetic regulatory systems: A literature review, Journal of Computational
Biology, vol. 9, pp. 67103, 2002.
[14] W. S. Mac Culloch and W. S. Pitts, A logical calculus of the ideas immanent in nervous activity, Bull. Math. Bio. Phys.,
vol. 5, pp. 113115, 1943.
[15] J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. Nat. Acad. Sc.
U.S.A., vol. 79, pp. 25542558, 1982.
[16] E. Goles, Dynamics of positive automata networks, Theoretical Computer Science, vol. 41, pp. 1932, 1985.
[17] S. Poljak and M. Sura, On periodical behaviour in societies with symmetric influences, Combinatorica, vol. 3, pp.
119121, 1983.
[18] E. Goles and M. Tchuente, Iterative behaviour of generalized majority functions, Mathematical Social Sciences, vol. 4,
pp. 197204, 1983.
[19] R. Thomas and R. DAri, Biological Feedback.

CRC Press, 1990.

[20] E. Goles and S. Martnez, Neural and automata networks: Dynamical behavior and applications.

Kluwer Academic

Publishers, Norwell, MA, USA, 1990.

[21] G. Karlebach and R. Shamir, Modelling and analysis of gene regulatory networks, Nature, vol. 9, pp. 770780, October
2008.
[22] F. Robert, Discrete iterations: a metric study, ser. Series in Computational Mathematics.

Springer, 1986, vol. 6.

[23] J. Aracena, J. Demongeot, and E. Goles, Fixed points and maximal independent sets in AND-OR networks, Discrete
Applied Mathematics, vol. 138, pp. 277288, 2004.
[24] E. Remy, P. Ruet, and D. Thieffry, Graphic requirements for multistability and attractive cycles in a Boolean dynamical
framework, Advances in Applied Mathematics, vol. 41, pp. 335350, 2008.
[25] J. Aracena, Maximum number of fixed points in regulatory Boolean networks, Bulletin of Mathematical Biology, vol. 70,
pp. 13981409, 2008.
[26] A. Richard, Positive circuits and maximal number of fixed points in discrete dynamical systems, Discrete Applied
Mathematics, vol. 157, pp. 32813288, 2009.
[27] J. Aracena, A. Richard, and L. Salinas, Maximum number of fixed points in AND-OR-NOT networks, Journal of
Computer and System Sciences, vol. 80, pp. 11751190, 2014.
[28] M. Gadouleau, A. Richard, and S. Riis. (2014) Fixed points of Boolean networks, guessing graphs, and coding theory.
[Online]. Available: [Link]
[29] A. Richard. (2013) Fixed point theorems for boolean networks expressed in terms of forbidden subnetworks. [Online].
Available: [Link]
[30] S.-Y. R. Li, R. W. Yeung, and N. Cai, Linear network coding, IEEE Transactions on Information Theory, vol. 49, no. 2,
pp. 371381, February 2003.
[31] S. Riis, Utilising public information in network coding, in General Theory of Information Transfer and Combinatorics,
ser. Lecture Notes in Computer Science, vol. 4123/2006.

December 18, 2014

Springer, 2006, pp. 866897.

DRAFT

35

[32] D. Christofides and K. Markstrom, The guessing number of undirected graphs, Electronic Journal of Combinatorics,
vol. 18, no. 1, pp. 119, 2011.
[33] A. Naldi, E. Remy, D. Thieffry, and C. Chaouiya, Dynamically consistent reduction of logical regulatory graphs,
Theoretical Computer Science, vol. 412, pp. 22072218, 2011.
[34] T. Kobayashi, L. Chen, and K. Aihara, Modeling genetic switches with positive feedback loops, Journal of Theoretical
Biology, vol. 221, pp. 379399, 2003.
[35] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, ser. Springer Monographs in Mathematics.
Springer, 2009.
[36] T. Wu, P. J. Cameron, and S. Riis, On the guessing number of shift graphs, Journal of Discrete Algorithms, vol. 7, pp.
220226, 2009.
[37] R. Baber, D. Christofides, A. N. Dang, S. Riis, and E. R. Vaughan, Multiple unicasts, graph guessing games, and nonShannon inequalities, in Proc. NetCod 2013, 2013.
[38] P. J. Cameron, A. N. Dang, and S. Riis. (2014, October) Guessing games on triangle-free graphs. [Online]. Available:
[Link]
[39] F. Robert, Les Syst`emes Dynamiques Discrets.

Springer, 1995.

[40] R. Dougherty and K. Zeger, Nonreversibility and equivalent constructions of multiple unicast networks, IEEE Transactions
on Information Theory, vol. 52, no. 11, pp. 12871291, November 2006.
[41] G. J. Chang, K. Feng, L.-H. Huang, and M. Lu, The linear guessing number of undirected graphs, Linear Algebra and
Applications, vol. 449, pp. 119131, 2014.
[42] R. C. Brigham and R. D. Dutton, On clique covers and independence numbers of graphs, Discrete Mathematics, vol. 44,
pp. 139144, 1983.
[43] J. Bondy and U. Murty, Graph Theory, ser. Graduate Texts in Mathematics.

December 18, 2014

Springer, 2008, vol. 244.

DRAFT