text: [18] N. Megiddo. On the ball spanned by balls. Discrete & Computational Geometry, 4(1):605–610, 1989. [19] J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633–701. Elsevier, 2000. [20] B. Nilsson and S. Schuierer. Computing the rectilinear link diameter of a polygon. In Proceedings of CG, pages 203–215, 1991. [21] B. Nilsson and S. Schuierer. An optimal algorithm for the rectilinear link center of a rectilinear polygon. Computational Geometry: Theory and Ap- plications, 6:169–194, 1996. [22] R. Pollack, M. Sharir, and G. Rote. Computing the geodesic center of a simple polygon. Discrete & Computational Geometry, 4(1):611–626, 1989. [23] S. Suri. Minimum Link Paths in Polygons and Related Problems. PhD thesis, Johns Hopkins Univ., 1987. [24] S. Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39(2):220–235, 1989. 23

label: reference

text: N.

text: Megiddo.

text: On

text: the

text: ball

text: spanned

text: by

text: balls.

text: Discrete

text: Computational

text: Geometry,

text: J.

text: S.

text: B.

text: Mitchell.

text: Geometric

text: shortest

text: paths

text: and

text: network

text: optimization.

text: In

text: J.-R.

text: Sack

text: and

text: J.

text: Urrutia,

text: editors,

text: Handbook

text: of

text: Computational

text: Geometry,

text: pages

text: Elsevier,

text: B.

text: Nilsson

text: and

text: S.

text: Schuierer.

text: Computing

text: the

text: rectilinear

text: link

text: diameter

text: of

text: a

text: polygon.

text: In

text: Proceedings

text: of

text: CG,

text: pages

text: B.

text: Nilsson

text: and

text: S.

text: Schuierer.

text: An

text: optimal

text: algorithm

text: for

text: the

text: rectilinear

text: link

text: center

text: of

text: a

text: rectilinear

text: polygon.

text: Computational

text: Geometry:

text: Theory

text: and

text: Ap-

text: plications,

text: R.

text: Pollack,

text: M.

text: Sharir,

text: and

text: G.

text: Rote.

text: Computing

text: the

text: geodesic

text: center

text: of

text: a

text: simple

text: polygon.

text: Discrete

text: Computational

text: Geometry,

text: S.

text: Suri.

text: Minimum

text: Link

text: Paths

text: in

text: Polygons

text: and

text: Related

text: Problems.

text: PhD

text: thesis,

text: Johns

text: Hopkins

text: Univ.,

text: S.

text: Suri.

text: Computing

text: geodesic

text: furthest

text: neighbors

text: in

text: simple

text: polygons.

text: Journal

text: of

text: Computer

text: and

text: System

text: Sciences,


text: ∗ − Note that t = 1 gives time of O (2(1 ab )k+ab l). For ﬁxed values of a and b, it is easy to ﬁnd optimal value of t in Theorem 4.5. The following equivalence is well-known (see e.g. [16]). ≤ Proposition 4.6 (folklore). Graph G has fractional chromatic number χ (G) r iﬀ there f exists a probability distribution π on the independent sets of G such that for each vertex v, the probability that v is contained in a random independent set (with respect to π) is at least 1/r. Proposition 4.6 is interesting because an upper bound B on the fractional chromatic number can be proven by providing a polynomial-time randomized algorithm which outputs ∈ an independent set I such that, for every vertex v, the probability that v I is at least 1/B. This strategy was used e.g. by Ferguson et al. [16]. It is not hard to show that having such an algorithm one can build in randomized polynomial time an (a : b)-coloring of G such that a = B + (cid:15) for arbitrary ﬁxed (cid:15) > 0. However, for our applications in (k, l)-tree this is not b needed as observed in the following lemma (the main observation behind this lemma traces back to Bj¨orklund[2], Theorem 2). Theorem 4.7. Assume there is a polynomial-time randomized algorithm A which outputs an ∈ independent set I such that, for every vertex v of G, the probability that v I is at least p, ∈ for some p (0, 1). Then, there is a Monte-Carlo polynomial space algorithm for ﬁnding a (k, l)-tree running in time ∗ − O (2(1 p)k+pl) which never reports a false positive, and reports false negatives with constant probability. (cid:100) − (cid:101) Proof. (Sketch.) Put r = (1 p) k + pl +1. Let T be a (k, l)-tree in G. Run the algorithm G \ A and let I be the resulting independent set. Put V = V I and V = I. It is easy to | | | ∩ | | ∩ | 1 − ≤2 − see that E( la(T ) ) = V (T ) V + L(T ) V = (1 p)k + pl r 1. By Markov’s | G | ≤ G 1 G 2 inequality, Pr( la(T ) r) = Ω(1) = Ω(1). We run the algorithm from Lemma 2.8 and it G r k ﬁnds a (k, l)-tree with probability Ω(1). By repeating the whole procedure O(k) times, we k can increase the success probability to a positive constant. 4.3 Vector Coloring A vector coloring of a graph G on n vertices of value r > 1 is an assignment of unit length R · ≤ − − vectors v in n for each vertex u so that for every edge uv, v v 1/(r 1). The vector u u v chromatic number χ (G) is the smallest real r admitting a vector coloring. v Once we have a vector coloring, we can use a random hyperplane through the origin with normal h chosen uniformly over the surface of the unit hypersphere to divide the vertices in · ≥ V and V : For vertex u, we put u in V if v h 0; otherwise, we put it in V . 1 2 1 u 2 By the linearity of expectation, we can upper bound the expected number of labels as the expected number of vertices put in V , which is half of them, plus an upper bound of the 1 expected number of edges in the tree that have both endpoints in V , which depend on the 2 angle between these two vertices’ vectors. The vector coloring value gives us a lower bound on the size of this angle. Paraphrasing Lemma 3.2 in Goemans and Williamson [23], we have Lemma 4.8. For a random hyperplane normal h and two vectors v and v , we have u v · (cid:54) · 1 · Pr(sign(v h) = sign(v h)) = arccos(v v ). u v u v π 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: Note

text: that

text: t

text: gives

text: time

text: of

text: O

text: ab

text: )k+ab

text: l).

text: For

text: ﬁxed

text: values

text: of

text: a

text: and

text: b,

text: it

text: is

text: easy

text: to

text: ﬁnd

text: optimal

text: value

text: of

text: t

text: in

text: Theorem

text: The

text: following

text: equivalence

text: is

text: well-known

text: (see

text: e.g.

text: Proposition

text: (folklore).

text: Graph

text: G

text: has

text: fractional

text: chromatic

text: number

text: χ

text: (G)

text: r

text: iﬀ

text: there

text: f

text: exists

text: a

text: probability

text: distribution

text: π

text: on

text: the

text: independent

text: sets

text: of

text: G

text: such

text: that

text: for

text: each

text: vertex

text: v,

text: the

text: probability

text: that

text: v

text: is

text: contained

text: in

text: a

text: random

text: independent

text: set

text: (with

text: respect

text: to

text: π)

text: is

text: at

text: least

text: Proposition

text: is

text: interesting

text: because

text: an

text: upper

text: bound

text: B

text: on

text: the

text: fractional

text: chromatic

text: number

text: can

text: be

text: proven

text: by

text: providing

text: a

text: polynomial-time

text: randomized

text: algorithm

text: which

text: outputs

text: an

text: independent

text: set

text: I

text: such

text: that,

text: for

text: every

text: vertex

text: v,

text: the

text: probability

text: that

text: v

text: I

text: is

text: at

text: least

text: This

text: strategy

text: was

text: used

text: e.g.

text: by

text: Ferguson

text: et

text: al.

text: It

text: is

text: not

text: hard

text: to

text: show

text: that

text: having

text: such

text: an

text: algorithm

text: one

text: can

text: build

text: in

text: randomized

text: polynomial

text: time

text: an

text: (a

text: b)-coloring

text: of

text: G

text: such

text: that

text: a

text: B

text: for

text: arbitrary

text: ﬁxed

text: However,

text: for

text: our

text: applications

text: in

text: (k,

text: l)-tree

text: this

text: is

text: not

text: b

text: needed

text: as

text: observed

text: in

text: the

text: following

text: lemma

text: (the

text: main

text: observation

text: behind

text: this

text: lemma

text: traces

text: back

text: to

text: Theorem

text: Theorem

text: Assume

text: there

text: is

text: a

text: polynomial-time

text: randomized

text: algorithm

text: A

text: which

text: outputs

text: an

text: independent

text: set

text: I

text: such

text: that,

text: for

text: every

text: vertex

text: v

text: of

text: G,

text: the

text: probability

text: that

text: v

text: I

text: is

text: at

text: least

text: p,

text: for

text: some

text: p

text: Then,

text: there

text: is

text: a

text: Monte-Carlo

text: polynomial

text: space

text: algorithm

text: for

text: ﬁnding

text: a

text: (k,

text: l)-tree

text: running

text: in

text: time

text: O

text: p)k+pl)

text: which

text: never

text: reports

text: a

text: false

text: positive,

text: and

text: reports

text: false

text: negatives

text: with

text: constant

text: probability.

text: Proof.

text: (Sketch.)

text: Put

text: r

text: p)

text: k

text: pl

text: Let

text: T

text: be

text: a

text: (k,

text: l)-tree

text: in

text: G.

text: Run

text: the

text: algorithm

text: G

text: A

text: and

text: let

text: I

text: be

text: the

text: resulting

text: independent

text: set.

text: Put

text: V

text: V

text: I

text: and

text: V

text: I.

text: It

text: is

text: easy

text: to

text: ≤2

text: see

text: that

text: E(

text: la(T

text: V

text: (T

text: V

text: L(T

text: V

text: p)k

text: pl

text: r

text: By

text: Markov’s

text: G

text: G

text: G

text: inequality,

text: Pr(

text: la(T

text: r)

text: We

text: run

text: the

text: algorithm

text: from

text: Lemma

text: and

text: it

text: G

text: r

text: k

text: ﬁnds

text: a

text: (k,

text: l)-tree

text: with

text: probability

text: By

text: repeating

text: the

text: whole

text: procedure

text: O(k)

text: times,

text: we

text: k

text: can

text: increase

text: the

text: success

text: probability

text: to

text: a

text: positive

text: constant.

text: Vector

text: Coloring

text: A

text: vector

text: coloring

text: of

text: a

text: graph

text: G

text: on

text: n

text: vertices

text: of

text: value

text: r

text: is

text: an

text: assignment

text: of

text: unit

text: length

text: R

text: vectors

text: v

text: in

text: n

text: for

text: each

text: vertex

text: u

text: so

text: that

text: for

text: every

text: edge

text: uv,

text: v

text: v

text: The

text: vector

text: u

text: u

text: v

text: chromatic

text: number

text: χ

text: (G)

text: is

text: the

text: smallest

text: real

text: r

text: admitting

text: a

text: vector

text: coloring.

text: v

text: Once

text: we

text: have

text: a

text: vector

text: coloring,

text: we

text: can

text: use

text: a

text: random

text: hyperplane

text: through

text: the

text: origin

text: with

text: normal

text: h

text: chosen

text: uniformly

text: over

text: the

text: surface

text: of

text: the

text: unit

text: hypersphere

text: to

text: divide

text: the

text: vertices

text: in

text: V

text: and

text: V

text: For

text: vertex

text: u,

text: we

text: put

text: u

text: in

text: V

text: if

text: v

text: h

text: otherwise,

text: we

text: put

text: it

text: in

text: V

text: u

text: By

text: the

text: linearity

text: of

text: expectation,

text: we

text: can

text: upper

text: bound

text: the

text: expected

text: number

text: of

text: labels

text: as

text: the

text: expected

text: number

text: of

text: vertices

text: put

text: in

text: V

text: which

text: is

text: half

text: of

text: them,

text: plus

text: an

text: upper

text: bound

text: of

text: the

text: expected

text: number

text: of

text: edges

text: in

text: the

text: tree

text: that

text: have

text: both

text: endpoints

text: in

text: V

text: which

text: depend

text: on

text: the

text: angle

text: between

text: these

text: two

text: vertices’

text: vectors.

text: The

text: vector

text: coloring

text: value

text: gives

text: us

text: a

text: lower

text: bound

text: on

text: the

text: size

text: of

text: this

text: angle.

text: Paraphrasing

text: Lemma

text: in

text: Goemans

text: and

text: Williamson

text: we

text: have

text: Lemma

text: For

text: a

text: random

text: hyperplane

text: normal

text: h

text: and

text: two

text: vectors

text: v

text: and

text: v

text: we

text: have

text: u

text: v

text: Pr(sign(v

text: h)

text: sign(v

text: h))

text: arccos(v

text: v

text: u

text: v

text: u

text: v

text: π

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:18) (cid:19) Hence we have − − − | | ≤ k + l − arccos( 1/(r 1)) k 1 E( la(T ) ) + 1 . G 2 π 2 | | By Markov’s inequality and by using that la(T ) is an integer quantity, we see that such a G random hyperplane gives us at most the expected number of labels with probability at least | | | | 1/(E( la(T ) )+1). If we pick E( la(T ) )+1) hyperplanes independently of each other, with G − − G | | | | probability at least 1 e 1 one of them will use at most E( la(T ) ) labels. Since E( la(T ) ) G G is a polynomial in k, we can run Lemma 2.8 for each hyperplane to obtain the following algorithm guarantee. Theorem 4.9. Assume we are given a vector coloring of the host graph of some value r. Then the(cid:18)re is a Monte-Carlo polynomi(cid:19)al space algorithm for ﬁnding a (k, l)-tree running in (cid:16) (cid:16) (cid:17) (cid:17) time ∗ k+l+ 1−arccos(−1/(r−1)) k−1 O 2 2 π 2 which never reports a false positive, and reports false negatives with constant probability. 5 Corollaries 5.1 Solving (k, l)-Tree and k-IST in Bounded Degree Graphs For a graph of bounded degree ∆ that is neither complete nor an odd cycle, it is possible to construct a proper ∆-coloring in linear time (e.g., by Lov´asz’s proof of Brooks’ theorem [33]). Note that, given a graph that is either complete or an odd cycle, (k, l)-Tree can clearly be (cid:18) (cid:19) solved in polynomial time. In conjunction wi(cid:16)th Theore(cid:17)m 4.3, this yields the following result. Corollary 5.1. There is a Monte-Carlo polynomial space algorithm for (k, l)-Tree in graphs ∗ 1− x(∆−−x) (cid:32)k+(cid:18)(1− x )l (cid:19) (cid:33) (cid:98)∆+(l/k)(∆−1)(cid:101) of bounded degree ∆ which runs in time O 2 ∆(∆ 1) ∆ , where x = . 2 −(cid:98)∆(cid:99)(cid:100)∆(cid:101) ∗ 1 2 −2 k+ l In particular, the running time can be bounded by O 2 ∆(∆ 1) 2 . With l = 2, the same result holds for k-Path, and with k = n, for Hamiltonicity. ∗ In particular, if ∆ < 13 we get k-Path and Hamiltonicity algorithms in O (1.655k) ∗ and O (1.655n) time, respectively, that are faster than the algorithms from [4, 2]. As shown in [44], a graph G of bounded degree ∆ has a spanning tree with at least k − − inte(cid:18)rnal vertices iﬀ it contains a tree wi(cid:19)th exactly k internal vertices and at most k k−2 = − (cid:16) (cid:17) ∆ 1 ∆−2k + O(1) leaves.3 Therefore, by the above corollary,4 we can solve k-IST in time ∆ 1 O∗ 2 1−∆x((∆∆−−x1)) (1+∆∆−−21)k+(1−∆x )(∆∆−−21)k , where x = (cid:98)3∆2−6−∆+2(cid:101). That is, we can solve 2(2∆ 3) 3For graphs with a small bounded degree, this bound is better than the one of Strategy A in Section (i.e., ≤ ≤ ≤ l 0.8628k). Indeed, for ∆ 8, this bound implies that l 0.8572k. 4Note that now, in the context of k-IST, k is the number of internal vertices, where in Corollary 5.1, it is the total number of vertices. 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Hence

text: we

text: have

text: k

text: l

text: arccos(

text: k

text: E(

text: la(T

text: G

text: π

text: By

text: Markov’s

text: inequality

text: and

text: by

text: using

text: that

text: la(T

text: is

text: an

text: integer

text: quantity,

text: we

text: see

text: that

text: such

text: a

text: G

text: random

text: hyperplane

text: gives

text: us

text: at

text: most

text: the

text: expected

text: number

text: of

text: labels

text: with

text: probability

text: at

text: least

text: la(T

text: If

text: we

text: pick

text: E(

text: la(T

text: hyperplanes

text: independently

text: of

text: each

text: other,

text: with

text: G

text: G

text: probability

text: at

text: least

text: e

text: one

text: of

text: them

text: will

text: use

text: at

text: most

text: E(

text: la(T

text: labels.

text: Since

text: E(

text: la(T

text: G

text: G

text: is

text: a

text: polynomial

text: in

text: k,

text: we

text: can

text: run

text: Lemma

text: for

text: each

text: hyperplane

text: to

text: obtain

text: the

text: following

text: algorithm

text: guarantee.

text: Theorem

text: Assume

text: we

text: are

text: given

text: a

text: vector

text: coloring

text: of

text: the

text: host

text: graph

text: of

text: some

text: value

text: r.

text: Then

text: is

text: a

text: Monte-Carlo

text: space

text: algorithm

text: for

text: ﬁnding

text: a

text: (k,

text: l)-tree

text: running

text: in

text: time

text: k+l+

text: O

text: π

text: which

text: never

text: reports

text: a

text: false

text: positive,

text: and

text: reports

text: false

text: negatives

text: with

text: constant

text: probability.

text: Corollaries

text: Solving

text: (k,

text: l)-Tree

text: and

text: k-IST

text: in

text: Bounded

text: Degree

text: Graphs

text: For

text: a

text: graph

text: of

text: bounded

text: degree

text: that

text: is

text: neither

text: complete

text: nor

text: an

text: odd

text: cycle,

text: it

text: is

text: possible

text: to

text: construct

text: a

text: proper

text: ∆-coloring

text: in

text: linear

text: time

text: (e.g.,

text: by

text: Lov´asz’s

text: proof

text: of

text: Brooks’

text: theorem

text: Note

text: that,

text: given

text: a

text: graph

text: that

text: is

text: either

text: complete

text: or

text: an

text: odd

text: cycle,

text: (k,

text: l)-Tree

text: can

text: clearly

text: be

text: solved

text: in

text: polynomial

text: time.

text: In

text: conjunction

text: this

text: yields

text: the

text: following

text: result.

text: Corollary

text: There

text: is

text: a

text: Monte-Carlo

text: polynomial

text: space

text: algorithm

text: for

text: (k,

text: l)-Tree

text: in

text: graphs

text: 1−

text: x(∆−−x)

text: x

text: )l

text: of

text: bounded

text: degree

text: which

text: runs

text: in

text: time

text: O

text: where

text: x

text: −2

text: k+

text: l

text: In

text: particular,

text: the

text: running

text: time

text: can

text: be

text: bounded

text: by

text: O

text: With

text: l

text: the

text: same

text: result

text: holds

text: for

text: k-Path,

text: and

text: with

text: k

text: n,

text: for

text: Hamiltonicity.

text: In

text: particular,

text: if

text: we

text: get

text: k-Path

text: and

text: Hamiltonicity

text: algorithms

text: in

text: O

text: and

text: O

text: time,

text: respectively,

text: that

text: are

text: faster

text: than

text: the

text: algorithms

text: from

text: As

text: shown

text: in

text: a

text: graph

text: G

text: of

text: bounded

text: degree

text: has

text: a

text: spanning

text: tree

text: with

text: at

text: least

text: k

text: vertices

text: iﬀ

text: it

text: contains

text: a

text: tree

text: exactly

text: k

text: internal

text: vertices

text: and

text: at

text: most

text: k

text: ∆−2k

text: Therefore,

text: by

text: the

text: above

text: we

text: can

text: solve

text: k-IST

text: in

text: time

text: O∗

text: where

text: x

text: That

text: is,

text: we

text: can

text: solve

text: graphs

text: with

text: a

text: small

text: bounded

text: degree,

text: this

text: bound

text: is

text: better

text: than

text: the

text: one

text: of

text: Strategy

text: A

text: in

text: Section

text: (i.e.,

text: l

text: Indeed,

text: for

text: this

text: bound

text: implies

text: that

text: l

text: that

text: now,

text: in

text: the

text: context

text: of

text: k-IST,

text: k

text: is

text: the

text: number

text: of

text: internal

text: vertices,

text: where

text: in

text: Corollary

text: it

text: is

text: the

text: total

text: number

text: of

text: vertices.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∆ Running Time ∗ χ (G) Running Time 3 O (1.5705k) v ∗ ∗ ∗ 4 O (1.6199k) 4 O (22k/3) = O (1.5874k) ∗ ∗ ∗ 5 O (1.6356k) 5, 6 O (27k/10) = O (1.6245k) ∗ ∗ ∗ 6 O (1.6448k) 7, 8 O (25k/7) = O (1.6406k) ∗ ∗ ∗ 7 O (1.6510k) 9, 10 O (213k/18) = O (1.6497k) ∗ ∗ ∗ 8 O (1.6554k) 11, 12 O (28k/11) = O (1.6555k) Table 2: Running times of our k-Path algorithm in bounded degree graphs (left), and bounded vector chromatic number (right). Replacing k by n gives bounds for Hamiltonic- ity. the distribution of this variable (Lemma 2.10), and again this turned out to be much more tricky than in the path case. The (k, l)-Tree algorithm described above already implies an improved running time for k-IST in general graphs. However, it works much faster if the hidden spannning tree has few leaves. We design a diﬀerent strategy, based on ﬁnding a maximum matching, to accelerate the algorithm when it looks for solutions with many leaves. By merging the two strategies, ∗ ∗ − we obtain an O (3.455k) time algorithm for k-IST. This is the ﬁrst O ((4 Ω(1))k)-time algorithm that uses polynomial space. It immediately implies a moderately exponential time ∗ ∗ algorithm running in time O (1.946n), which breaks the O (2n) barrier. Paths and Trees in Colored Graphs. Next, we study the (k, l)-Tree problem in graphs that admit a vertex coloring with d colors. This can be seen as an extension of Bj¨orklund’s ∗ O (2n/2)-time algorithm for Hamiltonicity in bipartite graphs [2]. However, the insight in [2] was to ﬁnd a small vertex cover of the hidden solution. Here, we use a diﬀerent insight: by choosing roughly half of the color classes we get a small subset of the hidden solution vertices which covers many (but not all) of its edges. The resulting algorithm runs ∗ (1−(cid:98)d/2(cid:99)−(cid:100)d/2(cid:101))k in O (2 d(d 1) ) time when l = O(1) (see Section for a more complicated bound in the general case). For a graph of bounded degree ∆ that is neither complete nor an odd cycle, it is possible to construct a proper ∆-coloring in linear time (e.g., by Lov´asz’s proof of Brooks’ theorem [33]). This immediately results in a fast algorithm for (k, l)-Tree in bounded degree graphs (see Table 2 for the special cases of k-Path and Hamiltonicity; the case ∆ = 3 is solved by a special algorithm, see below), along with an improved algorithm for k-IST in such graphs (see Table 3 in Section ). Fractional coloring is a well studied generalization of the classical vertex coloring. Our algorithm for graphs of low chromatic number generalizes quite easily to the case of low frac- tional chromatic number. This has consequences in improved algorithms for some special ∗ graph classes, e.g. an O (1.571k1.274l)-time algorithm for (k, l)-Tree in subcubic triangle- ∗ free graphs, or O (1.571k)-time algorithm for k-Path in general subcubic graphs. For sub- cubic graphs of even larger girth, we get further improved bounds. Another relaxation of the classical coloring is vector coloring, known for its importance in approximation algorithms (e.g. [23]). Its important advantage is that, contrary to the classical or fractional coloring, a (1 + (cid:15))-approximation can be found in polynomial time [21]. We provide an algorithm for (k, l)-Tree that applies vector coloring. It results in improved running time when the vector chromatic number is at most 8. 4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: table

text: Running

text: Time

text: χ

text: (G)

text: Running

text: Time

text: O

text: v

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: O

text: Table

text: Running

label: caption

text: times

text: of

text: our

text: k-Path

text: algorithm

text: in

text: bounded

text: degree

text: graphs

text: (left),

text: and

text: bounded

text: vector

text: chromatic

text: number

text: (right).

text: Replacing

text: k

text: by

text: n

text: gives

text: bounds

text: for

text: Hamiltonic-

text: ity.

text: the

text: distribution

text: of

text: this

text: variable

text: (Lemma

text: and

text: again

text: this

text: turned

text: out

text: to

text: be

text: much

text: more

text: tricky

text: than

text: in

text: the

text: path

text: case.

text: The

text: (k,

text: l)-Tree

text: algorithm

text: described

text: above

text: already

text: implies

text: an

text: improved

text: running

text: time

text: for

text: k-IST

text: in

text: general

text: graphs.

text: However,

text: it

text: works

text: much

text: faster

text: if

text: the

text: hidden

text: spannning

text: tree

text: has

text: few

text: leaves.

text: We

text: design

text: a

text: diﬀerent

text: strategy,

text: based

text: on

text: ﬁnding

text: a

text: maximum

text: matching,

text: to

text: accelerate

text: the

text: algorithm

text: when

text: it

text: looks

text: for

text: solutions

text: with

text: many

text: leaves.

text: By

text: merging

text: the

text: two

text: strategies,

text: we

text: obtain

text: an

text: O

text: time

text: algorithm

text: for

text: k-IST.

text: This

text: is

text: the

text: ﬁrst

text: O

text: algorithm

text: that

text: uses

text: polynomial

text: space.

text: It

text: immediately

text: implies

text: a

text: moderately

text: exponential

text: time

text: algorithm

text: running

text: in

text: time

text: O

text: which

text: breaks

text: the

text: O

text: barrier.

text: Paths

text: and

text: Trees

text: in

text: Colored

text: Graphs.

text: Next,

text: we

text: study

text: the

text: (k,

text: l)-Tree

text: problem

text: in

text: graphs

text: that

text: admit

text: a

text: vertex

text: coloring

text: with

text: d

text: colors.

text: This

text: can

text: be

text: seen

text: as

text: an

text: extension

text: of

text: Bj¨orklund’s

text: O

text: algorithm

text: for

text: Hamiltonicity

text: in

text: bipartite

text: graphs

text: However,

text: the

text: insight

text: in

text: was

text: to

text: ﬁnd

text: a

text: small

text: vertex

text: cover

text: of

text: the

text: hidden

text: solution.

text: Here,

text: we

text: use

text: a

text: diﬀerent

text: insight:

text: by

text: choosing

text: roughly

text: half

text: of

text: the

text: color

text: classes

text: we

text: get

text: a

text: small

text: subset

text: of

text: the

text: hidden

text: solution

text: vertices

text: which

text: covers

text: many

text: (but

text: not

text: all)

text: of

text: its

text: edges.

text: The

text: resulting

text: algorithm

text: runs

text: in

text: O

text: d(d

text: time

text: when

text: l

text: (see

text: Section

text: for

text: a

text: more

text: complicated

text: bound

text: in

text: the

text: general

text: case).

text: For

text: a

text: graph

text: of

text: bounded

text: degree

text: that

text: is

text: neither

text: complete

text: nor

text: an

text: odd

text: cycle,

text: it

text: is

text: possible

text: to

text: construct

text: a

text: proper

text: ∆-coloring

text: in

text: linear

text: time

text: (e.g.,

text: by

text: Lov´asz’s

text: proof

text: of

text: Brooks’

text: theorem

text: This

text: immediately

text: results

text: in

text: a

text: fast

text: algorithm

text: for

text: (k,

text: l)-Tree

text: in

text: bounded

text: degree

text: graphs

text: (see

text: Table

text: for

text: the

text: special

text: cases

text: of

text: k-Path

text: and

text: Hamiltonicity;

text: the

text: case

text: is

text: solved

text: by

text: a

text: special

text: algorithm,

text: see

text: below),

text: along

text: with

text: an

text: improved

text: algorithm

text: for

text: k-IST

text: in

text: such

text: graphs

text: (see

text: Table

text: in

text: Section

text: Fractional

text: coloring

text: is

text: a

text: well

text: studied

text: generalization

text: of

text: the

text: classical

text: vertex

text: coloring.

text: Our

text: algorithm

text: for

text: graphs

text: of

text: low

text: chromatic

text: number

text: generalizes

text: quite

text: easily

text: to

text: the

text: case

text: of

text: low

text: frac-

text: tional

text: chromatic

text: number.

text: This

text: has

text: consequences

text: in

text: improved

text: algorithms

text: for

text: some

text: special

text: graph

text: classes,

text: e.g.

text: an

text: O

text: algorithm

text: for

text: (k,

text: l)-Tree

text: in

text: subcubic

text: triangle-

text: free

text: graphs,

text: or

text: O

text: algorithm

text: for

text: k-Path

text: in

text: general

text: subcubic

text: graphs.

text: For

text: sub-

text: cubic

text: graphs

text: of

text: even

text: larger

text: girth,

text: we

text: get

text: further

text: improved

text: bounds.

text: Another

text: relaxation

text: of

text: the

text: classical

text: coloring

text: is

text: vector

text: coloring,

text: known

text: for

text: its

text: importance

text: in

text: approximation

text: algorithms

text: (e.g.

text: Its

text: important

text: advantage

text: is

text: that,

text: contrary

text: to

text: the

text: classical

text: or

text: fractional

text: coloring,

text: a

text: can

text: be

text: found

text: in

text: polynomial

text: time

text: We

text: provide

text: an

text: algorithm

text: for

text: (k,

text: l)-Tree

text: that

text: applies

text: vector

text: coloring.

text: It

text: results

text: in

text: improved

text: running

text: time

text: when

text: the

text: vector

text: chromatic

text: number

text: is

text: at

text: most

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1.3 Notation (cid:0) (cid:1) Throughout the paper we consider undirected graphs. For an integer k, by [k] we denote { } the set 1, 2, . . . , k . For a set S and an integer k by S we denote the family of all subsets k of S of size k. Let us write V = V (G) = [n] for the vertex set and E = E(G) for the edge set of the host graph G. 2 Finding Trees on k Vertices with l Leaves In this section we generalize the k-Path algorithm by Bj¨orklund et al. [2, 4] to ﬁnding subtrees with k nodes including l leaves. We focus on undirected graphs. Throughout this ∪ section we assume we are given a ﬁxed partition V = V V of the vertices of the input graph. 1 2 To get the promised generalization, in Section we will use a random bipartition, similarly as in [2, 4]. In the next sections we investigate other partitions. 2.1 Branching Walks → The notion of branching walk was introduced by Nederlof [35]. A mapping h : V (T ) { } ∈ V (G) is a homomorphism from a graph T to the host G if for all a, b E(T ) it holds that { } ∈ h(a), h(b) E(G). We adopt the convention of calling the elements of V (T ) nodes and the elements of V (G) vertices. A branching walk in G is a pair B = (T, h) where T is an unordered rooted tree and → h : V (T ) V (G) is a homomorphism from T to G. Let B = (T, h) be a branching walk in G.The walk starts from the vertex h(1) in G. The | | size of the walk is V (T ) . The walk is simple if h is injective. The walk is weakly simple ∈ if for any node x V (T ), the homomorphism h is injective on children of x. The walk is U-turn-free if for any node a of T , every child b of a maps to a diﬀerent vertex than the parent (cid:54) c of a, i.e., h(b) = h(c). → { | |} A proper order of B is any permutation π : V (T ) 1, . . . , V (T ) such that for every ∈ two nodes a, b V (T ), (i) if depth(a) < depth(b) then π(a) < π(b), (cid:54) (ii) if a, b = root(T ) and π(parent(a)) < π(parent(b)) then π(a) < π(b), (iii) if a and b are siblings and h(a) < h(b) then π(a) < π(b). The following proposition is immediate. Proposition 2.1. Every weakly simple branching walk has exactly one proper order. { | |} We say that a weakly simple branching walk B is properly ordered if V (T ) = 1, . . . , V (T ) and the proper order from Proposition 2.1 is the identity function. 2.2 Labeling For a tree T , by L(T ) we note the set of leaves of T and by I(T ) we denote the set of \ internal vertices of T , i.e., I(T ) = V (T ) L(T ). Like in [4] or [5] our crucial tool are labelled branching walks. In [5], every node in the tree T of a branching walk (T, h) was assigned a label. Here, similarly as in [4], we do not assign labels to some nodes, but we assign labels to some edges of T . We deﬁne the set of labellable elements of a branching walk B = (T, h) as 5

label: section

text: Notation

text: Throughout

text: the

text: paper

text: we

text: consider

text: undirected

text: graphs.

text: For

text: an

text: integer

text: k,

text: by

text: [k]

text: we

text: denote

text: the

text: set

text: k

text: For

text: a

text: set

text: S

text: and

text: an

text: integer

text: k

text: by

text: S

text: we

text: denote

text: the

text: family

text: of

text: all

text: subsets

text: k

text: of

text: S

text: of

text: size

text: k.

text: Let

text: us

text: write

text: V

text: V

text: (G)

text: [n]

text: for

text: the

text: vertex

text: set

text: and

text: E

text: E(G)

text: for

text: the

text: edge

text: set

text: of

text: the

text: host

text: graph

text: G.

text: Finding

text: Trees

text: on

text: k

text: Vertices

text: with

text: l

text: Leaves

text: In

text: this

text: section

text: we

text: generalize

text: the

text: k-Path

text: algorithm

text: by

text: Bj¨orklund

text: et

text: al.

text: to

text: ﬁnding

text: subtrees

text: with

text: k

text: nodes

text: including

text: l

text: leaves.

text: We

text: focus

text: on

text: undirected

text: graphs.

text: Throughout

text: this

text: section

text: we

text: assume

text: we

text: are

text: given

text: a

text: ﬁxed

text: partition

text: V

text: V

text: V

text: of

text: the

text: vertices

text: of

text: the

text: input

text: graph.

text: To

text: get

text: the

text: promised

text: generalization,

text: in

text: Section

text: we

text: will

text: use

text: a

text: random

text: bipartition,

text: similarly

text: as

text: in

text: In

text: the

text: next

text: sections

text: we

text: investigate

text: other

text: partitions.

text: Branching

text: Walks

text: The

text: notion

text: of

text: branching

text: walk

text: was

text: introduced

text: by

text: Nederlof

text: A

text: mapping

text: h

text: V

text: (T

text: V

text: (G)

text: is

text: a

text: homomorphism

text: from

text: a

text: graph

text: T

text: to

text: the

text: host

text: G

text: if

text: for

text: all

text: a,

text: b

text: E(T

text: it

text: holds

text: that

text: h(a),

text: h(b)

text: E(G).

text: We

text: adopt

text: the

text: convention

text: of

text: calling

text: the

text: elements

text: of

text: V

text: (T

text: nodes

text: and

text: the

text: elements

text: of

text: V

text: (G)

text: vertices.

text: A

text: branching

text: walk

text: in

text: G

text: is

text: a

text: pair

text: B

text: (T,

text: h)

text: where

text: T

text: is

text: an

text: unordered

text: rooted

text: tree

text: and

text: h

text: V

text: (T

text: V

text: (G)

text: is

text: a

text: homomorphism

text: from

text: T

text: to

text: G.

text: Let

text: B

text: (T,

text: h)

text: be

text: a

text: branching

text: walk

text: in

text: G.The

text: walk

text: starts

text: from

text: the

text: vertex

text: in

text: G.

text: The

text: size

text: of

text: the

text: walk

text: is

text: V

text: (T

text: The

text: walk

text: is

text: simple

text: if

text: h

text: is

text: injective.

text: The

text: walk

text: is

text: weakly

text: simple

text: if

text: for

text: any

text: node

text: x

text: V

text: (T

text: the

text: homomorphism

text: h

text: is

text: injective

text: on

text: children

text: of

text: x.

text: The

text: walk

text: is

text: U-turn-free

text: if

text: for

text: any

text: node

text: a

text: of

text: T

text: every

text: child

text: b

text: of

text: a

text: maps

text: to

text: a

text: diﬀerent

text: vertex

text: than

text: the

text: parent

text: c

text: of

text: a,

text: i.e.,

text: h(b)

text: h(c).

text: A

text: proper

text: order

text: of

text: B

text: is

text: any

text: permutation

text: π

text: V

text: (T

text: V

text: (T

text: such

text: that

text: for

text: every

text: two

text: nodes

text: a,

text: b

text: V

text: (T

text: (i)

text: if

text: depth(a)

text: depth(b)

text: then

text: π(a)

text: π(b),

text: (ii)

text: if

text: a,

text: b

text: root(T

text: and

text: π(parent(a))

text: π(parent(b))

text: then

text: π(a)

text: π(b),

text: (iii)

text: if

text: a

text: and

text: b

text: are

text: siblings

text: and

text: h(a)

text: h(b)

text: then

text: π(a)

text: π(b).

text: The

text: following

text: proposition

text: is

text: immediate.

text: Proposition

text: Every

text: weakly

text: simple

text: branching

text: walk

text: has

text: exactly

text: one

text: proper

text: order.

text: We

text: say

text: that

text: a

text: weakly

text: simple

text: branching

text: walk

text: B

text: is

text: properly

text: ordered

text: if

text: V

text: (T

text: V

text: (T

text: and

text: the

text: proper

text: order

text: from

text: Proposition

text: is

text: the

text: identity

text: function.

text: Labeling

text: For

text: a

text: tree

text: T

text: by

text: L(T

text: we

text: note

text: the

text: set

text: of

text: leaves

text: of

text: T

text: and

text: by

text: I(T

text: we

text: denote

text: the

text: set

text: of

text: internal

text: vertices

text: of

text: T

text: i.e.,

text: I(T

text: V

text: (T

text: L(T

text: Like

text: in

text: or

text: our

text: crucial

text: tool

text: are

text: labelled

text: branching

text: walks.

text: In

text: every

text: node

text: in

text: the

text: tree

text: T

text: of

text: a

text: branching

text: walk

text: (T,

text: h)

text: was

text: assigned

text: a

text: label.

text: Here,

text: similarly

text: as

text: in

text: we

text: do

text: not

text: assign

text: labels

text: to

text: some

text: nodes,

text: but

text: we

text: assign

text: labels

text: to

text: some

text: edges

text: of

text: T

text: We

text: deﬁne

text: the

text: set

text: of

text: labellable

text: elements

text: of

text: a

text: branching

text: walk

text: B

text: (T,

text: h)

text: as


text: (cid:48) (cid:54) Note that (cid:96) = (cid:96) because (cid:96) is injective. In this way, to the labelled branching walk (B, (cid:96)) we (cid:48) (cid:48) assigned another labelled branching walk (B, (cid:96) ). Note that mon(B, (cid:96)) = mon(B, (cid:96) ). Observe (cid:48) that (B, (cid:96) ) is also admissible and (k, l, i)-ﬁxed, and B is non-simple and falls into Case 1. (cid:48) Moreover, if we begin from (B, (cid:96) ) and follow the same way of assigning labels, we get (B, (cid:96)). Thus we have paired up all the non-simple labelled branching walks that fall into Case 1. In what follows we assume that Case 1 does not apply. Observe that once Case 1 is excluded, no two edges of T map to the same edge of G. Indeed, assume that there is a pair of edges u v and u v of T that map to the same edge ∈ 1 1 2 2 uv E(G), with h(u ) = h(u ) = u and h(v ) = h(v ) = v. Then, either one of u or v is in V 1 2 1 2 ∈ ∈ 1 or both are in V . By the deﬁnition of la(B), in the prior case u , u la(B), or v , v la(B) 2 ∈ 1 2 1 2 and in the latter case u v , u v la(B). In both situations Case 1 applies. 1 1 2 2 Deﬁne { ∈ } A = (u, v) : u, v V (T ) and h(u) = h(v) . ∈ Since Case 1 does not apply, and B is not simple, we know that for every pair (u, v) A at most one of u, v is in la(B). Let ∗ { ∈ } A = (u, v) A : h(u) = min h(x) . ∈ (x,y) A ∈ Consider any node x V (T ). Then, we deﬁne   ∈ (cid:96)(x) if x la(B), ↓ { ∈ ∩ } ∩ (cid:54) ∅ (cid:96) (x) = min (cid:96)(z) : z children(x) la(B) if children(x) la(B) = , { ∈ } min (cid:96)(xz) : z children(x) otherwise. ∈ ∗ Case 2. There is a pair (u, v) A such that u is an ancestor of v. Let us deﬁne a subset ∗∗ ⊆ ∗ ∈ ∗ A A consisting of pairs (u, v) A such that node u is an ancestor of v, and for every ∈ { } node x on the path from v to the root, if h(x) = h(u) then x u, v . We choose the ∈ ∗∗ ↓ pair (u, v) A such that the pair (u, (cid:96) (v)) is lexicographically minimal. Note that there is (cid:48) (cid:48) ∈ ∗∗ (cid:48) ↓ (cid:48) ↓ exactly one such pair. Indeed, consider another pair (u , v ) A with (u , (cid:96) (v )) = (u, (cid:96) (v)). (cid:48) (cid:54) (cid:48) ↓ ↓ (cid:48) (cid:48) Clearly, u = u . If v = v then, since (cid:96) (v) = (cid:96) (v ), it means that v is a child of v or vice (cid:48) versa. However, h(v) = h(v ), so h is not a homomorphism, a contradiction. (cid:48) Let T be the tree obtained from T by reversing the path from u to v. More precisely, · · · consider the path p = uu u v. Remove the edges uu and u v from T , obtaining three uv 1 t 1 t trees: T (rooted at root(T )), T (rooted at u ), and T (rooted at v). Next, root T at v , u (cid:48) p (cid:48) 1 v p t obtaining T . Finally, make the root of T the child of u in T , and make v the child of u in (cid:48) p (cid:48) p u 1 T . The resulting tree is denoted by T . p (cid:48) Note that the multigraphs h(T ) and h(T ) are equal. Now we essentially want to leave h (cid:48) (cid:48) unchanged; however the branching walk B = (T , h) is not properly ordered and we need to renumber the nodes. (cid:48) (cid:48) Note that B is weakly simple since no two edges of T (and hence also of T ) map to the (cid:48) (cid:48)(cid:48) same edge of G. Hence, by Proposition 2.1, there is exactly one proper order π of B . Let T (cid:48) (cid:48)(cid:48) be obtained from T by replacing every node x by π(x). Let us deﬁne homomorphism h by (cid:48)(cid:48) − ∈ (cid:48)(cid:48) (cid:48)(cid:48) (cid:48)(cid:48) (cid:48)(cid:48) (cid:48)(cid:48) h (x) = h(π 1(x)) for every x V (T ), and let B = (T , h ). Note that T has the same (cid:48)(cid:48) (cid:48)(cid:48) number of leaves and internal vertices as T and B is properly ordered. Also, T is weakly 7

font: default

text: Note

text: that

text: because

text: is

text: injective.

text: In

text: this

text: way,

text: to

text: the

text: labelled

text: branching

text: walk

text: (B,

text: we

text: assigned

text: another

text: labelled

text: branching

text: walk

text: (B,

text: Note

text: that

text: mon(B,

text: mon(B,

text: Observe

text: that

text: (B,

text: is

text: also

text: admissible

text: and

text: (k,

text: l,

text: i)-ﬁxed,

text: and

text: B

text: is

text: non-simple

text: and

text: falls

text: into

text: Case

text: Moreover,

text: if

text: we

text: begin

text: from

text: (B,

text: and

text: follow

text: the

text: same

text: way

text: of

text: assigning

text: labels,

text: we

text: get

text: (B,

text: Thus

text: we

text: have

text: paired

text: up

text: all

text: the

text: non-simple

text: labelled

text: branching

text: walks

text: that

text: fall

text: into

text: Case

text: In

text: what

text: follows

text: we

text: assume

text: that

text: Case

text: does

text: not

text: apply.

text: Observe

text: that

text: once

text: Case

text: is

text: excluded,

text: no

text: two

text: edges

text: of

text: T

text: map

text: to

text: the

text: same

text: edge

text: of

text: G.

text: Indeed,

text: assume

text: that

text: there

text: is

text: a

text: pair

text: of

text: edges

text: u

text: v

text: and

text: u

text: v

text: of

text: T

text: that

text: map

text: to

text: the

text: same

text: edge

text: uv

text: E(G),

text: with

text: h(u

text: h(u

text: u

text: and

text: h(v

text: h(v

text: v.

text: Then,

text: either

text: one

text: of

text: u

text: or

text: v

text: is

text: in

text: V

text: or

text: both

text: are

text: in

text: V

text: By

text: the

text: deﬁnition

text: of

text: la(B),

text: in

text: the

text: prior

text: case

text: u

text: u

text: la(B),

text: or

text: v

text: v

text: la(B)

text: and

text: in

text: the

text: latter

text: case

text: u

text: v

text: u

text: v

text: la(B).

text: In

text: both

text: situations

text: Case

text: applies.

text: Deﬁne

text: A

text: (u,

text: v)

text: u,

text: v

text: V

text: (T

text: and

text: h(u)

text: h(v)

text: Since

text: Case

text: does

text: not

text: apply,

text: and

text: B

text: is

text: not

text: simple,

text: we

text: know

text: that

text: for

text: every

text: pair

text: (u,

text: v)

text: A

text: at

text: most

text: one

text: of

text: u,

text: v

text: is

text: in

text: la(B).

text: Let

text: A

text: (u,

text: v)

text: A

text: h(u)

text: min

text: h(x)

text: (x,y)

text: A

text: Consider

text: any

text: node

text: x

text: V

text: (T

text: Then,

text: we

text: deﬁne

text: if

text: x

text: la(B),

text: (x)

text: min

text: z

text: children(x)

text: la(B)

text: if

text: children(x)

text: la(B)

text: min

text: z

text: children(x)

text: otherwise.

text: Case

text: There

text: is

text: a

text: pair

text: (u,

text: v)

text: A

text: such

text: that

text: u

text: is

text: an

text: ancestor

text: of

text: v.

text: Let

text: us

text: deﬁne

text: a

text: subset

text: A

text: A

text: consisting

text: of

text: pairs

text: (u,

text: v)

text: A

text: such

text: that

text: node

text: u

text: is

text: an

text: ancestor

text: of

text: v,

text: and

text: for

text: every

text: node

text: x

text: on

text: the

text: path

text: from

text: v

text: to

text: the

text: root,

text: if

text: h(x)

text: h(u)

text: then

text: x

text: u,

text: v

text: We

text: choose

text: the

text: pair

text: (u,

text: v)

text: A

text: such

text: that

text: the

text: pair

text: (u,

text: (v))

text: is

text: lexicographically

text: minimal.

text: Note

text: that

text: there

text: is

text: exactly

text: one

text: such

text: pair.

text: Indeed,

text: consider

text: another

text: pair

text: (u

text: v

text: A

text: with

text: (u

text: (v

text: (u,

text: (v)).

text: Clearly,

text: u

text: u

text: If

text: v

text: v

text: then,

text: since

text: (v)

text: (v

text: it

text: means

text: that

text: v

text: is

text: a

text: child

text: of

text: v

text: or

text: vice

text: versa.

text: However,

text: h(v)

text: h(v

text: so

text: h

text: is

text: not

text: a

text: homomorphism,

text: a

text: contradiction.

text: Let

text: T

text: be

text: the

text: tree

text: obtained

text: from

text: T

text: by

text: reversing

text: the

text: path

text: from

text: u

text: to

text: v.

text: More

text: precisely,

text: consider

text: the

text: path

text: p

text: uu

text: u

text: v.

text: Remove

text: the

text: edges

text: uu

text: and

text: u

text: v

text: from

text: T

text: obtaining

text: three

text: uv

text: t

text: t

text: trees:

text: T

text: (rooted

text: at

text: root(T

text: T

text: (rooted

text: at

text: u

text: and

text: T

text: (rooted

text: at

text: v).

text: Next,

text: root

text: T

text: at

text: v

text: u

text: p

text: v

text: p

text: t

text: obtaining

text: T

text: Finally,

text: make

text: the

text: root

text: of

text: T

text: the

text: child

text: of

text: u

text: in

text: T

text: and

text: make

text: v

text: the

text: child

text: of

text: u

text: in

text: p

text: p

text: u

text: T

text: The

text: resulting

text: tree

text: is

text: denoted

text: by

text: T

text: p

text: Note

text: that

text: the

text: multigraphs

text: h(T

text: and

text: h(T

text: are

text: equal.

text: Now

text: we

text: essentially

text: want

text: to

text: leave

text: h

text: unchanged;

text: however

text: the

text: branching

text: walk

text: B

text: (T

text: h)

text: is

text: not

text: properly

text: ordered

text: and

text: we

text: need

text: to

text: renumber

text: the

text: nodes.

text: Note

text: that

text: B

text: is

text: weakly

text: simple

text: since

text: no

text: two

text: edges

text: of

text: T

text: (and

text: hence

text: also

text: of

text: T

text: map

text: to

text: the

text: same

text: edge

text: of

text: G.

text: Hence,

text: by

text: Proposition

text: there

text: is

text: exactly

text: one

text: proper

text: order

text: π

text: of

text: B

text: Let

text: T

text: be

text: obtained

text: from

text: T

text: by

text: replacing

text: every

text: node

text: x

text: by

text: π(x).

text: Let

text: us

text: deﬁne

text: homomorphism

text: h

text: by

text: h

text: (x)

text: h(π

text: for

text: every

text: x

text: V

text: (T

text: and

text: let

text: B

text: (T

text: h

text: Note

text: that

text: T

text: has

text: the

text: same

text: number

text: of

text: leaves

text: and

text: internal

text: vertices

text: as

text: T

text: and

text: B

text: is

text: properly

text: ordered.

text: Also,

text: T

text: is

text: weakly


text: FIG. 6. (Color online) Variation of the normal isotropic pressure P with the shear rate γ˙ − for diﬀerent temperatures. Inset: Variation of log(P P ) with log(γ˙ ). Only data with 0 − error bars lower than the value of log(P P ) are shown. The dashed lines are straight line 0 ﬁts to this data. The solids lines in the main ﬁgure correspond to equation P = P + bγ˙ (cid:15), 0 − where b and (cid:15) were determined by the straight line ﬁts to log(P P ) versus log(γ˙ ). The 0 exponents (cid:15) are given in Table IV. T [K] (cid:15) 377 0.86 452 1.4 528 1.9 603 2.2 TABLE IV. Values of the exponent (cid:15) describing the power law increase of the normal isotropic pressure P for diﬀerent temperatures T . so that the equilibrium pressure P is around the atmospheric pressure. 0 × − Finally, for shear rates lower than 3 108 s 1 and for all temperatures, the pressure does not deviate signiﬁcantly from its equilibrium value, enabling a direct comparison with experimental results, usually obtained at constant pressure. IV. MOLECULAR STRUCTURE As mentioned in Sec. , the Cooee bitumen model used in this paper contains four molecule types. In order of increasing molecular weight, these types are: do- cosane, resinous oil, resin and asphaltene. Of these, only the docosane molecules are not aromatic. This composition resembles the SARA classiﬁcation [31] and is able to reproduce the characteristic supramolecular structure of bitumen in nanoag- gregates [11]. The nanoaggregates are composed of the aromatic molecules aligned with respect to each other. An example of a nanoaggregate seen in the simula- tions is shown in Fig. 7. The docosane molecules can be seen as a solvent for the nanoaggregates. The aim of this section is to quantify the variation of the nanoag- 15 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

text: (Color

text: online)

text: Variation

text: of

text: the

text: normal

text: isotropic

text: pressure

text: P

text: with

text: the

text: shear

text: rate

text: γ˙

text: for

text: diﬀerent

text: temperatures.

text: Inset:

text: Variation

text: of

text: log(P

text: P

text: with

text: log(γ˙

text: Only

text: data

text: with

text: error

text: bars

text: lower

text: than

text: the

text: value

text: of

text: log(P

text: P

text: are

text: shown.

text: The

text: dashed

text: lines

text: are

text: straight

text: line

text: ﬁts

text: to

text: this

text: data.

text: The

text: solids

text: lines

text: in

text: the

text: main

text: ﬁgure

text: correspond

text: to

text: equation

text: P

text: P

text: bγ˙

text: where

text: b

text: and

text: were

text: determined

text: by

text: the

text: straight

text: line

text: ﬁts

text: to

text: log(P

text: P

text: versus

text: log(γ˙

text: The

text: exponents

text: are

text: given

text: in

text: Table

text: IV.

text: T

text: [K]

text: TABLE

text: IV.

text: Values

text: of

text: the

text: exponent

text: describing

text: the

text: power

text: law

text: increase

text: of

text: the

text: normal

text: isotropic

text: pressure

text: P

text: for

text: diﬀerent

text: temperatures

text: T

text: so

text: that

text: the

text: equilibrium

text: pressure

text: P

text: is

text: around

text: the

text: atmospheric

text: pressure.

text: Finally,

text: for

text: shear

text: rates

text: lower

text: than

text: s

text: and

text: for

text: all

text: temperatures,

text: the

text: pressure

text: does

text: not

text: deviate

text: signiﬁcantly

text: from

text: its

text: equilibrium

text: value,

text: enabling

text: a

text: direct

text: comparison

text: with

text: experimental

text: results,

text: usually

text: obtained

text: at

text: constant

text: pressure.

text: IV.

text: MOLECULAR

text: STRUCTURE

text: As

text: mentioned

text: in

text: Sec.

text: the

text: Cooee

text: bitumen

text: model

text: used

text: in

text: this

text: paper

text: contains

text: four

text: molecule

text: types.

text: In

text: order

text: of

text: increasing

text: molecular

text: weight,

text: these

text: types

text: are:

text: do-

text: cosane,

text: resinous

text: oil,

text: resin

text: and

text: asphaltene.

text: Of

text: these,

text: only

text: the

text: docosane

text: molecules

text: are

text: not

text: aromatic.

text: This

text: composition

text: resembles

text: the

text: SARA

text: classiﬁcation

text: and

text: is

text: able

text: to

text: reproduce

text: the

text: characteristic

text: supramolecular

text: structure

text: of

text: bitumen

text: in

text: nanoag-

text: gregates

text: The

text: nanoaggregates

text: are

text: composed

text: of

text: the

text: aromatic

text: molecules

text: aligned

text: with

text: respect

text: to

text: each

text: other.

text: An

text: example

text: of

text: a

text: nanoaggregate

text: seen

text: in

text: the

text: simula-

text: tions

text: is

text: shown

text: in

text: Fig.

text: The

text: docosane

text: molecules

text: can

text: be

text: seen

text: as

text: a

text: solvent

text: for

text: the

text: nanoaggregates.

text: The

text: aim

text: of

text: this

text: section

text: is

text: to

text: quantify

text: the

text: variation

text: of

text: the

text: nanoag-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: rate is now considered. As can be seen in Fig. 8 (a), the nanoaggregate size at low shear rates decreases with increasing temperature. The size distribution of the linear nanoaggregates at a given low shear rate appears biexponential at all temperatures as can be seen in Fig. 9 (a). The cause of the decrease of the nanoaggregate size with temperature at low shear rates can be further investigated by looking at the rela- tive composition of the nanoaggregates for diﬀerent temperatures. The fraction r A of asphaltene molecule in a nanoaggregate is deﬁned as the number of asphaltene molecules in this nanoaggregate divided by the total number of aromatic molecules in the same nanoaggregate. Figure 9 (b) shows the variation of the fraction r of A asphaltene molecules with the nanoaggregate size for diﬀerent temperatures and at × − a low shear rate of 6 107 s 1. For linear nanoaggregates with a number of molecules larger than 3, the fraction r of asphaltene molecules in the nanoaggregates increases A with increasing temperature. Concurrently, the fraction of resin and resinous oil molecules in the nanoaggregates tends to decrease with increasing temperature in long nanoaggregates. It means that the overall decrease of the nanoaggregate size with temperature is mainly due to resin and resinous oil molecules being excluded from the aggregates at large temperatures. The asphaltene molecules stay aggre- gated even at large temperatures. It is probably an eﬀect of the cohesive energy being higher in absolute value between two asphaltene molecules than between two resin or two resinous oil molecules. This is itself due the diﬀerence in the sizes of the aromatic structures. Asphaltene molecules have a larger aromatic structure than resin and resinous oil molecules, thus creating a larger π-stacking interaction between the aromatic planes of two asphaltene molecules than between two resin or resinous oil molecules. At high shear rates in Fig. 8 (a), it seems on the contrary that the nanoaggregate size increases with increasing temperature. It is due to the fact that the shear rate at which the nanoaggregates begin to break up is not the same at all temperatures. The higher the temperature, the lower the shear rate needed to break up the nanoaggregates. This apparent crossover between the curves giving the nanoaggregate size versus the shear rate at diﬀerent temperatures can be removed if the average nanoaggregate size is plotted versus the shear stress σ rather than xy the shear rate γ˙ . This can be seen in Fig. 9 (c). This ﬁgure also shows that above 18

text: rate

text: is

text: now

text: considered.

text: As

text: can

text: be

text: seen

text: in

text: Fig.

text: (a),

text: the

text: nanoaggregate

text: size

text: at

text: low

text: shear

text: rates

text: decreases

text: with

text: increasing

text: temperature.

text: The

text: size

text: distribution

text: of

text: the

text: linear

text: nanoaggregates

text: at

text: a

text: given

text: low

text: shear

text: rate

text: appears

text: biexponential

text: at

text: all

text: temperatures

text: as

text: can

text: be

text: seen

text: in

text: Fig.

text: (a).

text: The

text: cause

text: of

text: the

text: decrease

text: of

text: the

text: nanoaggregate

text: size

text: with

text: temperature

text: at

text: low

text: shear

text: rates

text: can

text: be

text: further

text: investigated

text: by

text: looking

text: at

text: the

text: rela-

text: tive

text: composition

text: of

text: the

text: nanoaggregates

text: for

text: diﬀerent

text: temperatures.

text: The

text: fraction

text: r

text: A

text: of

text: asphaltene

text: molecule

text: in

text: a

text: nanoaggregate

text: is

text: deﬁned

text: as

text: the

text: number

text: of

text: asphaltene

text: molecules

text: in

text: this

text: nanoaggregate

text: divided

text: by

text: the

text: total

text: number

text: of

text: aromatic

text: molecules

text: in

text: the

text: same

text: nanoaggregate.

text: Figure

text: (b)

text: shows

text: the

text: variation

text: of

text: the

text: fraction

text: r

text: of

text: A

text: asphaltene

text: molecules

text: with

text: the

text: nanoaggregate

text: size

text: for

text: diﬀerent

text: temperatures

text: and

text: at

text: a

text: low

text: shear

text: rate

text: of

text: s

text: For

text: linear

text: nanoaggregates

text: with

text: a

text: number

text: of

text: molecules

text: larger

text: than

text: the

text: fraction

text: r

text: of

text: asphaltene

text: molecules

text: in

text: the

text: nanoaggregates

text: increases

text: A

text: with

text: increasing

text: temperature.

text: Concurrently,

text: the

text: fraction

text: of

text: resin

text: and

text: resinous

text: oil

text: molecules

text: in

text: the

text: nanoaggregates

text: tends

text: to

text: decrease

text: with

text: increasing

text: temperature

text: in

text: long

text: nanoaggregates.

text: It

text: means

text: that

text: the

text: overall

text: decrease

text: of

text: the

text: nanoaggregate

text: size

text: with

text: temperature

text: is

text: mainly

text: due

text: to

text: resin

text: and

text: resinous

text: oil

text: molecules

text: being

text: excluded

text: from

text: the

text: aggregates

text: at

text: large

text: temperatures.

text: The

text: asphaltene

text: molecules

text: stay

text: aggre-

text: gated

text: even

text: at

text: large

text: temperatures.

text: It

text: is

text: probably

text: an

text: eﬀect

text: of

text: the

text: cohesive

text: energy

text: being

text: higher

text: in

text: absolute

text: value

text: between

text: two

text: asphaltene

text: molecules

text: than

text: between

text: two

text: resin

text: or

text: two

text: resinous

text: oil

text: molecules.

text: This

text: is

text: itself

text: due

text: the

text: diﬀerence

text: in

text: the

text: sizes

text: of

text: the

text: aromatic

text: structures.

text: Asphaltene

text: molecules

text: have

text: a

text: larger

text: aromatic

text: structure

text: than

text: resin

text: and

text: resinous

text: oil

text: molecules,

text: thus

text: creating

text: a

text: larger

text: π-stacking

text: interaction

text: between

text: the

text: aromatic

text: planes

text: of

text: two

text: asphaltene

text: molecules

text: than

text: between

text: two

text: resin

text: or

text: resinous

text: oil

text: molecules.

text: At

text: high

text: shear

text: rates

text: in

text: Fig.

text: (a),

text: it

text: seems

text: on

text: the

text: contrary

text: that

text: the

text: nanoaggregate

text: size

text: increases

text: with

text: increasing

text: temperature.

text: It

text: is

text: due

text: to

text: the

text: fact

text: that

text: the

text: shear

text: rate

text: at

text: which

text: the

text: nanoaggregates

text: begin

text: to

text: break

text: up

text: is

text: not

text: the

text: same

text: at

text: all

text: temperatures.

text: The

text: higher

text: the

text: temperature,

text: the

text: lower

text: the

text: shear

text: rate

text: needed

text: to

text: break

text: up

text: the

text: nanoaggregates.

text: This

text: apparent

text: crossover

text: between

text: the

text: curves

text: giving

text: the

text: nanoaggregate

text: size

text: versus

text: the

text: shear

text: rate

text: at

text: diﬀerent

text: temperatures

text: can

text: be

text: removed

text: if

text: the

text: average

text: nanoaggregate

text: size

text: is

text: plotted

text: versus

text: the

text: shear

text: stress

text: σ

text: rather

text: than

text: xy

text: the

text: shear

text: rate

text: γ˙

text: This

text: can

text: be

text: seen

text: in

text: Fig.

text: (c).

text: This

text: ﬁgure

text: also

text: shows

text: that

text: above


text: a certain shear stress, all curves collapse. Figure 9 (c) can be understood if one assumes that the size of the nanoaggregates depends on two factors: the thermal energy and the work done by the external shear force applied to the system. The thermal energy is directly proportional to temperature and the work done by the shear force can be estimated from the product of the shear stress σ and the char- xy acteristic volume of an aromatic molecule in a nanoaggregate. At low shear stresses, the work done by the shear force is negligible with respect to the thermal energy and the nanoaggregate size is determined by thermal energy alone. The nanoaggre- gates have then their equilibrium size. At high shear stresses, on the contrary, the thermal energy is negligible with respect to the work done by the shear force and the nanoaggregate size is determined by the shear stress σ alone. The curves at xy diﬀerent temperatures collapse at high shear stresses. At intermediate values of the shear stress, both factors play a role in the nanoaggregate size. In this intermediate regime, an increase in shear stress at constant temperature results in a monotonic decrease of the nanoaggregate size and an increase in temperature at constant shear stress results in a monotonic decrease of the nanoaggregate size. The connection between the rupture of the nanoaggregates around a given shear rate and the variation of the viscosity with shear rate and temperature quantiﬁed in Sec. is now discussed. The overall decrease of the nanoaggregate size with increasing temperature at low shear rates contributes to the decrease of the viscosity observed with increasing temperature in Fig. 2. The rupture of the nanoaggregates at high shear rates is consistent with a decrease in the viscosity at these same shear rates instead of a plateauing around the viscosity at inﬁnite shear rate η∞, predicted by the Cross model. The Carreau-Yasuda model does not postulate the existence of a constant viscosity at inﬁnite shear rate. It could be why it better ﬁts the data than the Cross model, as was found in Sec. . Moreover, the important change in the nanoaggregate size upon shearing could explain why the time-temperature superposition principle is not satisﬁed. Indeed, the time temperature superposition typically works when all relaxation times have the same temperature dependence [43]. In the case of the Cooee bitumen model, at least two main long relaxation times can be identiﬁed: the rotational relaxation 19

text: a

text: certain

text: shear

text: stress,

text: all

text: curves

text: collapse.

text: Figure

text: (c)

text: can

text: be

text: understood

text: if

text: one

text: assumes

text: that

text: the

text: size

text: of

text: the

text: nanoaggregates

text: depends

text: on

text: two

text: factors:

text: the

text: thermal

text: energy

text: and

text: the

text: work

text: done

text: by

text: the

text: external

text: shear

text: force

text: applied

text: to

text: the

text: system.

text: The

text: thermal

text: energy

text: is

text: directly

text: proportional

text: to

text: temperature

text: and

text: the

text: work

text: done

text: by

text: the

text: shear

text: force

text: can

text: be

text: estimated

text: from

text: the

text: product

text: of

text: the

text: shear

text: stress

text: σ

text: and

text: the

text: char-

text: xy

text: acteristic

text: volume

text: of

text: an

text: aromatic

text: molecule

text: in

text: a

text: nanoaggregate.

text: At

text: low

text: shear

text: stresses,

text: the

text: work

text: done

text: by

text: the

text: shear

text: force

text: is

text: negligible

text: with

text: respect

text: to

text: the

text: thermal

text: energy

text: and

text: the

text: nanoaggregate

text: size

text: is

text: determined

text: by

text: thermal

text: energy

text: alone.

text: The

text: nanoaggre-

text: gates

text: have

text: then

text: their

text: equilibrium

text: size.

text: At

text: high

text: shear

text: stresses,

text: on

text: the

text: contrary,

text: the

text: thermal

text: energy

text: is

text: negligible

text: with

text: respect

text: to

text: the

text: work

text: done

text: by

text: the

text: shear

text: force

text: and

text: the

text: nanoaggregate

text: size

text: is

text: determined

text: by

text: the

text: shear

text: stress

text: σ

text: alone.

text: The

text: curves

text: at

text: xy

text: diﬀerent

text: temperatures

text: collapse

text: at

text: high

text: shear

text: stresses.

text: At

text: intermediate

text: values

text: of

text: the

text: shear

text: stress,

text: both

text: factors

text: play

text: a

text: role

text: in

text: the

text: nanoaggregate

text: size.

text: In

text: this

text: intermediate

text: regime,

text: an

text: increase

text: in

text: shear

text: stress

text: at

text: constant

text: temperature

text: results

text: in

text: a

text: monotonic

text: decrease

text: of

text: the

text: nanoaggregate

text: size

text: and

text: an

text: increase

text: in

text: temperature

text: at

text: constant

text: shear

text: stress

text: results

text: in

text: a

text: monotonic

text: decrease

text: of

text: the

text: nanoaggregate

text: size.

text: The

text: connection

text: between

text: the

text: rupture

text: of

text: the

text: nanoaggregates

text: around

text: a

text: given

text: shear

text: rate

text: and

text: the

text: variation

text: of

text: the

text: viscosity

text: with

text: shear

text: rate

text: and

text: temperature

text: quantiﬁed

text: in

text: Sec.

text: is

text: now

text: discussed.

text: The

text: overall

text: decrease

text: of

text: the

text: nanoaggregate

text: size

text: with

text: increasing

text: temperature

text: at

text: low

text: shear

text: rates

text: contributes

text: to

text: the

text: decrease

text: of

text: the

text: viscosity

text: observed

text: with

text: increasing

text: temperature

text: in

text: Fig.

text: The

text: rupture

text: of

text: the

text: nanoaggregates

text: at

text: high

text: shear

text: rates

text: is

text: consistent

text: with

text: a

text: decrease

text: in

text: the

text: viscosity

text: at

text: these

text: same

text: shear

text: rates

text: instead

text: of

text: a

text: plateauing

text: around

text: the

text: viscosity

text: at

text: inﬁnite

text: shear

text: rate

text: η∞,

text: predicted

text: by

text: the

text: Cross

text: model.

text: The

text: Carreau-Yasuda

text: model

text: does

text: not

text: postulate

text: the

text: existence

text: of

text: a

text: constant

text: viscosity

text: at

text: inﬁnite

text: shear

text: rate.

text: It

text: could

text: be

text: why

text: it

text: better

text: ﬁts

text: the

text: data

text: than

text: the

text: Cross

text: model,

text: as

text: was

text: found

text: in

text: Sec.

text: Moreover,

text: the

text: important

text: change

text: in

text: the

text: nanoaggregate

text: size

text: upon

text: shearing

text: could

text: explain

text: why

text: the

text: time-temperature

text: superposition

text: principle

text: is

text: not

text: satisﬁed.

text: Indeed,

text: the

text: time

text: temperature

text: superposition

text: typically

text: works

text: when

text: all

text: relaxation

text: times

text: have

text: the

text: same

text: temperature

text: dependence

text: In

text: the

text: case

text: of

text: the

text: Cooee

text: bitumen

text: model,

text: at

text: least

text: two

text: main

text: long

text: relaxation

text: times

text: can

text: be

text: identiﬁed:

text: the

text: rotational

text: relaxation


text: temperature at low shear rates. An interesting feature can be noticed for the molecular order parameter S (A) of m asphaltene molecules at high temperatures. Looking closely at the data of Fig. 11 (a) at temperature 603 K, one can note three diﬀerent regimes with increasing shear rate: at low shear rates S (A) is mostly constant, at intermediate shear rates S (A) m m slightly decreases with the shear rate, and ﬁnally at large shear rates it increases. × × − The intermediate shear rate range corresponds roughly to [3 108, 6 109] s 1 for temperature 603 K. At these shear rates, the average number of molecules in the nanoaggregates is still very close to its equilibrium value as can be seen in Fig. 8 (a). Consequently, the decrease in the molecular order parameter of the asphaltene molecules in this intermediate shear rate range can be interpreted in the following way: the nanoaggregates are still well formed, but the shear ﬂow is strong enough to disturb the alignment of the nanoaggregates with respect to each other causing the order parameter to locally drop. At higher shear rates the nanoaggregates break, the molecules align in the shear direction and the molecular order parameter increases again. This intermediate drop of the molecular order parameter S (A) of asphaltene molecules is also noticeable for temperature 528 K, m but not for lower temperatures. It might be because the nanoaggregates break before the shear ﬂow is strong enough to modify the alignment of the nanoaggregates with respect to each other. The direct consequence of this reorganization of the nanoaggregates with respect to each other on the behavior of the viscosity with the shear rate is unclear. In total, the ﬂuid is shear-thinning in this range of shear rates, as can be seen in Fig. 2. This global behavior could be mainly due to the alignment of the docosane molecules in the shear direction, the order parameter of the resin and resinous oil molecules being nearly constant in this range. 2. Molecular alignment angle The variation of the molecular alignment angle χ is plotted for each molecule m type versus the shear rate γ˙ at temperature 452 K in Fig. 12 (a). The typical behav- ior for a polymer solution under shear is the following: in the Newtonian regime, the molecular alignment angle is around 45 degrees and in the non-Newtonian regime, the molecular alignment angle decreases until reaching zero. The value of 45 de- 25

text: temperature

text: at

text: low

text: shear

text: rates.

text: An

text: interesting

text: feature

text: can

text: be

text: noticed

text: for

text: the

text: molecular

text: order

text: parameter

text: S

text: (A)

text: of

text: m

text: asphaltene

text: molecules

text: at

text: high

text: temperatures.

text: Looking

text: closely

text: at

text: the

text: data

text: of

text: Fig.

text: (a)

text: at

text: temperature

text: K,

text: one

text: can

text: note

text: three

text: diﬀerent

text: regimes

text: with

text: increasing

text: shear

text: rate:

text: at

text: low

text: shear

text: rates

text: S

text: (A)

text: is

text: mostly

text: constant,

text: at

text: intermediate

text: shear

text: rates

text: S

text: (A)

text: m

text: m

text: slightly

text: decreases

text: with

text: the

text: shear

text: rate,

text: and

text: ﬁnally

text: at

text: large

text: shear

text: rates

text: it

text: increases.

text: The

text: intermediate

text: shear

text: rate

text: range

text: corresponds

text: roughly

text: to

text: s

text: for

text: temperature

text: K.

text: At

text: these

text: shear

text: rates,

text: the

text: average

text: number

text: of

text: molecules

text: in

text: the

text: nanoaggregates

text: is

text: still

text: very

text: close

text: to

text: its

text: equilibrium

text: value

text: as

text: can

text: be

text: seen

text: in

text: Fig.

text: (a).

text: Consequently,

text: the

text: decrease

text: in

text: the

text: molecular

text: order

text: parameter

text: of

text: the

text: asphaltene

text: molecules

text: in

text: this

text: intermediate

text: shear

text: rate

text: range

text: can

text: be

text: interpreted

text: in

text: the

text: following

text: way:

text: the

text: nanoaggregates

text: are

text: still

text: well

text: formed,

text: but

text: the

text: shear

text: ﬂow

text: is

text: strong

text: enough

text: to

text: disturb

text: the

text: alignment

text: of

text: the

text: nanoaggregates

text: with

text: respect

text: to

text: each

text: other

text: causing

text: the

text: order

text: parameter

text: to

text: locally

text: drop.

text: At

text: higher

text: shear

text: rates

text: the

text: nanoaggregates

text: break,

text: the

text: molecules

text: align

text: in

text: the

text: shear

text: direction

text: and

text: the

text: molecular

text: order

text: parameter

text: increases

text: again.

text: This

text: intermediate

text: drop

text: of

text: the

text: molecular

text: order

text: parameter

text: S

text: (A)

text: of

text: asphaltene

text: molecules

text: is

text: also

text: noticeable

text: for

text: temperature

text: K,

text: m

text: but

text: not

text: for

text: lower

text: temperatures.

text: It

text: might

text: be

text: because

text: the

text: nanoaggregates

text: break

text: before

text: the

text: shear

text: ﬂow

text: is

text: strong

text: enough

text: to

text: modify

text: the

text: alignment

text: of

text: the

text: nanoaggregates

text: with

text: respect

text: to

text: each

text: other.

text: The

text: direct

text: consequence

text: of

text: this

text: reorganization

text: of

text: the

text: nanoaggregates

text: with

text: respect

text: to

text: each

text: other

text: on

text: the

text: behavior

text: of

text: the

text: viscosity

text: with

text: the

text: shear

text: rate

text: is

text: unclear.

text: In

text: total,

text: the

text: ﬂuid

text: is

text: shear-thinning

text: in

text: this

text: range

text: of

text: shear

text: rates,

text: as

text: can

text: be

text: seen

text: in

text: Fig.

text: This

text: global

text: behavior

text: could

text: be

text: mainly

text: due

text: to

text: the

text: alignment

text: of

text: the

text: docosane

text: molecules

text: in

text: the

text: shear

text: direction,

text: the

text: order

text: parameter

text: of

text: the

text: resin

text: and

text: resinous

text: oil

text: molecules

text: being

text: nearly

text: constant

text: in

text: this

text: range.

text: Molecular

text: alignment

text: angle

text: The

text: variation

text: of

text: the

text: molecular

text: alignment

text: angle

text: χ

text: is

text: plotted

text: for

text: each

text: molecule

text: m

text: type

text: versus

text: the

text: shear

text: rate

text: γ˙

text: at

text: temperature

text: K

text: in

text: Fig.

text: (a).

text: The

text: typical

text: behav-

text: ior

text: for

text: a

text: polymer

text: solution

text: under

text: shear

text: is

text: the

text: following:

text: in

text: the

text: Newtonian

text: regime,

text: the

text: molecular

text: alignment

text: angle

text: is

text: around

text: degrees

text: and

text: in

text: the

text: non-Newtonian

text: regime,

text: the

text: molecular

text: alignment

text: angle

text: decreases

text: until

text: reaching

text: zero.

text: The

text: value

text: of

text: de-


text: The same procedure is applied to the equations of motion for the B operator, 1 which for the atomic momenta (at constant positions) are: dp − m − m iα iα iα = γ˙ p xˆ α p . (A12) yi 1 i dt M M i i Here α is the part of the Gaussian thermostat multiplier ζ associated with con- 1 serving the kinetic energy during this (cid:80)part of the integration; it has the expression (cid:80) − γ˙ p p /M α = i xi yi i . (A13) 1 p2/M i i i Note that the thermostat term involves only molecular quantities, that is, it is a (cid:80) so-called molecular thermostat which conserves the sum of the translational kinetic energies of the molecules p2/2M . Summing Eq. (A12) over α gives i i i dp − − i = γ˙ p xˆ α p , (A14) yi 1 i dt which is identical to the B equation in Ref. 32 (where i was an atomic index). 1 Again the solution must be the same: − p (t + ∆t) = g(∆t) (p (t) xˆ∆tγ˙ p (t)) . (A15) i i yi √ − Here g(∆t) = 1/ 1 2c ∆t + c ∆t2 and c and c are expressions involving 1 2 1 2 sums of products of molecular momenta (see Ref. 32). Next we consider the veloc- ity relative to the center of mass. Dividing Eqs. (A12) and A14 by m and M , iα i respectively, and then subtracting the second from the ﬁrst gives the equation for the relative velocity: d − (v v ) = 0, (A16) iα i dt 35 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: same

text: procedure

text: is

text: applied

text: to

text: the

text: equations

text: of

text: motion

text: for

text: the

text: B

text: operator,

text: which

text: for

text: the

text: atomic

text: momenta

text: (at

text: constant

text: positions)

text: are:

text: dp

label: equation

text: m

text: m

text: iα

text: iα

text: iα

text: γ˙

text: p

text: xˆ

text: α

text: p

text: yi

text: i

text: dt

text: M

text: M

text: i

text: i

text: Here

text: α

text: is

text: the

text: part

text: of

text: the

text: Gaussian

text: thermostat

text: multiplier

text: ζ

text: associated

text: with

text: con-

text: serving

text: the

text: kinetic

text: energy

text: during

text: this

text: of

text: the

text: integration;

text: it

text: has

text: the

text: expression

text: γ˙

text: p

text: p

text: /M

text: α

text: i

text: xi

text: yi

text: i

text: i

text: i

text: i

text: Note

text: that

text: the

text: thermostat

text: term

text: involves

text: only

text: molecular

text: quantities,

text: that

text: is,

text: it

text: is

text: a

text: so-called

text: molecular

text: thermostat

text: which

text: conserves

text: the

text: sum

text: of

text: the

text: translational

text: kinetic

text: energies

text: of

text: the

text: molecules

text: Summing

text: Eq.

text: over

text: α

text: gives

text: i

text: i

text: i

text: dp

text: i

text: γ˙

text: p

text: xˆ

text: α

text: p

text: yi

text: i

text: dt

text: which

text: is

text: identical

text: to

text: the

text: B

text: equation

text: in

text: Ref.

text: (where

text: i

text: was

text: an

text: atomic

text: index).

text: Again

text: the

text: solution

text: must

text: be

text: the

text: same:

text: p

text: (t

text: ∆t)

text: g(∆t)

text: (p

text: (t)

text: xˆ∆tγ˙

text: p

text: (t))

text: i

text: i

text: yi

text: Here

text: g(∆t)

text: ∆t

text: c

text: and

text: c

text: and

text: c

text: are

text: expressions

text: involving

text: sums

text: of

text: products

text: of

text: molecular

text: momenta

text: (see

text: Ref.

text: Next

text: we

text: consider

text: the

text: veloc-

text: ity

text: relative

text: to

text: the

text: center

text: of

text: mass.

text: Dividing

text: Eqs.

text: and

text: by

text: m

text: and

text: M

text: iα

text: i

text: respectively,

text: and

text: then

text: subtracting

text: the

text: second

text: from

text: the

text: ﬁrst

text: gives

text: the

text: equation

text: for

text: the

text: relative

text: velocity:

text: d

text: (v

text: v

text: iα

text: i

text: dt

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: i.e. the relative velocity is not aﬀected by the ﬂow or the thermostat—this is of course the point of using molecular SLLOD equations and a molecular thermostat: they translate each molecules rigidly, without rotation or deformation. The update- expression for an atomic velocity is therefore that which gives the same numerical diﬀerence as the update-expression for the center of mass velocity. − v (t + ∆t) = v (t) v (t) + v (t + ∆t) (A17) iα iα i i − − = v (t) + (g(∆t) 1)v (t) g(∆t)∆tγ˙ v xˆ. (A18) iα i yi For the B2 equations of motion, the procedure is essentially the same: the velocity of the center of mass obeys the B equation in Ref. 32 for the atomic case, with 2 solution (cid:18) (cid:19) − − − 1 h 1 + h e h/e p (t + ∆t) = − p (t) + F (t) − = p (t) + M ∆v (A19) i t i i i i e h/e (1 h)β where expressions for e(∆t), β and h are given in Ref. 32 (note that the sign of the second term in parentheses was incorrect in Ref. 32, their Eq. (22)). The notation ∆v for the change in center of mass velocity of molecule i is introduced i for use below. The relative velocity obeys: d − − − (v v ) = F /m F /M = a a , (A20) iα i iα iα i i iα i dt where a and a are the (constant) accelerations. To update the atomic velocities iα i we then have − v (t + ∆t) = v (t) + ∆v + ∆t(a a ), (A21) iα iα i iα i where ∆v is determined from Eq. (A19). i 36 ##LTLine## ##LTLine## ##LTLine##

text: i.e.

text: the

text: relative

text: velocity

text: is

text: not

text: aﬀected

text: by

text: the

text: ﬂow

text: or

text: the

text: thermostat—this

text: is

text: of

text: course

text: the

text: point

text: of

text: using

text: molecular

text: SLLOD

text: equations

text: and

text: a

text: molecular

text: thermostat:

text: they

text: translate

text: each

text: molecules

text: rigidly,

text: without

text: rotation

text: or

text: deformation.

text: The

text: update-

text: expression

text: for

text: an

text: atomic

text: velocity

text: is

text: therefore

text: that

text: which

text: gives

text: the

text: same

text: numerical

text: diﬀerence

text: as

text: the

text: update-expression

text: for

text: the

text: center

text: of

text: mass

text: velocity.

text: v

text: (t

text: ∆t)

text: v

text: (t)

text: v

text: (t)

text: v

text: (t

text: ∆t)

text: iα

text: iα

text: i

text: i

text: v

text: (t)

text: (g(∆t)

text: (t)

text: g(∆t)∆tγ˙

text: v

text: xˆ.

text: iα

text: i

text: yi

text: For

text: the

text: equations

text: of

text: motion,

text: the

text: procedure

text: is

text: essentially

text: the

text: same:

text: the

text: velocity

text: of

text: the

text: center

text: of

text: mass

text: obeys

text: the

text: B

text: equation

text: in

text: Ref.

text: for

text: the

text: atomic

text: case,

text: with

text: solution

text: h

text: h

text: e

text: h/e

text: p

text: (t

text: ∆t)

text: p

text: (t)

text: F

text: (t)

text: p

text: (t)

text: M

text: ∆v

text: i

text: t

text: i

text: i

text: i

text: i

text: e

text: h/e

text: h)β

text: where

text: expressions

text: for

text: e(∆t),

text: β

text: and

text: h

text: are

text: given

text: in

text: Ref.

text: (note

text: that

text: the

text: sign

text: of

text: the

text: second

text: term

text: in

text: parentheses

text: was

text: incorrect

text: in

text: Ref.

text: their

text: Eq.

text: The

text: notation

text: ∆v

text: for

text: the

text: change

text: in

text: center

text: of

text: mass

text: velocity

text: of

text: molecule

text: i

text: is

text: introduced

text: i

text: for

text: use

text: below.

text: The

text: relative

text: velocity

text: obeys:

text: d

text: (v

text: v

text: F

text: /m

text: F

text: /M

text: a

text: a

text: iα

text: i

text: iα

text: iα

text: i

text: i

text: iα

text: i

text: dt

text: where

text: a

text: and

text: a

text: are

text: the

text: (constant)

text: accelerations.

text: To

text: update

text: the

text: atomic

text: velocities

text: iα

text: i

text: we

text: then

text: have

text: v

text: (t

text: ∆t)

text: v

text: (t)

text: ∆v

text: ∆t(a

text: a

text: iα

text: iα

text: i

text: iα

text: i

text: where

text: ∆v

text: is

text: determined

text: from

text: Eq.

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: the ﬁrst time that the operator splitting algorithm has been adapted to molecular systems. This implementation is described in appendix A. The MD graphical processing unit package RUMD [33] was used to perform the calculation in double precision. The time step is equal to δt = 0.86 fs. Each simulation was equilibrated for a period of 1.7 ns and lasted thereafter 6.9 ns. Depending on the strain rate and the temperature, 8 or 16 independent initial conﬁgurations were used. The change − in density from one initial conﬁguration to the other is less than 10 12 %. The averages and standard errors shown in this paper correspond to the averages and standard errors over these independent simulations. III. RHEOLOGY Four main rheological properties can be computed from the NEMD simulations under shear. They are the shear viscosity η, the ﬁrst and second normal stress coeﬃcients Ψ and Ψ , and the non-equilibrium molecular pressure P . They provide 1 2 information about the Newtonian and non-Newtonian behavior of the ﬂuid. These quantities are derived from the molecular stress tensor σ, given by the Irving-Kirkwood formula [34]: (cid:28) (cid:29) (cid:88) (cid:88) (cid:88) − 1 Nm p p Nm Nm i i σ = + r F , (5) ij ij V M i i=1 i=1 j>i (cid:104)·(cid:105) where V is the volume of the system, denotes a time average over the non- (cid:80) (cid:80) − equilibrium steady state, r = r r is the vector between the centers of mass of ij i j molecules i and j, F = F is the intermolecular force acting on molecule i ij α β iαjβ due to molecule j and F is the force acting on particle α in molecule i due to iαjβ particle β in molecule j. A. Shear viscosity Due to the shear geometry enforced in the simulation, the shear viscosity is given by: σ + σ xy yx η = , (6) 2γ˙ 6 ##LTLine## ##LTLine## ##LTLine##

text: the

text: ﬁrst

text: time

text: that

text: the

text: operator

text: splitting

text: algorithm

text: has

text: been

text: adapted

text: to

text: molecular

text: systems.

text: This

text: implementation

text: is

text: described

text: in

text: appendix

text: A.

text: The

text: MD

text: graphical

text: processing

text: unit

text: package

text: RUMD

text: was

text: used

text: to

text: perform

text: the

text: calculation

text: in

text: double

text: precision.

text: The

text: time

text: step

text: is

text: equal

text: to

text: δt

text: fs.

text: Each

text: simulation

text: was

text: equilibrated

text: for

text: a

text: period

text: of

text: ns

text: and

text: lasted

text: thereafter

text: ns.

text: Depending

text: on

text: the

text: strain

text: rate

text: and

text: the

text: temperature,

text: or

text: independent

text: initial

text: conﬁgurations

text: were

text: used.

text: The

text: change

text: in

text: density

text: from

text: one

text: initial

text: conﬁguration

text: to

text: the

text: other

text: is

text: less

text: than

text: The

text: averages

text: and

text: standard

text: errors

text: shown

text: in

text: this

text: paper

text: correspond

text: to

text: the

text: averages

text: and

text: standard

text: errors

text: over

text: these

text: independent

text: simulations.

text: III.

text: RHEOLOGY

text: Four

text: main

text: rheological

text: properties

text: can

text: be

text: computed

text: from

text: the

text: NEMD

text: simulations

text: under

text: shear.

text: They

text: are

text: the

text: shear

text: viscosity

text: η,

text: the

text: ﬁrst

text: and

text: second

text: normal

text: stress

text: coeﬃcients

text: Ψ

text: and

text: Ψ

text: and

text: the

text: non-equilibrium

text: molecular

text: pressure

text: P

text: They

text: provide

text: information

text: about

text: the

text: Newtonian

text: and

text: non-Newtonian

text: behavior

text: of

text: the

text: ﬂuid.

text: These

text: quantities

text: are

text: derived

text: from

text: the

text: molecular

text: stress

text: tensor

text: σ,

text: given

text: by

text: the

text: Irving-Kirkwood

text: formula

text: Nm

text: p

text: p

text: Nm

text: Nm

text: i

text: i

text: σ

text: r

text: F

text: ij

text: ij

text: V

text: M

text: i

text: j>i

text: where

text: V

text: is

text: the

text: volume

text: of

text: the

text: system,

text: denotes

text: a

text: time

text: average

text: over

text: the

text: non-

text: equilibrium

text: steady

text: state,

text: r

text: r

text: r

text: is

text: the

text: vector

text: between

text: the

text: centers

text: of

text: mass

text: of

text: ij

text: i

text: j

text: molecules

text: i

text: and

text: j,

text: F

text: F

text: is

text: the

text: intermolecular

text: force

text: acting

text: on

text: molecule

text: i

text: ij

text: α

text: β

text: iαjβ

text: due

text: to

text: molecule

text: j

text: and

text: F

text: is

text: the

text: force

text: acting

text: on

text: particle

text: α

text: in

text: molecule

text: i

text: due

text: to

text: iαjβ

text: particle

text: β

text: in

text: molecule

text: j.

text: A.

text: Shear

text: viscosity

text: Due

text: to

text: the

text: shear

text: geometry

text: enforced

text: in

text: the

text: simulation,

text: the

text: shear

text: viscosity

text: is

text: given

text: by:

text: σ

text: σ

text: xy

text: yx

text: η

text: 2γ˙

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##