Printer Friendly

Finiteness conditions for graph algebras over tropical semirings.

1 Introduction and Summary

Connection matrices of graph parameters with values in a field K have been introduced by M. Freedman, L. Lovasz and A. Schrijver (2007). Graph parameters with connection matrices of finite rank exhibit many nice properties. In particular, as was shown by L. Lovasz, (L.Lovasz, 2012, Theorem 6.48), they can be computed in polynomial time on graph classes of bounded tree-width. This is a logic-free version of the celebrated theorem by B. Courcelle, cf. (Downey and Fellows, 1999, Chapter 6.5) and (Flum and Grohe, 2006, Chapter 11.4-5). The theorem is proved using the formalism of graph algebras as developed in L.Lovasz (2012).

In this paper we introduce join matrices, a generalization of connection matrices, which will allow us to replace the condition on tree-width to weaker conditions involving clique-width. Courcelle's theorem was extended to this case in Courcelle et al. (1998); Oum (2005). Furthermore we study graph parameters which take values in the tropical semirings [T.sub.max] and [T.sub.min] (max-plus algebras) over the real numbers, as opposed to values in a field. We shall call them tropical graph parameters in contrast to real graph parameters.

There are several notions of rank for matrices over commutative semirings. All of them coincide in the case of a field, and some of them coincide in the tropical case, Butkovic (2010); Guterman (2009); Cuninghame-Green and Butkovic (2004). We shall work with two specific notions: row-rank in the tropical case, and a finiteness condition introduced by G. Jacob Jacob (1975), which we call J-finiteness, in the case of arbitrary commutative semirings.

A typical example of a tropical graph parameter with finite row-rank of its connection matrix is [omega](G), the maximal size of a clique in a graph G. If viewed as a real graph parameter, its connection matrix has infinite rank.

Main results

We adapt the formalism of graph algebras to tropical semirings with an inner product derived from the join matrices. Superficially this adaption may seem straightforward. However, there are several complications to be overcome: (i) the definition of the join matrix, (ii) the choice of the finiteness condition on the join matrices, and (iii) the choice of the definition of the quotient algebra.

(Theorem 6.2) We show that row-rank finiteness of join matrices implies that tropical graph parameters can be computed in polynomial time on graph classes of bounded clique-width.

(Theorem 6.3) A similar result holds in arbitrary commutative semirings when we replace row-rank finiteness with J-finiteness and bounded clique-width with bounded linear clique-width.

It was shown by B. Godlin, T. Kotek and J.A. Makowsky (2008) that definability of the graph parameter in Monadic Second Order Logic implies rank finiteness.

(Theorems 4.4,4.6) We show that there are uncountably many integer valued graph parameters with connection matrices or join matrices of fixed finite rank. This shows that (row)-rank finiteness is a much weaker assumption than any definability assumption.

It is well known that graph classes of bounded tree-width are also of bounded clique-width, therefore we restrict our presentation to the case of bounded clique-width. All results stated in this paper for tropical or arbitrary commutative semirings hold for fields as well.

Outline of the paper

In Section 2 we give the background on k-graphs, k-colored graphs, tree-width and clique width. In Section 3 we introduce join-matrices, and more generally, Hankel matrices and their ranks. In Section 4 we show that there are uncountably many graph parameters with Hankel matrices of fixed finite rank. In Section 5 we construct the graph algebras for join-matrices of finite row-rank. Finally, in Section 6 we show our main theorems for graph classes of bounded (linear) clique-width. In Section 7 we discuss our achievements and remaining open problems.

2 Prerequisites

2.1 k-graphs and k-colored graphs

Let k [member of] N. A k-graph is a graph G = (V(G), E(G)) together with a partial map i: [k] [right arrow] V(G). l is called a labeling and the images of l are called labels.

A k-colored graph is a graph G = (V(G), E(G)) together with a map C: [k] [right arrow] [2.sup.V(G)]. C is called a coloring and the images of C are called colors.

i and C are often required to be injective, but this is not necessary. If l is partial not all labels in [k] are assigned values in V(G). This corresponds to C having as values the empty set in V(G). The labeling l can be viewed as a special case of the coloring C, where C(i) is a singleton for all i [member of] [k].

We denote the class of graphs by G, the class of k-graphs by [G.sub.k], and the class of k-colored graphs by C[G.sub.k].

2.2 Gluing and joining

We consider binary operations [] on k-graphs, resp. k-colored graphs. Specific examples are the following versions of gluing and joining, but if not further specified, [] can be any isomorphism preserving binary operation.

Two k-graphs ([G.sub.1], [l.sub.1]) and ([G.sub.2], [l.sub.2]) can be glued together producing a k-graph (G, l) = ([G.sub.1], [l.sub.1]) [[??].sub.k] ([G.sub.2], [l.sub.2]) by taking the disjoint union of [G.sub.1] and [G.sub.2] and [l.sub.1] and [l.sub.2] and identifying elements with the same label.

For two k-colored graphs ([G.sub.1], [C.sub.1]) and ([G.sub.2], [C.sub.2]) we have similar operations. Let i, j [member of] [k] be given. We define their (i, j)-join by

[[bar.[eta]]].sub.i,j](([G.sub.1], [C.sub.1]), ([G.sub.2], [C.sub.2])) = (G, C)

by taking disjoint unions for

(i) V(G) = V([G.sub.1]) [??] V([G.sub.2]) and

(ii) for all i [member of] [k] C(i) = [C.sub.1](i) [??] [C.sub.2](i), and

(iii) E(G) = E([G.sub.1]) [??] E([G.sub.2]) [union] {(u, v) [member of] V(G): u [member of] C(i), [upsilon] [member of] C(j)}, which connects in the disjoint union all vertices in C(i) with all vertices in C(j).

[[bar.n].sub.i,j] is a binary version of the operation [[eta].sub.i,j] used in the definition of the clique-width of a graph, cf. Courcelle et al. (1998).

Proposition 2.1 The operations [[??].sub.k] and [[bar.[eta]].sub.i,j] are commutative and associative.

2.3 Inductive definition of tree-width and clique-width

As we do not need much of the theory of graphs of bounded tree-width and clique-width, the following suffices for our purpose. The interested reader may consult Hlineny et al. (2008). In Makowsky (2004) the following equivalent definitions of the class of (labeled or colored) graphs of tree-width at most k (TW(k)), path-width at most k (PW(k)), clique-width at most k (CW(k)), and linear clique-width at most k (LCW(k)) were given:

Tree-width

(i) Every k-graph of size at most k + 1 is in TW(k) and PW(k).

(ii) TW(k) is closed under disjoint union [??] and gluing [[??].sub.k].

(iii) PW(k) is closed under disjoint union [??] and small gluing [[??].sub.k] where one operand is k-graph of size at most k +1.

(iv) Let n: [k] ^[right arrow][k] be a partial relabeling function. If (G, l) [member of] TW(k) then also (G, l') [member of] TW(k) where l'(i) = l([pi](i)). The same holds for PW(k).

Clique-width

(i) Every single-vertex k-colored graph is in CW(k) and LCW(k).

(ii) CW(k) is closed under disjoint union [??] and (i, j)-joins for i, j [less than or equal to] k and i [not equal to] j.

(iii) LCW(k) is closed under disjoint union [??] and small (i, j)-joins for i, j [less than or equal to] k and i [not equal to] j, where one operand is a single-vertex k-colored graph.

(iv) Let [rho]: [2.sup.[k]] [right arrow] [2.sup.[k]] be a recoloring function. If (G, C) [member of] CW(k) then also (G, C') [member of] CW(k) where C'(I) = C([rho](1)). The same holds for LCW(k).

A graph G is of clique-width at most [2.sup.k] iff there is a coloring C such that (G, C) [member of] CW(k). The discrepancy between [2.sup.k] and k comes from the fact that we allow overlapping colorings. Note that in the original definition a unary operation [[eta].sub.i,j] is used instead of the binary (i, j)-join [[bar.[eta]].sub.ij]. However, the two are interdefinable with the help of disjoint union. For a detailed discussion of various width parameters, cf. Hlineny et al. (2008).

A parse tree for G is a witness for the inductive definition describing how G was constructed. Parse trees for G [member of] TW(k) and G [member of] PW(k) can be found in polynomial time, Bodlaender and Kloks (1991). For G [member of] CW(k) the situation seems slightly worse. It was shown in Oum (2005):

Proposition 2.2 (S. Oum) Let G be a graph of clique-width at most k. Then we can find a parse tree for G [member of] CW(3k) in polynomial time.

3 Graph parameters with values in a semiring and their Hankel matrices

An S-valued graph parameter f is a function f: G [right arrow] S which is invariant under graph isomorphisms. If we consider f: [G.sub.k] [right arrow] S or f: C[G.sub.k] [right arrow] S then we require that f is also invariant under labelings and colorings.

Let [X.sub.i]: i [member of] N be an enumeration of all colored graphs in C[G.sub.k]. For a binary operation [] on labeled or colored graphs, and a graph parameter f, we define the Hankel matrix H(f, []) with

H[(f, []).sub.i,j] = f ([X.sub.i][??] [X.sub.j]).

If the operation [] is [[??].sub.k], the Hankel matrix H (f, []) is the connection matrix M (f, k) of L.Lovasz (2012).

Given a Hankel matrix H(f, []) we associate with it the semimodule MH(f, []) generated by its rows. If there exist finitely many elements [g.sub.1], ..., [g.sub.m] [member of] MH(f, []) which generated MH(f, []), we say that MH(f, []) is finitely generated.

3.1 Notions of rank for matrices over semirings

Semimodules over semirings are analogs of vector spaces over fields. However, in contrast to vector spaces, there are several ways of defining the notion of independence for semimodules. For our purposes we adopt the definition 3.4 used in (Guterman, 2009, Section 3) and in Cuninghame-Green and Butkovic (2004), but see also Develin et al. (2005); Akian et al. (2009). A set of elements P from a semimodule U over a semiring S is linearly independent if there is no element in P that can be expressed as a linear combination of other elements in P.

Using this notion of linear independence, we define the notions of basis and dimension as in Guterman (2009); Cuninghame-Green and Butkovic (2004): a basis of a semimodule U over a semiring S is a set P of linearly independent elements from U which generate it, and the dimension of a semimodule U is the cardinality of its smallest basis.

Given a Hankel matrix H(f, []) with its associated semimodule MH(f, []), we define the row-rank r(H(f, [])) of the matrix as the dimension of MH(f, []). In addition, we say that H(f, []) has maximal row-rank mr(H(f, [])) = k if H(f, []) has k linearly independent rows and any k + 1 rows are linearly dependent. These definitions are the definitions used in Guterman (2009), applied to infinite matrices.

As stated in Guterman (2009); Cuninghame-Green and Butkovic (2004), in the case of tropical semirings, we have r(H(f, [])) = rm(H(f, [])).

Lemma 3.1 If a Hankel matrix H(f, []) over a tropical semiring has row-rank r(H(f, [])) = m, then there are m rows in H(f, []) which form a basis of MH(f, []).

Remark 3.1 If the matrix H(f, []) is over a general semiring S, a smallest basis of MH(f, []) does not necessarily reside in H(f, []).

Proof: r(H(f, [])) = m, so by definition the dimension of MH(f, []) is m. Suppose the set B = {[g.sub.1], ..., [g.sub.m]} is a smallest basis for MH(f, []). Each [g.sub.p] is in MH(f, []), therefore there is a finite linear combination of rows from H(f, []) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider the set of all the rows that appear in any of these linear combinations: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since H(f, []) is over a tropical semiring, it holds that mr(H(f, [])) = r(H(f, [])) = m. Therefore, any set of m +1 rows from H(f, []) is linearly dependent. Consider the result of the following process:

(i) Set i = [absolute value of R], and [B.sub.i] = R, note that [B.sub.i] is of size i and generates B. Repeat until i = m:

(ii) Let r' [member of] [B.sub.i] be a row that can be expressed using other rows in [B.sub.i]. Such an element must exist, as [absolute value of [B.sub.i]] > m. Set B' = [B.sub.i] - r', set i = i - 1 and [B.sub.i] = B'.

Note that [B.sub.i] is still of size (now smaller) i and it still generates B.

When i = m is reached, we have [B.sub.m] of size m which generates B. This set must be independent: if it were not, we could perform more iterations of the above process and obtain a linearly independent set of size < m which generates B. But the existence of such a set contradicts B being a smallest basis, Therefore, B is linearly independent and generates B. Since B generate MH(f, []), so does B, making B a basis for MH(f, []) which resides in H (f, []).

After establishing the fact that there lies a basis B of MH(f, []) in H(f, []), we can find it in finite time, due to (Cuninghame-Green and Butkovic, 2004, Theorems 2.4 and 2.5).

4 Graph parameters with join matrices of finite (row-)rank

4.1 Graph parameters definable in Monadic Second Order Logic

It follows from Godlin et al. (2008); Kotek and Makowsky (2012, 2013) that for graph parameters definable in Monadic Second Order Logic (MSOL) or MSOL with modular counting quantifiers (CMSOL), the connection matrices and join matrices all have finite rank over fields, and finite row-rank over tropical semirings.

Let H = (V(H),E(H)) be a weighted graph with weight functions on vertices and edges [alpha]: V(H) [right arrow] R and [beta]: E(H) [right arrow] R. The tropical partition function [Z.sub.H,[alpha],[beta]] on graphs G is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the tropical ring this can be written as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where h ranges over all homomorphisms h: G [right arrow] H.

It is easy to verify that [Z.sub.H,[alpha],[beta]] is MSOL-definable. Hence we have:

Proposition 4.1 H([Z.sub.H,[alpha],[beta]] [[bar.[eta]].sub.ij]) has finite row-rank.

The independence number [alpha](G), which is the cardinality of the largest independent set, is a special case of a tropical partition function.

There are many graph parameters which have infinite connection rank, but finite row-rank if interpreted over tropical semirings. Examples for this phenomenon are the clique number [omega](G) and the independence number [alpha](G). Many other examples may be found in Arnborg et al. (1991).

4.2 Uncountably many graph parameters with finite (row-)rank

Here we show that both over fields and tropical semirings, most of the graph parameters with finite (row)rank of connection or join matrices are not definable in the above mentioned logics.

We first need an observation. A graph is k-connected, if there is no set of k vertices, such that their removal results in a graph which is not connected. Obviously we have:

Lemma 4.2 Let [G.sub.1] and [G.sub.2] be two k-graphs and G = [G.sub.1] [[??].sub.k] [G.sub.2]. Then G is not k + 1- connected.

For a subset A [subset or equal to] N we define graph parameters

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 4.3 Let S be a commutative semiring which contains N. Let [k.sub.0] [member of] N and A [subset or equal to] N with 1 [member of] A. Then for every k [less than or equal to] [k.sub.0] the semimodule of the rows of H([f.sub.A], [[??].sub.k]) is generated by the two rows

(1,0, ...) and (..., [f.sub.A](1, G), ...)

If S is a field, H([f.sub.A], [[??].sub.k]) has rank at most 2.

Proof: By Lemma 4.2, if the graph [G.sub.1] [[??].sub.k] [G.sub.2] is [k.sub.0] + 1-connected, then either [G.sub.1] is [k.sub.0] + 1-connected and [G.sub.2] is the empty graph, or vice versa. So the non-zero entries in H([f.sub.A], [[??].sub.k]) are in the first row and the first column. As 1 [member of] A, we have a row (1,0, ...) which generates all the rows but the first one.

Theorem 4.4 Let [k.sub.0] [member of] N and S a field. There are continuum many graph parameters f with values in S with r(f, [[??].sub.k]) [less than or equal to] 2 for each k [less than or equal to] [k.sub.0].

The same holds for tropical semirings and row-rank.

Proof: There are continuum many subsets A [subset or equal to] N and for two different sets A, B [subset or equal to] N the parameters [f.sub.A] and [f.sub.B] are different.

Let ([G.sub.1], [C.sub.1]), ([G.sub.2], [C.sub.2]) be two 2-colored graphs.

Lemma 4.5 Let (G, C) = [[bar.[eta]].sub.1,2](([G.sub.1], [C.sub.1]), ([G.sub.2], [C.sub.2])) and let [C.sub.1](2) = [C.sub.2](1) = 0.

(i) G is the disjoint union of [G.sub.1] and [G.sub.2] iff [C.sub.1](1) or [C.sub.2](2) are empty.

(ii) If both [C.sub.1](1) and [C.sub.2](2) are not empty, there is a vertex in [C.sub.1](1) which has a higher degree in G than it had in [G.sub.1].

Let r [member of] N and A [subset or equal to] N. We define graph parameters with values in N:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4.6 Let S be a field of characteristic 0. There are continuum many graph parameters [g.sup.r.sub.A] with values in S such that r(f, [[bar.n].sub.1,2]) [less than or equal to] 2.

Similarly for commutative semirings.

Proof: Use Lemma 4.5.

5 Graph algebras

This section presents our adaptation of the formalism of graph algebras, to tropical semirings with an inner product derived from the join matrices of tropical graph parameters.

5.1 Quantum graphs

A formal linear combination of a finite number of k-colored graphs [F.sub.i] with coefficients from [T.sub.max] ([T.sub.min]) is called a quantum graph. The set of k-colored (i) quantum graphs is denoted [Q.sub.k].

Let X, Y be quantum graphs: X = [[direct sum].sup.m.sub.i=1] [a.sub.i][F.sub.i], and Y = [[direct sum].sup.n.sub.i=1] [b.sub.i][F.sub.i]. Note that some of the coefficients may be -[infinity] ([infinity]).

[Q.sub.k] is a semimodule with the operations:

* x [direst sum] y = ([[direct sum].sup.m.sub.i=1] [a.sub.i][F.sub.i]) [direct sum] ([[direct sum].sup.n.sub.i=1] [b.sub.i][F.sub.i]) = [[direct sum].sup.max{m,n}.sub.i=1] ([a.sub.i] [direct sum] [b.sub.i])[F.sub.i], and

* [alpha] [cross product] x = [[direct sum].sup.n.sub.i=1] ([alpha] [cross product] [a.sub.i])[F.sub.i]

We extend any binary operation [] to quantum graphs by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We extend any graph parameter f to quantum graphs linearly

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From now on we assume that [] is a commutative graph operation. Given a Hankel matrix H(f, []), we turn [Q.sub.k] into a commutative algebra by defining an inner product on X, Y:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5.2 Equivalence relations over [Q.sub.k]

Given a Hankel matrix H(f, []), we define an equivalence relation in the following way:

[Ker.sup.[].sub.f] = {(X, Y) [member of] [Q.sub.k] x [Q.sub.k] | [for all]Z [member of] [Q.sub.k]: f ([](X, Z)) = f ([](Y,Z))}

Note that this definition is reminiscent to the equivalence relation used in the Myhill-Nerode Theorem characterizing regular languages, cf. Hopcroft and Ullman (1980).

We denote the set of equivalence classes of this relation by [Q.sub.k]/[Ker.sup.[].sub.f.] [Q.sub.k]/[Ker.sup.[].sub.f] is a semimodule with the operations:

[[X].sup.[??].sub.f] [direct sum] [[Y].sup.[].sub.f] = [[X [direct sum] Y].sup.[].sub.f]

and

[alpha][[X].sup.[].sub.f] = [[[alpha]X].sup.[].sub.f]

We turn [Q.sub.k]/[Ker.sup.[].sub.f] into a quotient algebra by extending the binary operation [] to these equivalence classes. We define

[]([[X].sup.[].sub.f], [Y][[].sub.f) = [[[](X,Y)].sup.[].sub.f]

It can be easily verified that the following properties hold for X' [member of] [[X].sup.[].sub.f] and Y' e[member of] [[Y].sup.[].sub.f]:

Proposition 5.1 Let [] be a commutative and associative operation on graphs.

(i) X' [direct sum] Y' [member of] [[X [direct sum] Y].sup.[].sub.f] = [[X].sup.[].sub.f] [direct sum] [[Y].sup.[].sub.f]

(ii) [alpha]X' [member of] [[[alpha]X].sup.[].sub.f] = [[alpha][X].sup.[].sub.f]

(iii) [](X', Y') [member of] [[[](X, Y)].sup.[].sub.f]

5.3 Finiteness condition on Hankel matrices

Given the Hankel matrix H(f, []) we denote by MH(f, []) the semimodule generated by the rows of H(f, []).

Lemma 5.2 Assume the semimodule MH(f, []) is generated by the rows Gen = {[r.sub.1], ..., [r.sub.m]} of H(f, []), whereeachrow corresponds to a graph [G.sub.q]. Then [Q.sub.k]/[Ker.sup.[].sub.f] is generated by [B.sub.k] = {[[[G.sub.1]].sup.[].sub.f], ..., [[[G.sub.m]].sup.[].sub.f]}.

Proof: Let X [member of] [Q.sub.k], where X = [[direct sum].sup.n.sub.i=1] [a.sub.i][F.sub.i]. Each [F.sub.i] a linear combination of the generators [G.sub.1], ..., [G.sub.m], [F.sub.i] = [[direct sum].sup.m.sub.j=1] [[alpha].sub.i,j][G.sub.j]. By Proposition 5.1(i)-(ii) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

6 Graphs of clique-width at most k

Let k [member of] N be fixed. From now on [] = [[bar.[eta]].sub.1,2] on k-colored graphs, and we write simply [[eta].sup.k] instead of [[bar.[eta]].sub.1,2]. We omit k when it is clear from the context. The Hankel matrix H(f, [eta]) is called the join matrix.

We note that because the rows and columns correspond to all the graphs with all the possible k-colorings, all the join matrices H(f, [[bar.[eta]].sub.i,j]) are submatrices of H(f, [eta]), after a suitable recoloring.

6.1 Representing G in the graph algebra

Given a graph G of clique-width at most k, together with its parse tree of the inductive definition from Section 2.3, we want to find [[[X.sub.G]].sup.[eta].sub.f] [member of] [Q.sub.k]/[Ker.sup.[eta].sub.f] s.t. f ([X.sub.G]) = f (G). Furthermore, [[[X.sub.G]].sup.[eta].sub.f] will be a linear combination of generators of [Q.sub.p]/[Ker.sup.[eta].sub.f] and will be computable in polynomial time.

The same result for tree-width follows from the result on clique-width, but it can also be directly obtained using the inductive definition of tree-width from Section 2.3.

Lemma 6.1 Let G of clique-width at most k be given together with its parse tree T, and let B = {[[[F.sub.1]].sup.[eta].sub.f], ..., [[[F.sub.m]].sup.[eta].sub.f]} be a basis of [Q.sub.k]/[Ker.sub.f]. Then there exists [[[X.sub.G]].sup.[eta].sub.f] [member of] [Q.sub.k]/[Ker.sup.[eta].sub.f] s.t. f ([X.sub.G]) = f (G), and [[[X.sub.G]].sup.[eta].sub.f] can be represented as a linear combination of {[[[F.sub.1]].sup.[eta].sub.f], ..., [[[F.sub.m]].sup.[eta].sub.f]}.

Proof:

Let [S.sub.1], ..., [S.sub.l] [member of] [Q.sub.k] be the single-vertex k-colored graphs (we later refer to them as small graphs), and let [[[S.sub.i]].sup.[eta].sub.f] = [[direct sum].sub.j] [s.sub.ij] [[[F.sub.j]].sup.[eta].sub.f] be their representations in the basis B.

Let [eta]([[[F.sub.i]].sup.[eta].sub.f], [[[F.sub.j]].sup.[eta].sub.f]) be the representations of the results of the [eta] operation on elements from the basis B. Let G be a graph of clique-width at most k, and let T be its parse tree. We proceed by induction on T. If G = [S.sub.i] then set [X.sub.G] = [S.sub.i]. The graph [S.sub.i] is a single-vertex graph, and we have a representation for [X.sub.G]. Assume that for [G.sub.1], [G.sub.2], there exist [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and that there are representations [[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for them.

If G = [eta]([G.sub.1], [G.sub.2]), then by Proposition 5.1(iii) we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We have representations for the operations [eta]([[[F.sub.i]].sup.[eta].sub.f], [[[F.sub.j]].sup.[eta].sub.f]) on the basis elements, so we replace the expressions [eta]([[[F.sub.i]].sup.[eta].sub.f], [[[F.sub.j]].sup.[eta].sub.f]) in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by these representations and obtain a representation of [X.sub.G] = [eta]([G.sub.1], [G.sub.2]) [member of] [[[eta]([G.sub.1], [G.sub.2])].sup.[eta].sub.f].

If G = [[rho].sub.i,j]([G.sub.1]), we replace the basis elements [[[F.sub.i]].sup.[eta].sub.f] in the representation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the representations of [[[[rho].sub.i,j] ([F.sub.i])].sup.[eta].sub.f] and obtain a representation of [X.sub.G].

6.2 Computing f (G)

Theorem 6.2 Let f be a tropical graph parameter. Let the row-rank r(H(f, [eta])) be finite, and let G be a graph of clique width at most k. Then f (G) can be computed in polynomial time.

Proof: We first use Proposition 2.2 to find a parse tree for G [member of] CW(3k). Next, we use dynamic programming to build a representation of the given graph G in the basis B in order to obtain f (G). The algorithm requires a finite amount of preprocessing:

Find basis elements B. By Lemma 3.1 and Theorems 2.4 and 2.5 in Cuninghame-Green and Butkovic (2004) this can be done in finite time.

Compute representations of all the small graphs by basis elements

Compute representations of the product [eta] for all basis elements and all small graphs

Compute the value of f on all the small graphs and basis elements

The algorithm works with the provided parse tree T from the bottom up, following the inductive definition given in the proof of Lemma 6.1. When the top of the tree is reached, we have a representation of [[[X.sub.G]].sup.[eta].sub.f] using only basis elements [[[F.sub.i]].sup.[eta].sub.f]. We then use the precomputed values of f in order to compute the value of f ([X.sub.G]) = f (G).

6.3 Commutative semirings

In the case of S being an arbitrary commutative semiring we use following finiteness condition first introduced in Jacob (1975):

A Hankel matrix H(f, []) of an S-valued graph parameter f is J-finite if MH(f, []) is finitely generated. This does not necessarily imply that H(f, []) has a finite row-rank. However, in automata theory it suffices to prove the following: Let f be a S-valued function on words in [[SIGMA].sup.*] (for a finite alphabet [SIGMA]). Then f is recognizable by a multiplicity automaton iff H(f, [omicron]) is J-finite, Berstel and Reutenauer (1984). Using virtually the same proof we can show:

Theorem 6.3 Let S be an arbitrary commutative semiring. Let f be an S-valued graph parameter and k [member of] N be fixed.

(i) If H(f, [[??].sub.i]) is J-finite for all i [less than or equal to] k, then f can be computed in polynomial time on graphs of path-width at most k.

(ii) If H (f, [[eta].sup.k]) is J-finite, then f can be computed in polynomial time on graphs of linear clique-width at most k.

7 Conclusions

L. Lovasz showed a "logic-free" version of Courcelle's famous theorem, cf. (Downey and Fellows, 1999, Chapter 6.5) and (Flum and Grohe, 2006, Chapter 11.4-5).

Theorem 7.1 (Theorem 6.48 of L.Lovasz (2012)) Let f be a real-valued graph parameter and k [greater than or equal to] 0.

If r(f, [[??].sub.k]) is finite, then f can be computed in polynomial time for graphs of tree-width at most k.

The proof in L.Lovasz (2012) is rather sketchy in its part relating to tree-decompositions. In particular, the role of relabelings, admittedly not very critical, is not spelled out at all.

In this paper we extended Theorem 7.1 to Theorems 6.2 and 6.3 in two ways.

(i) We showed how to prove the theorem for bounded clique-width instead of bounded tree-width.

(ii) We showed how to prove the theorem for tropical graph parameters, and more generally for graph parameters in an arbitrary commutative semirings.

In order to do this we introduced Hankel matrices for binary graph operations, in particular for a binary version of the basic operations used in the definition of clique-width.

The main differences between our proofs and the proof in L.Lovasz (2012) are:

(i) the definition of the join matrix,

(ii) the choice of the finiteness condition of the join matrices, and

(iii) the choice of the definition of the equivalence relation used for the quotient algebra.

We also had to spell out the role of parse trees for clique-width in the dynamic programming part of the polynomial time algorithm.

Our approach also works for

* other notions of width for graphs, such as rank-width and modular width, and other inductively defined graph classes, cf. Makowsky (2004); Hlineny et al. (2008).

* other notions of connection matrices, cf. Schrijver (2012a,b).

In the full paper we shall discuss these extensions in detail.

Tropical graph parameters occur naturally in optimization theory. Graph parameters with values in polynomial rings are called graph polynomials, and are widely studied in diverse fields as statistical mechanics, computational biology and mathematics of finance. It remains open to identify the most suitable finiteness condition on Hankel matrices in the case where the graph parameter has its values in a arbitrary ring or semiring.

References

M. Akian, S. Gaubert, and A. Guterman. Linear independence over tropical semirings and beyond. In Tropical and idempotent mathematics, volume 495 of Contemp. Math., pages 1-38. Amer. Math. Soc., 2009.

S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree decomposable graphs. Journal of Algorithms, 12: 308-340, 1991.

J. Berstel and C. Reutenauer. Rational Series and their languages, volume 12 of EATCS Monographs on Theoretical Computer Science. Springer, 1984.

H. L. Bodlaender and T. Kloks. Better algorithms for path-width and tree-width of graphs. Lecture Notes in Computer Science, 510:544-555, 1991.

P. Butkovic. Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer, 2010.

B. Courcelle, J. Makowsky, and U. Rotics. Linear time solvable optimization problems on graph of bounded clique width, extended abstract. In J. Hromkovic and O. Sykora, editors, Graph Theoretic Concepts in Computer Science, 24th International Workshop, WG'98, volume 1517 of Lecture Notes in Computer Science, pages 1-16. Springer Verlag, 1998.

R. Cuninghame-Green and P. Butkovic. Bases in max-algebra. Linear Algebra and its Applications, 389(0): 107-120,2004. ISSN 0024-3795. doi: http://dx.doi.org/10.1016/jdaa.2004.03.022. URL http://www. sciencedirect.com/science/article/pii/S0024379504001703.

M. Develin, F. Santos, and B. Sturmfels. On the rank of a tropical matrix. In Combinatorial and computational geometry, volume 52 of Math. Sci. Res. Inst. Publ., pages 213-242. Cambridge University Press, 2005.

R. Downey and M. Fellows. Parametrized Complexity. Springer, 1999.

J. Flum and M. Grohe. Parameterized complexity theory. Springer, 2006.

B. Godlin, T. Kotek, and J. Makowsky. Evaluation of graph polynomials. In 34th International Workshop on Graph- Theoretic Concepts in Computer Science, WG08, volume 5344 of Lecture Notes in Computer Science, pages 183-194, 2008.

A. E. Guterman. Matrix invariants over semirings. In M. Hazewinkel, editor, Handbook of Algebra Volume 6, volume 6 of Handbook of Algebra, pages 3-33. North-Holland, 2009. doi: http://dx.doi.org/10. 1016/S1570-7954(08)00201-5. URL http://www.sciencedirect.com/science/article/pii/ S1570795408002015.

P. Hlineny, S. Oum, D. Seese, and G. Gottlob. Width parameters beyond tree-width and their applications. Comput. J., 51(3):326-362, 2008.

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley, 1980.

G. Jacob. Representations et substitutions matricielles dans la theorie algebrique des transductions. PhD thesis, Universite de Paris, VII, 1975.

T. Kotek and J. Makowsky. Connection matrices and the definability of graph parameters. arXiv:1308.3654, 2013.

T. Kotek and J. A. Makowsky. Connection matrices and the definability of graph parameters. In CSL, pages 411-425, 2012.

L.Lovasz. Large Networks and Graph Limits, volume 60 of Colloquium Publications. AMS, 2012.

J. Makowsky. Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic, 126.1-3: 159-213, 2004.

S. Oum. Approximating rank-width and clique-width quickly. In Graph Theoretic Concepts in Computer Science, WG 2005, volume 3787 of Lecture Notes in Computer Science, pages 49-58, 2005.

A. Schrijver. Characterizing partition functions of the spin model by rank growth. arXiv:1209.5044, 2012a.

A. Schrijver. Characterizing partition functions of the vertex model by rank growth. arXiv:1211.3561, 2012b.

(i) In L.Lovasz (2012) this notations is used only for k-graphs and real coefficients. As k-graphs are a special case of k-colored graphs our notations also includes his.

Nadia Labai * and Johann A. Makowsky ([dagger])

Faculty of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel

* Email: nadia@cs.technion.ac.il. Partially supported by a grant of the graduate school of the Technion.

([dagger]) Email: janos@cs.technion.ac.il, Partially supported by a grant of Technion Research Authority.
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Labai, Nadia; Makowsky, Johann A.
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2014
Words:5958
Previous Article:An extension of MacMahon's equidistribution theorem to ordered multiset partitions.
Next Article:Electrical networks, electrical lie algebras and lie groups of finite Dynkin type.
Topics:

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters