Spotting Trees with Few Leaves

We show two results related to the

Hamiltonicity

and

$$k$$

k

-Path

algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some

$$k$$

k

-vertex tree with

$$l$$

l

leaves in an

$$n$$

n

-vertex undirected graph in

$$O^*(1.657^k2^{l/2})$$

O

∗

(

1

.

657

k

2

l

/

2

)

time. It can be applied as a subroutine to solve the

$$k$$

k

-Internal Spanning Tree

(

$$k$$

k

-IST) problem in

$$O^*({\text {min}}(3.455^k, 1.946^n))$$

O

∗

(

min

(

3

.

455

k

,

1

.

946

n

)

)

time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of

$$O^*(2^n)$$

O

∗

(

2

n

)

. Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for

$$k$$

k

-Path

and

Hamiltonicity

in any graph of maximum degree

$$\Delta =4,\ldots ,12$$

Δ

=

4

,

…

,

12

or with vector chromatic number at most

$$8$$

8

.