How to navigate through obstacles?
Eduard Eiben∗

Iyad Kanj†

arXiv:1712.04043v1 [cs.CG] 11 Dec 2017

Abstract
Given a set of obstacles and two points in the plane, is there a path between the two points
that does not cross more than k different obstacles? Equivalently, can we remove k obstacles so
that there is an obstacle-free path between the two designated points? This is a fundamental
problem that has undergone a tremendous amount of work by researchers in various areas,
including computational geometry, graph theory, wireless computing, and motion planning. It
is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unitlength line segments). The problem can be formulated and generalized into the following graph
problem: Given a planar graph G whose vertices are colored by color sets, two designated
vertices s, t ∈ V (G), and k ∈ N, is there an s-t path in G that uses at most k colors? If each
obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that
each color induces a connected subgraph.
We study the complexity and design algorithms for the above graph problem with an eye on
its geometric applications. We prove a set of hardness results, among which a result showing
that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT)
algorithms (even for various restrictions and parameterizations of the problem), as without it,
the problem is W[SAT]-hard parameterized by k. Previous results only implied that the problem
is W[2]-hard. A corollary of the aforementioned result is that, unless W[2] = FPT, the problem
cannot be approximated in FPT time to within a factor that is a function of k. By describing
a generic plane embedding of the graph instances, we show that our hardness results translate
to the geometric instances of the problem.
We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results that reveal
rich structural properties of the problem. These results allow us to prove that, for any vertex v
in the graph, there exists a set of paths whose cardinality is upper bounded by some function
of k, that “represents” the valid s-t paths containing subsets of colors from v. We employ these
structural results to design an FPT algorithm for the problem parameterized by both k and
the treewidth of the graph, and extend this result further to obtain an FPT algorithm for the
parameterization by both k and the length of the path. The latter result directly implies and
explains previous FPT results for various obstacle shapes, such as unit disks and fat regions.

Keywords: parameterized complexity and algorithms; motion planning; barrier coverage; planar graphs; colored path

1

Introduction

We consider the following problem: Given a set of obstacles and two designated points in the plane,
is there a path between the two points that does not cross more than k obstacles? Equivalently,
∗

Algorithms and Complexity Group, TU Wien, Austria & Department of Informatics, University of Bergen,
Bergen, Norway. Email: eduard.eiben@uib.no
†
School of Computing, DePaul University, Chicago, USA. Email: ikanj@cs.depaul.edu

1

can we remove k obstacles so that there is an obstacle-free path between the two designated points?
We refer to this problem as Obstacle Removal, and to its restriction to instances in which each
obstacle is connected as Connected Obstacle Removal.
By considering the auxiliary plane graph that is the dual of the plane subdivision determined
by the obstacles1 , Obstacle Removal was formulated and generalized into the following graph
problem, referred to as Colored Path (see Figure 1 for illustrations):
Colored Path
Given: A planar graph G; a set of colors C; χ : V −→ 2C ; two designated vertices s, t ∈ V (G);
and k ∈ N
Question: Does there exist an s-t path in G that uses at most k colors?
Denote by Colored Path-Con the restriction of Colored Path to instances in which each
color induces a connected subgraph of G.

t

t

s

s

Figure 1: Illustration of instances of the problem under consideration drawn within a bounding
box. The left figure shows an instance in which the optimal path crosses two obstacles, zigzagging
between the other obstacles. The right figure shows an instance and its auxiliary plane graph.
As we discuss next, Connected Obstacle Removal and Colored Path are fundamental
problems that have undergone a tremendous amount of work, albeit under different names and
contexts, by researchers in various areas, including computational geometry, graph theory, wireless
computing, and motion planning.

1.1

Related Work

In motion planning, the goal is generally to move a robot from a starting position to a final position,
while avoiding collision with a set of obstacles. This is usually referred to as the piano-mover’s
1

We assume that the regions formed by the obstacles can be computed in polynomial time. We do not assume
that the obstacles contain their interiors.If the intersection of two obstacles is not a 2-D region, we can thicken the
borders of the obstacles without changing the sets of obstacles they intersect, so that their intersection becomes a
2-D region.

2

problem. Obstacle Removal is a variant of the piano-mover’s problem, in which the obstacles
are in the plane and the robot is represented as a point. Since determining if there is an obstacle-free
path for the robot in this case is solvable in polynomial time, if no such path exists, it is natural
to seek a path that intersects as few obstacles as possible. Motivated by planning applications,
Connected Obstacle Removal and Colored Path were studied under the name Minimum
Constraint Removal [11, 12, 16, 18]. Connected Obstacle Removal has also been studied
extensively, motivated by applications in wireless computing, under the name Barrier Coverage
or Barrier Resilience [1, 2, 25, 26, 30, 31]. In such applications, we are given a field covered
by sensors (usually simple shapes such as unit disks), and the goal is to compute a minimum set of
sensors that need to fail before an entity can move undetected between two given sites.
Kumar et al. [26] were the first to study Connected Obstacle Removal. They showed that
for unit-disk obstacles in some restricted setting, the problem can be solved in polynomial time.
The complexity of the general case for unit-disk obstacles remains open. Several works showed the
NP-hardness of the problem, even when the obstacles are very simple geometric shapes such as line
segments (e.g., see [1, 30, 31]). The complexity of the problem when each obstacle intersects a
constant number of other obstacles is open [12, 18].
Bereg and Kirkpatrick [2] designed approximation algorithms when the obstacles are unit disks
by showing that the length, referred to as the thickness [2] (i.e., number of regions visited), of a
shortest path that crosses k disks is at most 3k; this follows from the fact that a shortest path does
not cross a disk more than a constant number of times.
Korman et al. [25] showed that Connected Obstacle Removal is FPT parameterized by k
for unit-disk obstacles, and extended this result to similar-size fat-region obstacles with a constant
overlapping number, which is the maximum number of obstacles having nonempty intersection.
Their result draws the observation, which was also used in [2], that for unit-disk (and fat-region)
obstacles, the length of an optimal path can be upper bounded by a linear function of the number
of obstacles crossed (i.e., the parameter). This observation was then exploited by a branching phase
that decomposes the path into subpaths in (simpler) restricted regions, enabling a similar approach
to that of Kumar et al. [26].
Motivated by its applications to networking, among other areas, the problem of computing a
minimum-colored path in a graph received considerable attention (e.g., see [3, 32]). The problem
was shown to be NP-hard in several works [3, 4, 18, 32].2 Most of the NP-hardness reductions start
from Set Cover, and result in instances of Colored Path (i.e., planar graphs), as was also
observed by [2]. These reductions are FPT-reductions, implying the W[2]-hardness of Colored
Path. Moreover, these reductions imply that, unless P = NP, the minimization version of Colored
Path cannot be approximated to within a factor of c lg n, for any constant c < 1. Hauser [18], and
Gorbenko and Popov [16], implemented exact and heuristic algorithms for the problem on general
graphs. Very recently, Eiben et al. [11] designed exact and heuristic algorithms for Colored Path
and Obstacle Removal, and proved computational lower bounds on their subexponential-time
complexity, assuming the Exponential Time Hypothesis.
Finally, we mention that there is a related problem that is solvable in polynomial time, which
has received considerable attention [5, 19, 20], where the goal is to find a shortest path w.r.t. the
Euclidean length between two given points in the plane that intersects at most k obstacles. The
Colored Path problem also falls into the category of many computationally-hard problems on
colored graphs, where the objective is to compute a graph structure satisfying certain (desired)
properties that uses the minimum number of colors (e.g., see [14]).
2

We note that some works consider the edge-colored version of the problem, but for all purposes considered in
this paper the two versions are equivalent.

3

1.2

Our Results and Techniques

We study the complexity and parameterized complexity of Colored Path and Colored PathCon, eyeing the implications on their geometric counterparts Obstacle Removal and Connected Obstacle Removal, respectively. We do not treat the problem on general graphs because, as we point out in Remark 3.13, this problem is computationally very hard, even when
restricted to graphs satisfying the color-connectivity property.
Our first set of hardness results show that both problems are NP-hard, even when restricted to
graphs of small outerplanarity and pathwidth, and that it is unlikely that they can be solved in
subexponential time:
(i) Colored Path is NP-complete, even for outerplanar graphs of pathwidth at most 2 and in
which every vertex contains at most one color (Theorem 3.1).
(ii) Colored Path-Con is NP-complete even for 2-outerplanar graphs of pathwidth at most 3
(Corollary 3.2).
(iii) Unless ETH fails, Colored Path-Con (and hence Colored Path) is not solvable in subexponential time, even for 2-outerplanar graphs of pathwidth at most 3 and in which each color
appears at most 4 times (Corollary 3.3).
The reduction used to prove (i) produces instances of Colored Path that can be realized
as geometric instances of Obstacle Removal whose overlapping number is at most 2. Thus,
this hardness result extends to the aforementioned restriction of Obstacle Removal. The same
reduction is then modified to yield (ii) and (iii) for Colored Path-Con; this reduction produces
instances of Colored Path that can be realized as geometric instances of Connected Obstacle
Removal whose overlapping number is at most 4, again showing that the hardness results extend
to these restrictions of Connected Obstacle Removal.
We then study the parameterized complexity of Colored Path and Colored Path-Con. Clearly,
Colored Path is in the parameterized class XP. We show that the color-connectivity property
is crucial for any hope for an FPT-algorithm, since even very restricted instances and combined
parameterizations of Colored Path are W[1]-complete:
(iv) Colored Path, restricted to instances of pathwidth at most 4, and in which each vertex
contains at most one color and each color appears on at most 2 vertices, is W[1]-complete
parameterized by k (Theorem 3.8).
(v) Colored Path, parameterized by both k and the length of the sought path `, is W[1]complete (Theorem 3.7).
Without restrictions, the problem sits high in the parameterized complexity hierarchy:
(vi) Colored Path, parameterized by k, is W[SAT]-hard (Theorem 3.10) and is in W[P] (Theorem 3.9).
A corollary of (vi) is that, unless W[2] = FPT, Colored Path cannot be approximated in FPT
time to within a factor that is a function of k (Corollary 3.12).
By producing a generic construction (Remark 3.4) that can be used to realize any graph instance
of Colored Path as a geometric instance of Obstacle Removal, the hardness results in (iv)–(vi),
and the inapproximability result discussed above, translate to Obstacle Removal. This geometric
4

realization may slightly increase the overlapping number by at most 2. Previously, Colored Path
was only known to be W[2]-hard, via the standard reduction from Set Cover [3, 18, 32]. Our
results refine the parameterized complexity and approximability of Colored Path and Obstacle
Removal.
As noted in Remark 3.13, the color-connectivity property without planarity is hopeless: We can
tradeoff planarity for color-connectivity by adding a single vertex that serves as a color-connector,
thus establishing the W[SAT]-hardness of the problem on apex graphs.
The above hardness results show that we can focus our attention on Colored Path-Con. We
show the following algorithmic result:
(vii) Colored Path-Con, parameterized by both k and the treewidth ω of the input graph, is
FPT (Theorem 5.12).
We remark that bounding the treewidth does not make Colored Path-Con much easier, as we
show in this paper that Colored Path-Con is NP-hard even for 2-outerplanar graphs of pathwidth
at most 3 (Corollary 3.2).
The folklore dynamic programming approach based on tree decomposition, used for the Hamiltonian Path/Cycle problems, does not work for Colored Path-Con to prove the result in
(vii) for the following reasons. As opposed to the Hamiltonian Path/Cycle problems, where it
is sufficient to keep track of how the path/cycle interacts with each bag in the tree decomposition,
this is not sufficient in the case of Colored Path-Con because we also need to keep track of which
color sets are used on both sides of the bag. Although (by color connectivity) any subset of colors
appearing on both sides of a bag must appear on vertices in the bag as well, there can be too many
such subsets (up to |C|k , where C is the set of colors), and certainly we cannot afford to enumerate
all of them if we seek an FPT algorithm. To overcome this issue, we develop in Section 4 topological
structural results that exploit the planarity of the graph and the connectivity of the colors to show
the following. For any vertex w ∈ V (G), and for any pair of vertices u, v ∈ V (G), the set of (valid)
u-v paths in G − w that use colors appearing on vertices in the face of G − w containing w can be
“represented” by a minimal set of paths whose cardinality is a function of k.
In Section 5, we extend the notion of a minimal set of paths w.r.t. a single vertex to a “representative set” of paths w.r.t. a specific bag, and a specific enumerated configuration for the bag, in
a tree decomposition of the graph. This enables us to use the upper bound on the size of a minimal
set of paths, derived in Section 4, to upper bound the size of a representative set of paths w.r.t. a
bag and a configuration. This, in turn, yields an upper bound on the size of the table stored at
a bag, in the dynamic programming algorithm, by a function of both k and the treewidth of the
graph, thus yielding the desired result.
In Section 6, we extend the FPT result for Colored Path-Con in (vii) w.r.t. the parameters
k and ω, to the parameterization by both k and the length ` of the path:
(viii) Colored Path-Con, and hence Connected Obstacle Removal, parameterized by both
k and ` is FPT (Theorem 6.15).
The dependency on both ` and k is essential for the result in (viii) : If we parameterize only
by k, or only by `, then the problem becomes W[1]-hard (Theorem 6.1 and Theorem 6.2). By
Remark 3.4, these two results translate to Connected Obstacle Removal.
The result in (viii) generalizes and explains Korman et al.’s results [25] showing that Connected
Obstacle Removal is FPT parameterized by k for unit-disk obstacles, which they also generalized
to similar-size fat-region obstacles with bounded overlapping number. Their results exploit the
obstacle shape to upper bound the length of the path by a linear function of k, and then use
5

branching to reduce the problems to a simpler setting. Our result directly implies that, regardless
of the (connected) obstacle shapes, as long as the path length is upper bounded by some function
of k (Corollary 6.16), the problem is FPT. The FPT result in (viii) also implies that:
(ix) For any computable function h, Colored Path-Con restricted to instances in which each
color appears on at most h(k) vertices, is FPT parameterized by k (Corollary 6.18).
Result (ix) has applications to Connected Obstacle Removal, in particular, to the interesting case when the obstacles are convex polygons, each intersecting a constant number of other
polygons. The question about the complexity of this problem was posed in [12, 18], and remains
open. The result in (ix) implies that this problem is FPT (Theorem 6.19).
We finally mention that it remains open whether Colored Path-Con and Connected Obstacle Removal are FPT parameterized by k only.

2

Preliminaries

We assume familiarity with the basic notations and terminologies in graph theory and parameterized
complexity. We refer the reader to the standard books [9, 10] for more information on these subjects.
Graphs. All graphs in this paper are simple (i.e., loop-less and with no multiple edges). Let G
be an undirected graph. For an edge e = uv in G, contracting e means removing the two vertices u
and v from G, replacing them with a new vertex w, and for every vertex y in the neighborhood of
v or u in G, adding an edge wy in the new graph, not allowing multiple edges. Given a vertex-set
S ⊆ V (G), contracting S means contracting the edges between the vertices in S to obtain a single
vertex at the end.
A graph is planar if it can be drawn in the plane without edge intersections (except at the
endpoints). An apex graph is a graph in which the removal of a single vertex results in a planar
graph. A plane graph has a fixed drawing. Each maximal connected region of the plane minus the
drawing is an open set; these are the faces. One is unbounded, called the outer face. An outerplane
graph is a plane graph for which every vertex is incident to the outer face; and outerplanar graph
is a graph that has such a plane embedding. An i-outerplane graph (resp. i-outerplaner graph),
for i > 1, is defined inductively as a graph such that the removal of its outer face results in an
(i − 1)-outerplane graph (resp. (i − 1)-outerplaner graph) graph.
Let S be a set of points in the plane, and let C1 , C2 be two non self-intersecting curves that
meet S in precisely their common endpoints a and b. We say that C1 and C2 are isotopic w.r.t. S
(also known as homotopic rel. boundary) if there is a continuous deformation from C1 to C2 through
curves between a and b such that no intermediate curve in this deformation meets a vertex of S in
its interior.
Let W1 = (u1 , . . . , up ) and W2 = (v1 , . . . , vq ), p, q ∈ N, be two walks such that up = v1 .
Define the gluing operation ◦ that when applied to W1 and W2 produces that walk W1 ◦ W2 =
(u1 , . . . , up , v2 , . . . , vq ).
For a graph G and two vertices u, v ∈ V (G), we denote by dG (u, v) the distance between u and
v in G, which the length of a shortest path between u and v in G.
Treewidth, Pathwidth and Tree Decomposition.
Definition 2.1. Let G = (V, E) be a S
graph. A tree decomposition of G is a pair (V, T ) where V is
a collection of subsets of V such that Xi ∈V = V , and T is a rooted tree whose node set is V, such
that:
6

1. For every edge {u, v} ∈ E, there is an Xi ∈ V, such that {u, v} ⊆ Xi ; and
2. for all Xi , Xj , Xk ∈ V, if the node Xj lies on the path between the nodes Xi and Xk in the
tree T , then Xi ∩ Xk ⊆ Xj .
The width of the tree decomposition (V, T ) is defined to be max{|Xi | | Xi ∈ V} − 1. The
treewidth of the graph G is the minimum width over all tree decompositions of G.
A path decomposition of a graph G is a tree decomposition (V, T ) of G, where T is a path. The
pathwidth of a graph G is the minimum width over all path decompositions of G.
A tree decomposition (V, T ) is nice if it satisfies the following conditions:
1. Each node in the tree T has at most two children.
2. If a node Xi has two children Xj and Xk in the tree T , then Xi = Xj = Xk ; in this case node
Xi is called a join node.
3. If a node Xi has only one child Xj in the tree T , then either |Xi | = |Xj | + 1 and Xj ⊂ Xi ,
and in this case Xi is called an insert node; or |Xi | = |Xj | − 1 and Xi ⊂ Xj , and in this case
Xi is called a forget node.
4. If Xi is a leaf node or the root, then Xi = ∅.
Boolean Circuits and Parameterized Complexity. A circuit is a directed acyclic graph. The
vertices of indegree 0 are called the (input) variables, and are labeled either by positive literals xi
or by negative literals xi . The vertices of indegree larger than 0 are called the gates and are labeled
with Boolean operators and or or. A special gate of outdegree 0 is designated as the output gate.
We do not allow not gates in the above circuit model, since by De Morgan’s laws, a general circuit
can be effectively converted into the above circuit model. A circuit is said to be monotone if all its
input literals are positive. The depth of a circuit is the maximum distance from an input variable to
the output gate of the circuit. A circuit represents a Boolean function in a natural way. The size of
a circuit C, denoted |C|, is the size of the underlying graph (i.e., number of vertices and edges). An
occurrence of a literal in C is an edge from the literal to a gate in C. Therefore, the total number of
occurrences of the literals in C is the number of outgoing edges from the literals in C to its gates.
We say that a truth assignment τ to the variables of a circuit C satisfies a gate g in C if τ
makes the gate g have value 1, and that τ satisfies the circuit C if τ satisfies the output gate of C.
A circuit C is satisfiable if there is a truth assignment to the input variables of C that satisfies C.
The weight of an assignment τ is the number of variables assigned value 1 by τ .
A parameterized problem Q is a subset of Ω∗ × N, where Ω is a fixed alphabet. Each instance
of the parameterized problem Q is a pair (x, k), where k ∈ N is called the parameter. We say that
the parameterized problem Q is fixed-parameter tractable (FPT) [10], if there is a (parameterized)
algorithm, also called an FPT-algorithm, that decides whether an input (x, k) is a member of Q in
time f (k)·|x|O(1) , where f is a computable function. Let FPT denote the class of all fixed-parameter
tractable parameterized problems.
A parameterized problem Q is FPT-reducible to a parameterized problem Q0 if there is an
algorithm, called an FPT-reduction, that transforms each instance (x, k) of Q into an instance
(x0 , k 0 ) of Q0 in time f (k) · |x|O(1) , such that k 0 ≤ g(k) and (x, k) ∈ Q if and only if (x0 , k 0 ) ∈ Q0 ,
where f and g are computable functions. By FPT-time we denote time of the form f (k) · |x|O(1) ,
where f is a computable function and |x| is the input instance size.

7

Based Son the notion of FPT-reducibility, a hierarchy of parameterized complexity, the Whierarchy t≥0 W[t], where W[t] ⊆ W[t + 1] for all t ≥ 0, has been introduced, in which the 0-th level
W[0] is the class FPT. The hardness and completeness have been defined for each level W[i] of the
W-hierarchy for i ≥ 1 [10]. It is commonly believed that W[1] 6= FPT (see [10]). The W[1]-hardness
has served as the main working hypothesis of fixed-parameter intractability.
The class W[SAT] contains all parameterized problems that are FPT-reducible to the weighted
satisfiability of Boolean formulas. It contains the classes W[t], for every t ≥ 0. Boolean formulas can
be represented (in polynomial time) by Boolean circuits that are in the normalized form (see [10]). In
the normalized form every (nonvariable) gate has outdegree at most 1, and the gates are structured
into alternating levels of ors-of-ands-of-ors.... Therefore, the underlying undirected graph of the
circuit with the input variables removed is a tree; the input variables can be connected to any gate
in the circuit, including the output gate. The class W[P] contains all parameterized problems that
are FPT-reducible to the weighted satisfiability of Boolean circuits of polynomial size, and contains
the class W[SAT].
Let O be a parameterized minimization problem, and ρ : N → R≥1 a computable function such
that ρ(k) ≥ 1 for every k ≥ 1. A decision algorithm A is an FPT cost approximation algorithm for O
with approximation ratio ρ [7], if for every input (x, k) ∈ Σ∗ × N, its output satisfies the following:
• If k ≤ OP T (x), then A rejects (x, k), and
• if k ≥ ρ(OP T (x)) · OP T (x), then A accepts (x, k).
Furthermore, A runs in FPT-time.
The Exponential Time Hypothesis (ETH) states that the satisfiability of k-cnf Boolean formulas,
where k ≥ 3, is not decidable in subexponential-time O(2o(n) ), where n is the number of variables
in the formula. ETH has become a standard hypothesis in complexity theory for proving hardness
results that is closely related to the computational intractability of a large class of well-known NPhard problems, measured from a number of different angles, such as subexponential-time complexity,
fixed-parameter tractability, and approximation.
The asymptotic notation O∗ suppresses a polynomial factor in the input length.
Colored Path and Colored Path-Con. For a set S, we denote by 2S the power set of S.
Let G = (V, E) be a graph, let C ⊂ N be a finite set of colors, and let χ : V −→ 2C . A vertex
v inSV is empty if χ(v) = ∅. A color c appears on, or is contained in, a subset S of vertices if
c ∈ v∈S χ(v).
Sr For two vertices u, v ∈ V (G), ` ∈ N, a u-v path P = (u = v0 , . . . , vr = v) in G is
`-valid if | i=0 χ(vi )| ≤ `; that is, if the total number of colors appearing
on the vertices of P is
S
at most `. A color c ∈ C is connected in G, or simply connected, if c∈C(v) {v} induces a connected
subgraph of G. The graph G is color-connected, if for every c ∈ C, c is connected in G.
For an instance (G, C, χ, s, t, k) of Colored Path or Colored Path-Con, if s and t are
nonempty vertices, we can remove their colors and decrement k by |χ(s) ∪ χ(t)| because their colors
appear on every s-t path. If afterwards k becomes negative, then there is no k-valid s-t path in G.
Moreover, if s and t are adjacent, then the path (s, t) is a path with the minimum number of colors
among all s-t paths in G. Therefore, we will assume:
Assumption 2.2. For an instance (G, C, χ, s, t, k) of Colored Path or Colored Path-Con,
we can assume that s and t are nonadjacent empty vertices.
Definition 2.3. Let s, t be two designated vertices in G, and let x, y be two adjacent vertices in
G such that χ(x) = χ(y). We define the following operation to x and y, referred to as a color

8

contraction operation, that results in a graph G0 , a color function χ0 , and two designated vertices
s0 , t0 in G0 , obtained as follows:
• G0 is the graph obtained from G by contracting the edge xy, which results in a new vertex z;
• s0 = s (resp. t0 = t) if s ∈
/ {x, y} (resp. t ∈
/ {x, y}), and s0 = z (resp. t0 = z) otherwise; and
• χ0 : V (G0 ) −→ 2C is the function defined as χ0 (w) = χ(w) if w 6= z, and χ0 (z) = χ(x) = χ(y).
G is irreducible if there does not exist two vertices in G to which the color contraction operation is
applicable.
Lemma 2.4. Let G be a color-connected plane graph, C a color set, χ : V −→ 2C , s, t ∈ V (G),
and k ∈ N. Suppose that the color contraction operation is applied to two vertices in G to obtain
G0 , χ0 , s0 , t0 , as described in Definition 2.3. Then G0 is a color-connected plane graph, and there is
a k-valid s-t path in G if and only if there is a k-valid s0 -t0 path in G0 .
Proof. Let x and y be the two adjacent vertices in G to which the color contraction operation
is applied, and let z be the new vertex resulting from this contraction. It is clear that after the
contraction operation the obtained graph G0 is a plane color-connected graph.
Suppose that there is a k-valid s-t path in G, and let P = (s = v0 , . . . , vr = t) be such a path.
We can assume that P is an induced path. If no vertex in {x, y} is on P , then P 0 = P is a k-valid
s0 -t0 path in G0 . If exactly one vertex in {x, y}, say x, is on P , then since the color set of every vertex
other than x on P is the same before and after the contraction operation, and since χ0 (z) = χ(x),
the path P 0 obtained from P by replacing x with z is a k-valid s0 -t0 in G0 . (Note that if x = s then
s0 = z, and replacing x with z on P is obsolete in this case.) Finally, if both x and y are on P , then
since P is induced, x and y must appear consecutively on P . Without loss of generality, assume
x = vi and y = vi+1 , for some i ∈ {0, . . . , r − 1}. Since the color set of every vertex other than x
and y on P is the same before and after the operation, and since χ0 (z) = χ(x) = χ(y), the path
P 0 = (s0 = v0 , . . . , vi−1 , z, vi+1 , . . . , t = vr ) is a k-valid s0 -t0 path in G0 .
Conversely, suppose that there is a k-valid s0 -t0 path in G0 , and let P 0 = (s0 = v00 , . . . , vp0 = t0 ),
where p > 0, be such a path. If z does not appear on P 0 then P 0 is a k-valid s-t path in G.
Otherwise, z = vi0 for some i ∈ {0, . . . , p}. If i = 0 and P 0 consists only of vertex z, then since
χ(x) = χ(y) = χ0 (z), either s = t, and in which case there is a trivial k-valid s-t path in G, or
s 6= t, and in this case P = (x, y) is a k-valid s-t path in G. Otherwise, when i = 0 we must have
s = x or s = y, vi0 ∈ G for i ∈ [p], and t0 = t; without loss of generality, assume that s = x. Since
z is adjacent to v10 , either x = s or y (or both) is adjacent to v10 . Since χ(x) = χ(y) = χ0 (z), if x
is adjacent to v10 then P = (s = x, v10 , . . . , vp0 = t0 ) is a k-valid s-t path in G, and if y is adjacent
to v10 then P = (s = x, y, v10 , . . . , vp0 = t0 ) is a k-valid s-t path in G. The case is similar if i = p.
0
0 , then the path
Suppose now that i 6= 0 and i 6= p. If x (resp. y) is adjacent to both vi−1
and vi−1
0 , x, v 0 , . . . , v 0 = t) (resp. P = (s, v 0 , . . . , v 0 , y, v 0 , . . . , v 0 = t) is a k-valid
P = (s, v10 , . . . , vi−1
p
p
1
i+1
i−1
i+1
0 , and the other vertex
s-t-path in G; otherwise, one vertex in {x, y}, say x, must be adjacent to vi−1
0 . In this case the path P = (s, v 0 , . . . , v 0 , x, y, v 0 , . . . , v 0 = t) is a
y must be adjacent to vi+1
p
1
i−1
i+1
k-valid s-t-path in G.

3

Hardness Results

In this section, we study the complexity and the parameterized complexity of Colored Path and
Colored Path-Con and their geometric counterparts Obstacle Removal and Connected
Obstacle Removal. We start by showing that both problems are NP-hard, even when restricted
to graphs of small outerplanarity and pathwidth.
9

O12
O

O22

Oi2

s
Z0 O11 Z1 O21 Z2

s

t
Zi−1 Oi1 Zi

x2

x1

Om2
Zm−1 Om1 Zm

y1

xm

xi

t

zi

z1
y2

yi

ym

Figure 2: Illustration of the construction in the proof of Theorem 3.1. The left figure shows the
geometric instance of Colored Path, and the right figure the graph associated with it.
Theorem 3.1. Colored Path, restricted to outerplanar graphs of pathwidth at most 2 and in
which every vertex contains at most one color, is NP-complete.
Proof. It is clear that Colored Path is in NP. To show its NP-hardness, we reduce from the
NP-hard problem Vertex Cover [15]. Let (G, k) be an instance of Vertex Cover, where
V (G) = {v1 , . . . , vn } and E(G) = {e1 , . . . , em }. In the rest of the proof, when we write e = uw
for an edge e in E(G), we assume that u = vi and w = vj such that i < j (i.e., the vertex of
smaller index always appears first). Although not necessary for the proof, we first describe an
instance I of Obstacle Removal whose associated
graph is the desired instance of Colored
S
1
2
{O
Path. The regions of I are O ∪ {Z0 , . . . , Zm } ∪ m
i , Oi }, depicted in Figure 2 (left figure).
i=1
The obstacles of I are defined as follows. For each vertex vj ∈ V (G), the obstacle corresponding to
vj is the polygon whose boundary is the boundary of the region formed by the union of O, each Oi1
such that
, and each Oi2 such ei = vp vj . More formally, the obstacle corresponding to vj is
S ei = vj1vqS
∂(O∪ ei =vj vq Oi ∪ ei =vp vj Oi2 ). The graph associated with I, GI , is defined as follow. Each (empty)
region Zi , i = 0, . . . , m, corresponds to a vertex zi ∈ V (GI ), where Z0 corresponds to s and Zm to
t. Each region Oi1 , i ∈ [m], corresponds to a vertex yi , and each region Oi2 , i ∈ [m], corresponds
to a vertex xi . The set of edges E(GI ) is E(GI ) = {zi−1 xi , zi−1 yi , xi yi , zi xi , zi yi | i ∈ [m]}. The
color function χ : V (GI ) −→ 2C , where C = [n], is defined as follows: χ(zi ) = ∅, for i = 0, . . . , m;
χ(xi ) = {j} and χ(yi ) = {p}, where ei = vp vj , for i ∈ [m]. This completes the construction of GI ;
see Figure 2 (right figure) for illustration. It is easy to see that GI is outerplanar and has pathwidth
at most 2.
Define the reduction from Vertex Cover to Colored Path that takes an instance (G, k) to
the instance (GI , C, χ, s, t, k). Clearly, this reduction is polynomial-time computable. Suppose that
Q, where |Q| = r ≤ k, is a vertex cover of G. Consider the s-t path P = (s, w1 , z1 , , . . . , wm , zm ) in
GI , where wi = yi if edge ei = vp vq is covered by vp , and wi = xi otherwise, for i ∈ [m]. Clearly
this is a k-valid s-t path in GI since each edge ei is covered by a vertex in Q, each wi is colored
by the index of one of the vertices in Q, and each vertex in GI (and hence each wi ) contains at
most one color. Conversely, suppose that P is a k-valid s-t path in GI . By construction of GI ,
P has to contain at least one vertex from {xi , yi }, for each i ∈ [m]. If P contains both xi and yi ,
for some i ∈ [m], then clearly, from the construction of P , P must contain either (zi−1 , xi , yi , zi )
or (zi−1 , yi , xi , zi ), as a subpath, and we can shortcut this subpath by removing one of xi , yi , to
obtain another k-valid s-t path in GI . Therefore, without loss of generality, we may assume that P
contains exactly one vertex wi from {xi , yi }, for i ∈ [m]. Now define the set of vertices Q in G as
the vertices in G whose indices are the colors appearing on (the wi ’s in) P . More formally, define
Q = {vp | wi = xi ∈ P ∧ ei = vq vp } ∪ {vp | wi = yi ∈ P ∧ ei = vp vq }. Since P is a k-valid path
in GI , the total number of colors appearing on {w1 , . . . , wm } is at most k. Notice that the color of

10

each of xi , yi is the index of a vertex in G that covers edge ei . It follows that the set Q of vertices
in G, that are the indices of the colors on P , form a k-vertex cover of G.

s

t

zi

z1
y1

xm

xi

x2

x1

yi

y2

ym

Figure 3: Illustration of the proof of Corollary 3.2.
Corollary 3.2. Colored Path-Con, restricted to 2-outerplanar graphs of pathwidth at most 3,
is NP-complete.
Proof. This follows directly from the NP-hardness reduction in the proof of Theorem 3.1 by observing
the following. The graph GI resulting from the reduction is outerplanar. We can add a new vertex
to the outer face of GI (see Figure 3) containing all colors that appear on GI , and add edges between
the new vertex and all vertices in GI . The obtained graph is color-connected and has pathwidth at
most 3.
Assuming ETH, the following corollary rules out the existence of subexponential-time algorithms
for Colored Path-Con (and hence for Colored Path), even for restrictions of the problem to
graphs of small outerplanarity, pathwidth, and maximum number of occurrences of each color:
Corollary 3.3. Unless ETH fails, Colored Path-Con, restricted to 2-outerplanar graphs of
pathwidth at most 3 and in which each color appears at most 4 times, is not solvable in O(2o(n) )
time, where n is the number of vertices in the graph.
Proof. It is well known, and follows from [22] and the standard reduction from Independent Set
to Vertex Cover, that unless ETH fails, Vertex Cover, restricted to graphs of maximum
degree at most 3, denoted VC-3, is not solvable in subexponential time. Starting from an instance
of VC-3 with n vertices, and observing that the reduction in the proof of Theorem 3.1 results in an
instance of Colored Path-Con whose number of vertices is O(n), of pathwidth at most 3, and in
which each color appears at most 4 times, proves the result.
Next, we shift our attention to studying the parameterized complexity of Colored Path and
Colored Path-Con. The reduction from Set Cover showing the NP-hardness of Colored
Path, given in several works [3, 18, 32], is in fact an FPT-reduction implying the W[2]-hardness
of Colored Path. We will strengthen this result, and show in the remainder of this section that
Colored Path is W[SAT]-hard. We will also prove the membership of the problem in W[P], which
adds a natural W[SAT]-hard problem to this class. The W[SAT]-hardness result shows that the
problem is hopeless in terms of it having FPT-algorithms. We start by showing that the problem
remains W[1]-hard, even when restricted to instances of small pathwidth (and hence small treewidth)
and maximum number of occurrences of each color. We then show that the problem remains W[1]hard even when parameterized by both k and the length of the sought path.
11

uji

C1

Cj−1

Cj

Cj+1

Ck

C1

Cj−1

Cj

Cj+1

Ck

C10

0
Cj−1

Cj0

0
Ck−1

Figure 4: Illustration of the construction of the gadget Gi,j in the proof of Lemma 3.5.

12

zj

zj−1
C10

0
Cj−1

G1,1

s = z0

Gi,1

GN,1

0
Ck−1

Cj0

G1,j

z1

zj−1

Gi,j

GN,j

G1,k

zj

zk−1

Gi,k

zk = t

GN,k

Figure 5: Illustration of the construction of G0 in the proof of Lemma 3.5.
Remark 3.4. Before we prove our parameterized hardness results for Colored Path, we remark
that we can obtain equivalent hardness results for Obstacle Removal using the following generic
realization of instances of Colored Path as instances of Obstacle Removal. Given an instance
(G, C, χ, s, t, k) of Colored Path, we define an equivalent instance of Obstacle Removal as
follows. We start by fixing a straight-line plane embedding Π of G, which always exists by Fáry’s
theorem [13]. Moreover, we can compute such an embedding in linear time [8]. We define the
starting and finishing positions of the path as the images of vertices s and t under Π, respectively.
To force the path to go along the edges of G, we correspond with every edge a “corridor” by putting
on both sides of the image of the edge k + 1 trapezoids as shown in Figure 6. The only possible
way to move along the vertices of the graph G without intersecting more than k obstacles is to move
within these corridors. Finally, for each color c ∈ C and every vertex v ∈ V (G) such that c ∈ χ(v),
we create a rectangle around the image of the vertex v under Π that intersects all the trapezoids
corresponding to the edges incident to v. We define the obstacle corresponding to the color c in the
geometric instance to be the union of these rectangles. This disallows the use of less than k + 1
trapezoid obstacles to go through a vertex v of G without intersecting all the obstacles representing
the color set χ(v). Note that the only thing that is affected by this geometric realization is the number
of obstacles that overlap at a region, which corresponds to the number of colors on the vertex in the
graph that corresponds to the region; this number might increase by at most 2.
Lemma 3.5. Colored Path, restricted to instances of pathwidth at most 4 and in which each
vertex contains at most one color and each color appears on at most 2 vertices, is W[1]-hard parameterized by k.
Proof. We reduce from the W[1]-hard problem Multi-Colored Clique [17]. Let (G, k) be an
instance of Multi-Colored Clique, where V (G) is partitioned into the color classes C1 , . . . , Ck .
Let Cj = {uji | i ∈ [|Cj |]}. We describe how to construct an instance (G0 , C 0 , χ0 , s, t, k 0 ) of Colored
Path. For an edge e ∈ G, associate a distinct color ce , and define C 0 = {ce | e ∈ E(G)}. To simplify
13

t

t

s

s

Figure 6: Illustration of the realization of an instance of Colored Path as an instance of Obstacle
Removal.
the description of the construction, we start by defining a gadget that will serve as a building block
for this construction.
For a vertex uji in color class Cj , we define the gadget Gi,j as follows. Create a copy of each
color class Cj 0 , j 0 6= j, and remove from each Cj 0 all copies of vertices that are not neighbors of uji
0
in G. Let the resulting copies of the color classes be C10 , . . . , Ck−1
. We define the color of a copy
j
j
0
0
0
v of a neighbor v of ui as χ (v ) = {ce }, where e = ui v. Next, we introduce k − 2 empty vertices
yr , r ∈ [k − 2]. For r ∈ [k − 2], we connect all vertices in Cr0 to yr , and connect yr to all vertices in
0
0
as the first and last
Cr+1
. This completes the construction of gadget Gi,j ; we refer to C10 and Ck−1
color classes in gadget Gi,j , respectively. See Figure 4 for illustration of Gi,j . Observe that every
0
path from a vertex in C10 to a vertex in Ck−1
contains exactly one vertex from each Cr0 , r ∈ [k − 1],
and contains all vertices yr , r ∈ [k − 2]. Therefore, any such path contains the colors of exactly
k − 1 distinct edges that are incident to uji .
We finish the construction of G0 by introducing k +1 new empty vertices z0 , . . . , zk , and connecting them as follows. For each color class Cj , j ∈ [k], and each vertex uji ∈ Cj , we create the gadget
Gi,j , connect zj−1 to each vertex in the first color class of Gi,j , and connect each vertex in the last

color class of Gi,j to zj . Let G0 be the resulting graph. Finally, we set s = z0 , t = zk , and k 0 = k2 .
See Figure 5 for illustration. This completes the construction of the instance (G0 , C 0 , χ0 , s, t, k 0 ) of
Colored Path. Observe that each vertex in G0 contains at most one color, and that each color ce
0
0
of an edge e = uji uji0 in G, appears on exactly two vertices in G0 : the copy of uji0 in the gadget Gi,j
0
of uji , and the copy of uji in the gadget Gi0 ,j 0 of uji0 .
Clearly, the reduction that takes an instance (G, k) of Multi-Colored Clique and produces
the instance (G0 , C 0 , χ0 , s, t, k 0 ) of Colored Path is computable in FPT-time. To show its correctness, suppose that (G, k) is a yes-instance of Multi-Colored Clique, and let Q be a k-clique
in G. Then Q contains a vertex from each Cj , for j ∈ [k]. For a vertex uji ∈ Q, let Gi,j be its
gadget, and define the path Pj as follows. In each color class in Gi,j , pick the unique vertex that
is a copy of a neighbor of uji in Q; define Pj to be the path in Gi,j induced by the picked vertices,
plus the empty vertices yr , r ∈ [k − 2], that appear in Gi,j . Finally, define P to be the s-t path in
G0 whose edges are: the (unique) edge between zr−1 and an endpoint of Pr , Pr , and the (unique)
edge between an endpoint of Pr and zr , for r ∈ [k]. To show that P is k 0 -valid, observe that all
the nonempty vertices in P are vertices whose color is the color of an edge between
 two vertices in
Q. This shows that the number of colors that appear on P is at most k 0 = k2 , and hence, P is

14

k 0 -valid. It follows that (G0 , C 0 , χ0 , s, t, k 0 ) is a yes-instance of Colored Path.
Conversely, suppose that P is a k 0 -valid s-t path in G0 . Then P 0 must start at s, visit the gadgets
of exactly k vertices ujij ∈ Cj , for j ∈ [k], ij ∈ [|Cj |], and end at t. We claim that Q = {ujij | j ∈ [k]}
is a clique in G. Recall that the subpath of P that traverses a gadget Gi,j of ujij contains the colors
of exactly k − 1 edges that are incident to ujij . Therefore, the total number of occurrences of colors

(counting multiplicities) on P is precisely (k − 1)k. Since P is k2 -valid, and each color ce of an edge
e in G appears exactly twice in G0 , it follows that each color that appears on P appears exactly
twice on P . This is only possible if the gadgets corresponding to the two endpoints of the edge are
traversed by P , and hence, both endpoints of the edge are in Q. Therefore, P contains the colors
of k 0 = k2 edges, whose both endpoints are in Q. Since |Q| = k, it follows that Q is a k-clique in
G, and that (G, k) is a yes-instance of Multi-Colored Clique.
Lemma 3.6. Colored Path, parameterized by both k and the length of the path `, is in W[1].
Proof. To prove membership in W[1], we use the characterization of the class W[1] given by Chen
et al. [6]:
A parameterized problem Q is in W[1] if and only if there is a computable function h
and a nondeterministic FPT algorithm A for a nondeterministic-RAM machine deciding
Q, such that, for each instance (x, k 0 ) of Q (k 0 is the parameter), all nondeterministic
steps of A take place during the last h(k 0 ) steps of the computation.
Therefore, to show that Colored Path is in W[1], it suffices to exhibit such a nondeterministic
FPT algorithm A. A works as follows: It guesses a set C 0 of k colors and guesses a sequence of ` − 1
internal vertices v1 , . . . , v`−1 of the path. Then it verifies that (s = v0 , v1 , . . . , v`−1 , v` = t) is a path
in G, and that χ(vi ) ⊆ C 0 , for i = 0, . . . , `. It is not difficult to see that this verification can be
implemented in h(k, `) steps, where h is a computable function.
By Lemma 2.4, we can assume that in an instance of Colored Path, no two adjacent vertices
are empty. With this assumption in mind, if the instance satisfies that each vertex contains at most
one color and that each color appears on at most 2 vertices, then any k-valid s-t path has length at
most 4k + 1. It follows from Lemma 3.5 and Lemma 3.6 that:
Theorem 3.7. Colored Path, parameterized by both k and the length of the path `, is W[1]complete.
Theorem 3.8. Colored Path, restricted to instances of pathwidth at most 4 and in which each
vertex contains at most one color and each color appears on at most 2 vertices, is W[1]-complete
parameterized by k.
Next, we show that Colored Path sits high up in the parameterized complexity hierarchy.
We start by showing its membership in W[P]:
Theorem 3.9. Colored Path, parameterized by k, is in W[P].
Proof. We give an FPT-reduction from Colored Path to Weighted Boolean Circuit Satisfiability (WBCS) on polynomial size (monotone) circuits. Given an instance (G, C, χ, s, t, k) of
Colored Path, we construct an instance (B, k) of WBCS, where B is a circuit whose output gate
is an or-gate, as follows. By Assumption 2.2, we can assume that s and t are nonadjacent empty
vertices. By Lemma 2.4, we can also assume that no two adjacent vertices are empty. For each
15

color c ∈ C, we create a variable xc ; those are the input variables to B. In addition to the output
gate, B contains n = |V (G)| layers of gates, where each layer, except the first, consists of two rows
of gates, Ui , Li , for i = 2, . . . , n, and the first layer consists of one row L1 of gates. The layers of B
are defined as follows.
Each gate in L1 is an and-gate gv that corresponds to a neighbor v of s; the input to gv is the
set of input variables corresponding to the colors in χ(v). Suppose that row Li in layer i, i ≥ 1,
has been defined, and we describe how Ui+1 and Li+1 are defined. For every vertex v ∈ V (G) with
a neighbor u such that u has a corresponding and-gate gu2 in Li , we create an or-gate gv1 in Ui+1
and an and-gate gv2 in Li+1 corresponding to v; we connect the output of each and-gate gu2 in Li
corresponding to neighbor u of v to the input of or-gate gv1 in Ui+1 , and connect the output of the
or-gate gv1 and each input variable xc such that c ∈ χ(v) to the and-gate gv2 in Li+1 . If v = t,
then we connect the output of the and-gate gv2 to the output gate of the circuit. This completes
the description of B. Clearly, the reduction that takes (G, C, χ, s, t, k) to (B, k) runs in polynomial
time, and hence in FPT-time. Next, we prove its correctness.
First observe that the only gates in B that are connected to its output gate are the and-gates
that correspond to t. Second, every gate in B corresponds to a vertex that is reachable from s in
G. Moreover, for every and-gate g corresponding to a vertex v, and every s-v path in G, the truth
assignment that assigns 1 to the variables corresponding to the colors of this path satisfies g.
Suppose now that (G, C, χ, s, t, k) is a yes-instance of Colored Path. Then there is an s-t
k-valid path P in G. Based on the above observations, the assignment that assigns xc = 1 if and
only if c ∈ χ(P ) is a satisfying assignment to B of weight at most k. Conversely, suppose that B
has a satisfying assignment τ of weight at most k. Then there is an and-gate g corresponding to
t that is satisfied by τ , and there is a path in B from a gate corresponding to neighbor of s in L1
to g, all of whose gates are satisfied by τ . It is easy to verify that this path in B corresponds to an
s-t path all of whose colors correspond to the input variables assigned 1 by τ , and hence this path
is k-valid.

G1
ing

outg
Gi
Gr

ing

Gi

G1

Gr

outg

Figure 7: Illustrations of the construction of the gadgets for an or-gate (top) and an and-gate
(bottom) in the proof of Theorem 3.10.

16

Theorem 3.10. Colored Path, parameterized by k, is W[SAT]-hard.
Proof. We give an FPT-reduction from the W[SAT]-complete problem Monotone Weighted
Boolean Formulas Satisfiability (M-WSAT) [10].
Recall that a Boolean formula corresponds to a circuit in the normalized form. Therefore, we
can assume that the input instance of M-WSAT is (B, k), where B is a monotone Boolean circuit
in which each (non-variable) gate has fan-out at most 1, and the gates of B are structured into
alternating levels of ors-of-ands-of-ors. We construct an instance (G, C, χ, s, t, k) of Colored
Path as follows.
First, we let C = [n], where color i will represent input variable xi in B. We define G from B
by defining a gadget for each gate in B recursively, starting the recursive definition at the output
gate of B. For a gate g in B, its gadget is defined by distinguishing the type of g as follows.
If g is an and-gate, let g1 , . . . , gr be the or-gates, and xi1 , . . . , xip be the input variables that feed
into g. The gadget of g is defined as follows. First, create two empty vertices ing and outg , which
will serve as the “entry” and “exit” vertices of the gadget for g, respectively. For each xij , j ∈ [p],
create a vertex vj colored with color ij and an entry vertex v0 and an exit vertex vp+1 ; form a path
G0 consisting of the vertices v0 , v1 , . . . , vp , vp+1 . For each or-gate gi , i ∈ [r], recursively construct
the gadget Gi for gi . Connect all these gadgets G0 , . . . , Gr serially in arbitrary order, starting by
identifying ing with the entry vertex of the first gadget, the exit vertex of the first gadget with the
entry of the second, ..., and the exit vertex of the last gadget with outg . See Figure 7 (bottom) for
illustration.
If g is an or-gate, let g1 , . . . , gr be the and-gates, and xi1 , . . . , xip be the input variables that
feed into g. The gadget of g is defined as follows. First, create two empty vertices ing and outg ,
which will serve as the “entry” and “exit” vertices of the gadget for g, respectively. For each xij ,
j ∈ [p], create a vertex vj colored with color ij , and connect each vj to ing and outg . For each
and-gate gi , i ∈ [r], recursively construct the gadget Gi for gi . Connect all these gadgets G1 , . . . , Gr
in parallel by identifying all the entry vertices of G1 , . . . , Gr with ing and all their exit vertices with
outg . This complete the description of G. It is not difficult to see that since B with its input
variables removed is a tree, the above construction runs in polynomial time and results in a planar
graph G. See Figure 7 (top) for illustration.
Finally, set s and t to be the entry and exit vertices of the gadget corresponding to the output
gate of B. Clearly, the reduction that takes (B, k) and produces (G, C, χ, s, t, k) runs in FPT-time.
Next, we prove its correctness.
We will prove the following statement: For any gate g in B, and any assignment τ to B that
assigns variables xi1 , . . . , xip the value 1, and all other variables the value 0, τ satisfies g if and only
if there is a path P in G from the entry vertex to the exit vertex of the gadget corresponding to g
such that P uses a subset of the colors {i1 , . . . , ip }. Clearly, proving the aforementioned statement
implies that there is a k-valid s-t path in G if and only if there is an assignment of weight at most
k that satisfies the output gate of B, and hence satisfies B.
We prove the above statement by induction on the depth of the gate g in B. The base case is
when g has depth 1. In this case the input to g consists only of input variables. Suppose first that
g is an or-gate, and let τ be an assignment that assigns exactly variables xi1 , . . . , xip the value 1.
Then τ satisfies g if and only if xij is an input variable to g, for some j ∈ [p], which is true if and
only if there is a path from the entry vertex of the gadget for g to its exit vertex that uses color
ij . Suppose now that g is an and-gate, and let τ be an assignment that assigns exactly variables
xi1 , . . . , xip the value 1. Then τ satisfies g if and only if the input variables to g form a subset S of
{xi1 , . . . , xip }; let η(S) be the indices of the variables in S. Since the gadget for g consists of a path
P between the entry and exit vertices of the gadget for g such that χ(P ) = η(S), the statement
17

follows.
Suppose, by the inductive hypothesis, that the statement we are proving is true for any gate g
of depth 1 ≤ a < `, and let g be a gate of depth `. Let xj1 , . . . , xjq be the input variables to g, and
g1 , . . . , gr be the input gates to g. We again distinguish two cases based on the type of g.
Gate g is an or-gate. Let τ be an assignment that assigns exactly variables xi1 , . . . , xip the value
1. Suppose first that τ satisfies g. Then either τ satisfies an input variable xjz , z ∈ [q], or τ satisfies
an input and-gate gy , y ∈ [r]. If τ satisfies xjz then there is a path between the entry and exit
vertices of the gadget for g that uses color jz . Otherwise, τ satisfies gy , y ∈ [r], and by the inductive
hypothesis applied to gy , there is a path Py between the entry and exit vertices of the gadget for
gy such that χ(Py ) ⊆ {i1 , . . . , ip }. From the way the gadget for g was constructed, it follows that
Py is also a path between the entry and exit vertices of the gadget for g. To prove the converse,
suppose that there is a path Pg between the entry and exit vertices of the gadget for g that uses
a subset of colors in {i1 , . . . , ip }. Either Pg is a path whose only internal vertex corresponds to an
input variable, and in such case the input variable is in {xi1 , . . . , xip }, and g is satisfied; or Pg is a
path between the entry and exit vertices of the gadget for an and-gate gy that feeds into g, and by
the inductive hypothesis, τ satisfies gy and also g.
Gate g is an and-gate. Let τ be an assignment that assigns exactly variables xi1 , . . . , xip the value
1. Suppose first that τ satisfies g. Then τ assigns 1 to every input variable xjz to g, z ∈ [q]. Hence,
there is a path P between the entry and exit vertices of the gadget corresponding to xj1 , . . . , xjq
such that χ(P ) ⊆ {i1 , . . . , ip }. Assignment τ also satisfies each or-gate gy , where y ∈ [r]. By the
inductive hypothesis, there is a path Py between the entry and exit vertices of the gadget for gy such
that χ(Py ) ⊆ {i1 , . . . , ip }. From the construction of g, it follows that the path between the entry
and exit vertices of the gadget for g, which is Pg = P ◦ P1 ◦ · · · ◦ Pr , satisfies χ(Pg ) ⊆ {i1 , . . . , ip }.
Conversely, suppose that there is a path Pg between the entry and exit vertices of the gadget for
g such that χ(Pg ) ⊆ {i1 , . . . , ip }. Then Pg can be decomposed into a subpath P that traverses
the vertices corresponding to xj1 , . . . , xjq , and subpaths P1 , . . . , Pr , where Py is a subpath between
the entry and exit vertices of the gadget for gy . Since P traverses the vertices corresponding to
xj1 , . . . , xjq , it follows that {xj1 , . . . , xjq } ⊆ {xi1 , . . . , xip }. Since Py , y ∈ [r], is a subpath between
the entry and exit vertices of the gadget for gy , by the inductive hypothesis, it follows that τ satisfies
gy . It follows that τ assigns 1 to all input variables to g and satisfies all the input or-gates to g,
and hence, τ satisfies g.
As it turns out, we can even exclude FPT cost approximation algorithms for Colored Path.
We first need the following theorem:
Theorem 3.11 (Corollary 5 of [27]). Unless FPT= W[2], Monotone Weighted Boolean Circuit Satisfiability for circuits with depth 4 is not FPT cost approximable.
Corollary 3.12. Unless FPT= W[2], Colored Path parameterized by k is not FPT cost approximable.
Proof. We reduce from Monotone Weighted Boolean Circuit Satisfiability for circuits
with depth 4. Let C be a monotone circuit of depth at most 4. We can transform C into a monotone
circuit in the normalized form (see the proof of the Normalization Theorem in Section 23.2.2 of [10]
for more details). Since C has depth at most 4, this procedure terminates in polynomial time, results
in a polynomial blow-up of the instance size, and preserves the solutions and their sizes. Finally, it
is not hard to see that the reduction in the proof of Theorem 3.10 preserves all the solutions and
their sizes.
18

Remark 3.13. A noteworthy remark that we close this section with, is to comment on the role
that planarity plays in the parameterized complexity of Colored Path-Con. If one drops the
planarity requirement on the instances of Colored Path-Con (i.e., considers Colored PathCon on general graphs), then it follows from the proof of Theorem 3.10 that the resulting problem is
W[SAT]-hard. This can be seen by adding a single vertex containing all colors, that serves as a “colorconnector,” to the instance of Colored Path produced by the FPT-reduction; this modification
results in an instance of the connected obstacle removal problem on apex graphs, establishing the
W[SAT]-hardness of this problem on apex graphs.

4

Structural Results

Let G be a color-connected plane graph, C a set of colors, and χ : V −→ 2C . In this section, we
present structural results that are the cornerstone of the FPT-algorithm for Colored Path-Con
presented in the next section. We start by giving an intuitive description of the plan for this section.
As mentioned in Section 1, the main issue facing a dynamic programming algorithm based on
tree decomposition, is how to upper bound, by a function of k and the treewidth, the number of
k-valid paths between (any) two vertices u and v that use color sets contained in a certain bag. As
it turns out, this number cannot be upper bounded as desired. Instead, we “represent” those paths
using a minimal set P of k-valid u-v paths, in the sense that any k-valid u-v path can be replaced
by a path from P that is not “worse” than it. To do so, it suffices to represent the k-valid u-v paths
that use color sets contained in a third vertex w, by a set whose cardinality is a function of k. This
will enable us to extend the notion of a minimal set of k-valid u-v paths w.r.t. a single vertex to
a representative set for the whole bag, which is the key ingredient of the dynamic programming
FPT-algorithm—based on tree decomposition—in the next section.
As it turns out, the paths that matter are those that use “external” colors w.r.t. w (defined
below), since those colors have the potential of appearing on both sides of a bag containing w.
Therefore, the ultimate goal of this section is to define a notion of a minimal set P of k-valid u-v
paths with respect to w (Definition 4.4), and to upper bound |P| by a function of k. Upper bounding
|P| by a function of k turns out to be quite challenging, and requires ideas and topological results
that will be discussed later in this section.
Throughout this section, we shall assume that G is color-connected. We start with the following
simple observation:
Observation 4.1. Let x, y ∈ V (G) be such that there exists a color c ∈ C that appears on both x
and y. Then any x-y vertex-separator in G contains a vertex on which c appears.
Proof. This follows because color c is connected.
Let G0 be a plane graph, let w ∈ V (G0 ), and let f be the face in G0 − w such that w is interior to
f ; we call f the external face w.r.t. w in G0 , and the vertices incident to f external vertices w.r.t. w
in G0 . A color c ∈ C is an external color w.r.t. w in G0 , or simply external to w in G0 , if c appears
on an external vertex w.r.t. w in G0 ; otherwise, c is internal to w in G0 . The following observation
is easy to see:
Observation 4.2. Let G be a color-connected graph, and let w ∈ V (G). Let H be any subgraph of
G − w. If c is an external color to w in G − w and c appears on some vertex in H, then c is an
external color to w in H. This also implies that the set of internal colors to w in H is a subset of
the set of internal colors to w in G − w.

19

Definition 4.3. Let P = (w1 , . . . , wr ) be a path in a graph G, and let x, y ∈ V (G). Suppose that
we apply the color contraction operation to x and y, and let z be the new vertex resulting from this
contraction. We define an operation, denoted Λxy , that when applied to path P results in another
path Λxy (P ) defined as follows:
1. If {x, y} ∩ {w1 , . . . , wr } = ∅ then Λxy (P ) = P .
2. If {x, y} ∩ {w1 , . . . , wr } = {wi }, where i ∈ [r], then Λxy (P ) = (w1 , . . . , wi−1 , z, wi+1 , . . . , wr ).
3. If {x, y}∩{w1 , . . . , wr } = {wi , wj }, where i < j, then Λxy (P ) = (w1 , . . . , wi−1 , z, wj+1 , . . . , wr ).
For a set of paths P, we define Λxy (P) = {Λxy (P ) | P ∈ P}.
Definition 4.4. Let u, v, w ∈ V (G). A set P of k-valid u-v paths in G − w is said to be minimal
w.r.t. w if:
(i) There does not exist two paths P1 , P2 ∈ P such that χ(P1 ) ∩ χ(w) = χ(P2 ) ∩ χ(w);
(ii) there does not exist two paths P1 , P2 ∈ P such that χ(P1 ) ⊆ χ(P2 ); and
(iii) for any P ∈ P, there does not exist a u-v path P 0 in G − w such that χ(P 0 ) ( χ(P ).
Clearly, for any u, v, w ∈ V (G), a minimal set of k-valid u-v paths in G − w exists.
Observation 4.5. Let u, v, w ∈ V (G). Any set of u-v paths that is minimal w.r.t. w contains at
most one path whose vertices contain only internal colors w.r.t. w in G − w.
Proof. Since the external face f of w in G − w is a Jordan curve that separates w from any vertex
in G − w that is not incident to f , by Observation 4.1, any color that appears both on w and on
a vertex in G − w must appear on a vertex incident to f , and hence, must be external to w by
definition. Therefore, any path P containing only internal colors to w satisfies χ(P ) ∩ χ(w) = ∅.
The observation now follows from property (i) in Definition 4.4.
Lemma 4.6. Let u, v, w ∈ V (G), and let P be a minimal set of k-valid u-v paths in G − w. Suppose
that we apply the color contraction operation to an edge xy ∈ G − w, and let G0 , χ0 be the graph and
color function obtained from the contraction operation, respectively. Let P 0 = Λxy (P). Then P 0 is
a minimal set of k-valid paths w.r.t w in G0 .
Proof. Let H 0 be the subgraph of G0 − w induced by the edges of the paths in P 0 , and denote by
z the new vertex obtained from the contraction of the edge xy. We start by showing the following
claim:
Claim 1. For every P ∈ P, it holds that χ(Λxy (P )) = χ(P ).
Let P = (u = w1 , . . . , wr = v). Since χ0 (z) = χ(x) = χ(y), it follows from Definition 4.3 that
if |{x, y} ∩ {w1 , . . . , wr }| ≤ 1, then χ(Λxy (P )) = χ(P ). Now assume that {x, y} ∩ {w1 , . . . , wr } =
{wi , wj }, where i < j, and suppose to get a contradiction that χ(Λxy (P )) 6= χ(P ). Since Λxy (P ) =
(w1 , . . . , wi−1 , z, wj+1 , . . . , wr ), it follows that χ(Λxy (P )) ( χ(P ). However, G − w contains the
u-v path P 0 = (w1 , . . . , wi−1 , wi , wj , wj+1 , . . . , wr ), which satisfies χ(P 0 ) = χ(Λxy (P )) ( χ(P ); this,
together with P ∈ P, contradicts the minimality of P.
We now proceed to verify that P 0 is indeed minimal w.r.t. w. Properties (i) and (ii) in Definition 4.4 follow directly from Claim 1 and the minimality of P. To prove that property (iii)
holds, assume that there is a path P 0 ∈ P 0 , and a path Q0 in G0 − w between the endpoints of P 0
20

such that χ(Q0 ) ( χ(P 0 ). Let P be the path in P such that Λxy (P ) = P 0 . It is straightforward
to verify that G − w contains a u-v path Q that is either identical to Q0 , or obtained from Q0 by
replacing z by either a single vertex x or y, or by the pair x, y. Clearly, χ(Q) = χ(Q0 ). Since
χ(Q0 ) ( χ(P 0 ) = χ(P ) by Claim 1, it follows that χ(Q) ( χ(P ), contradicting the minimality of P.
It follows that Property (iii) holds, and the proof is complete.
To derive an upper bound on the cardinality of a minimal set P of k-valid u-v paths w.r.t. a
vertex w, we select a maximal set M of color-disjoint paths in P. We first upper bound |M| by
a function of k, which requires developing several results of topological nature. The key ingredient
for upper bounding |M| is showing that the subgraph induced by the paths in M has a u-v vertexseparator of cardinality O(k) (Lemma 4.11). We then upper bound |M| (Lemma 4.13) by upper
bounding the number of different traces of the paths of M on this small separator, and inducting
on both sides of the separator. Finally, we show (Theorem 4.14) that |P| is upper bounded by a
function of |M|, which proves the desired upper bound on |P|. We proceed to the details.
For the rest of this section, let u, v, w ∈ V (G), and let P be a set of minimal k-valid u-v paths
in G − w. Let M be a set of minimal k-valid color-disjoint u-v paths in G − w, and let M be the
subgraph of G − w induced by the edges of the paths in M.
Observation 4.7. If P ∈ M contains a color c that is external to w in M , then c appears on a
vertex in P that is incident to the external face to w in M .
Proof. By definition, c appears on a vertex x incident to the external face w.r.t. w in M . Since the
paths in M are pairwise color-disjoint and c appears on P , it follows that x is a vertex of P .
Lemma 4.8. Let G0 be a plane graph, and let x, y, z ∈ V (G0 ). Let x1 , . . . , xr , r ≥ 3, be the neighbors
of x in counterclockwise order. Suppose that, for each i ∈ [r], there exists an x-y path Pi containing
xi such that Pi does not contain z and does not contain any xj , j ∈ [r] and j 6= i. Then there exist
two paths Pi , Pj , i, j ∈ [r] and i 6= j, such that the two paths Pi , Pj induce a Jordan curve separating
{x1 , . . . , xr } \ {xi , xj } from z.
Proof. The proof is by induction on r ≥ 3. The base case is when r = 3. Consider the faces induced
by the two paths P1 and P2 in the embedding. If z and x3 are in two separate faces, then clearly
P1 and P2 induce a Jordan curve separating x3 from z, and we are done. Therefore, we can assume
that z and x3 are in the same face induced by P1 and P2 . Since P1 does not contain x2 , we can
continuously deform P1 into an isotopic non self-intersecting curve P10 w.r.t. x3 , x2 , z, that includes
xx1 , intersects edges xx2 and xx3 only at x, and intersects P2 only at x and y. Similarly, if P2 and
P3 do not separate z from x1 , then z and x1 are in the same face induced by P2 and P3 and we can
define a curve P30 that is isotopic to P3 w.r.t. x2 , x1 , z, and such that P30 contains xx3 , intersects
xx2 and xx1 only at x, and intersects P2 only at x and y. Now if z and x2 are in different faces
induced by P10 and P30 , then P10 and P30 separate z from x2 , and since P1 is isotopic to P10 w.r.t. z
and x2 , and P30 is isotopic to P3 w.r.t. z and x2 , it follows that P1 and P3 induce a Jordan curve
that separates x2 from z. Assume now that z and x2 are in the same face f induced by P10 and
P30 . Since P2 intersects with each of P10 and P30 precisely at x and y, it follows that P2 splits f
into two faces f1 , f2 , where xx2 , xx1 are two consecutive edges on the boundary of f1 and xx2 , xx3
are two consecutive edges on the boundary of f2 . Then, z must be interior to exactly one of the
two faces f1 , f2 . If z is interior to f1 , let f10 be the face induced by P10 and P2 and containing z.
Then f10 contains f1 , and does not contain x3 (because P10 intersects xx3 only at x). Therefore, f10 ,
and hence, P10 and P2 induce a Jordan curve that separates z from x3 . It follows that P1 , which is
isotopic to P10 w.r.t. x2 , x3 , z, and P2 induce a Jordan curve that separates z from x3 . Similarly, if

21

z is interior to f2 , then P30 , P2 induce a Jordan curve that separates z from x1 , and hence, P3 and
P2 induce a Jordan curve that separates z from x1 .
Assume inductively that the statement of the lemma is true for any 3 ≤ ` < r. By the inductive
hypothesis applied to x1 , . . . , xr−1 , there exist two paths Pi , Pj , i, j ∈ [r − 1] and i 6= j, such that
the two paths Pi , Pj induce a Jordan curve separating {x1 , . . . , xr−1 } \ {xi , xj } from z. If xr and
z are not in the same face induced by Pi , Pj , then Pi , Pj separate xr from z as well, and we are
done. Assume now that z and xr are in the same face f induced by Pi , Pj . Since Pi , Pj separate z
from {x1 , . . . , xr−1 } \ {xi , xj }, none of {x1 , . . . , xr−1 } \ {xi , xj } is interior to f , and hence, xr is the
only neighbor of x between xi and xj w.r.t. the rotation system of G0 , which implies w.l.o.g. that
x1 = xi and xr−1 = xj . By the inductive hypothesis applied to x1 , xr−1 , xr there are two paths in
P1 , Pr−1 , Pr that induce a Jordan curve that separates z from one of x1 , xr−1 , xr . Since P1 and Pr−1
do not separate xr from z, one of these two path must be Pr ; assume, w.l.o.g., that the two paths
are P1 and Pr . Since x1 and xr are consecutive neighbors in the rotation system, and since P1 , Pr do
not contain any of x2 , . . . , xr−1 , it follows that x2 , . . . , xr−1 are in the same face induced by P1 , Pr ,
and this face does not contain z because P1 , Pr separate z from xr−1 . It follows that P1 , Pr induce
a Jordan curve that separates z from x2 , . . . , xr−1 . This completes the inductive proof.
Lemma 4.9. Let G0 be a plane graph with a face f , and let u, v ∈ V (G0 ). Let u1 , . . . , ur , r ≥ 3, be
the neighbors of u. Suppose that, for each i ∈ [r], there exists a u-v path Pi in G0 containing ui and a
vertex incident to f different from v, and such that Pi does not contain any uj , j ∈ [r], j 6= i. Then
there exist two paths Pi , Pj , i, j ∈ [r], i 6= j, such that V (Pi ) ∪ V (Pj ) − {v} is a vertex-separator
separating {u1 , . . . , ur } \ {ui , uj } from v.
Proof. Create a new vertex y interior to f . Each path Pi , i ∈ [r], contains a vertex yi incident to
f and different from v; we define a new path Pi0 from u to y, consisting of the prefix of Pi up to
yi , and extending this prefix by adding a new edge between yi and the new vertex y. Note that we
can extend the rotation system of G0 in a straightforward manner to obtain a rotation system for
the plane graph resulting from adding y and the edges yi y to G0 , i ∈ [r]. Since v is the endpoint of
Pi and v 6= yi , it follows that v is not contained in Pi0 , for i ∈ [r]. By Lemma 4.8, there exist two
paths Pi0 , Pj0 , i, j ∈ [r], and i 6= j, such that the two paths Pi0 , Pj0 induce a Jordan curve separating
{u1 , . . . , ur }\{ui , uj } from v in G0 +y. It follows that V (Pi0 )∪V (Pj0 ) is a vertex-separator separating
{u1 , . . . , ur } \ {ui , uj } from v in G0 + y, and hence, V (Pi0 ) ∪ V (Pj0 ) − {y} ⊆ V (Pi ) ∪ V (Pj ) − {v} is
a vertex-separator separating {u1 , . . . , ur } \ {ui , uj } from v in G0 .
Lemma 4.10. Let x, y be two vertices in an irreducible subgraph G0 of G, and let f be a face in G0 .
Then there are at most two color-disjoint x-y paths in G0 that contain only colors that appear on f .
Proof. Suppose, to get a contradiction, that there are three color-disjoint x-y paths P1 , P2 , P3 in G0
that contain only colors that appear on f . We create a new vertex z interior to f and add edges
between z and each vertex incident to f . Note that we can extend the rotation system of G0 in a
straightforward manner to obtain a rotation system for the plane graph resulting from adding z and
the edges incident to it to G0 . Clearly, none of P1 , P2 , P3 contains z. Because the paths P1 , P2 , P3
are color-disjoint, both x and y must be empty vertices. Let v1 , v2 , v3 be the neighbors of x on
P1 , P2 , P3 , respectively. Since x is an empty vertex and G0 is irreducible, none of v1 , v2 , v3 is an
empty vertex, and hence each vi , i ∈ [3], must contain a color ci that appears on f . Since P1 , P2 , P3
are pairwise color-disjoint, it follows that no vertex in {v1 , v2 , v3 }\{vi } is contained in Pi , for i ∈ [3].
By Lemma 4.8, there is a vi , i ∈ [3], such that the two paths in {P1 , P2 , P3 } − Pi induce a Jordan
curve in G0 + z separating vi and z, and hence separating vi from each vertex incident to f . Since
ci appears on both vi and a vertex incident to f , by Observation 4.1, it follows that ci must appear
22

on a vertex in V (P1 ) ∪ V (P2 ) ∪ V (P3 ) − V (Pi ). This is a contradiction since ci appears on Pi and
the paths P1 , P2 , P3 are pairwise color-disjoint.
Qr
vr−1
Qr−1

P1r−1

Qi+1
u

vi
Qi

v
P1i

Q2

Q1

v1

P11
P1

Figure 8: Illustration for the proof of Lemma 4.11.
Lemma 4.11. Suppose that M is irreducible, then there exist paths P1 , P2 , P3 ∈ M such that
M − P1 − P2 − P3 has a u-v vertex-separator of cardinality at most 2k + 3.
Proof. By Observation 4.5 and Observation 4.2, M contains at most one path that contains only
internal colors w.r.t. w in M . Therefore, it suffices to show that M contains two paths P1 , P2 such
that M − P1 − P2 has a u-v vertex-separator of cardinality at most 2k + 3, assuming that every
path in M contains an external color w.r.t. w in M .
By Observation 4.7, every path in M passes through an external vertex w.r.t. w in M that
contains an external color to w in M . Because the paths in M are pairwise color-disjoint and u and
v are empty vertices, every path in M passes through a vertex on the external face of w in M that
is different from u and v. Let u1 , . . . , uq be the neighbors of u in M , and note that since u is empty
and M is irreducible, each ui , i ∈ [q], contains a color. Let P1 , . . . , Pq be the paths in M containing
u1 , . . . , uq , respectively, and note that since the paths in M are color-disjoint, no Pi passes through
uj , for j 6= i. By Lemma 4.9, there are two paths in P1 , . . . , Pq , say P1 , P2 without loss of generality,
such that V12 = V (P1 ) ∪ V (P2 ) − {v} is a vertex-separator that separates {u3 , . . . , uq } from v.
We proceed by contradiction and assume that M − = M − P1 − P2 does not have a u-v vertexseparator of cardinality 2k + 3. By Menger’s theorem [9], there exists a set D of r0 ≥ 2k + 3
vertex-disjoint u-v paths in M − . Since V12 separates {u3 , . . . , uq } from v in M , every u-v path in
M − intersects at least one of P1 , P2 at a vertex other than v. It follows that there exists a path in
{P1 , P2 }, say P1 , that intersects at least k + 2 paths in D at vertices other than v. Since the paths
in D are vertex-disjoint and incident to u, we can order the paths in D that intersect P1 around
u (in counterclockwise order) as hQ1 , . . . , Qr i, where r ≥ k + 2, and Qi+1 is counterclockwise from
Qi , for i ∈ [r − 1]. P1 intersects each path Qi , i ∈ [r], possibly multiple times. Moreover, since the
paths in M are pairwise color-disjoint, each intersection between P1 and a path Qi , i ∈ [r], must
23

occur at an empty vertex. We choose r − 1 subpaths, P11 , . . . , P1r−1 , of P1 satisfying the property
that the endpoints of P1i are on Qi and Qi+1 , for i = 1, . . . , r − 1, and the endpoints of P1i are the
only vertices on P1i that appear on a path Qj , for j ∈ [r]. It is easy to verify that the subpaths
P11 , . . . , P1r−1 of P1 can be formed by following the intersection of P1 with the sequence of (ordered)
paths Q1 , . . . , Qr . See Figure 8 for illustration.
Recall that the endpoints of P11 , . . . , P1r−1 are empty vertices. Since M is irreducible, no two
empty vertices are adjacent, and hence, each subpath P1i must contain an internal vertex vi that
contains at least one color. We claim that no two vertices vi , vj , 1 ≤ i < j ≤ r − 1, contain the
same color. Suppose not, and let vi , vj , i < j, be two vertices containing a color c. Since vi , vj are
internal to P1i and P1j , respectively, Q1 , . . . , Qr are vertex-disjoint u-v paths, and by the choice of the
subpaths P11 , . . . , P1r−1 , the paths Qi and Qi+1 form a Jordan curve, and hence a vertex-separator in
G, separating vi from vj . By Observation 4.1, color c must appear on a vertex in Qp , p ∈ {i, i + 1},
and this vertex is clearly not in P1 since P1 intersects Qp at empty vertices. Since every vertex in
M appears on a path in M, and c appears on P1 ∈ M and on a vertex not in P1 , this contradicts
that the paths in M are pairwise color-disjoint, and proves the claim.
Since no two vertices vi , vj , 1 ≤ i < j ≤ r, contain the same color, the number r − 1 of subpaths
1
P1 , . . . , P1r−1 is upper bounded by the number of distinct colors that appear on P1 , which is at
most k. It follows that r is at most k + 1, contradicting our assumption above and proving the
lemma.
Lemma 4.12. Let S be a minimal u-v vertex-separator in M . Let Mu , Mv be a partition of M − S
containing u and v, respectively, and such that there is no edge between Mu and Mv . For any vertex
x ∈ S, Mu is contained in a single face of Mv + x.
Proof. Let x ∈ S. It suffices to show that the subgraph F of M induced by V (Mu ) ∪ (S \ {x}) is
connected. This suffices because V (F ) and V (Mv + x) are disjoint, and hence every face in Mv + x
separates the vertices in V (F ) inside the face from those outside of it. We will show that F is
connected by showing that there is a path in F from each vertex in F to u ∈ V (F ). Let z ∈ V (F ).
If z ∈ S, then by minimality of S, there is a path from u to z whose internal vertices are all in Mu ,
and hence this path is in F . If z ∈
/ S, let P be a u-v path containing z. If P passes through z before
passing through any vertex in S, then clearly there is a path from u to z in F . Otherwise, P passes
through a vertex y ∈ S before passing through z. In this case, there exists a vertex y 0 ∈ S, such
that y 0 6= y and P passes through y 0 after passing through z. Either y or y 0 , say y 0 , is different from
x. From the above discussion, there is a path P 0 from u to y 0 in F , which when combined with the
subpath of P between y 0 and z yields a path from u to z in F .
Lemma 4.13. |M| ≤ g(k), where g(k) = O(ck k 2k ), for some constant c > 1.
Proof. By Observation 4.5, there can be at most one path in M that contains only internal colors
w.r.t. w in G − w. Therefore, it suffices to upper bound the number of paths in M that contain at
least one external color to w in G − w. Without loss of generality, in the rest of the proof, we shall
assume that M does not include a path that contains only internal colors w.r.t. w in G − w, and
upper bound |M| by g(k); adding 1 to g(k) we obtain an upper bound on |M| with this assumption
lifted. Note that by Observation 4.2, the previous assumption implies that every path in M contains
a color that is external to w in M .
The proof is by induction on k, over every color-connected plane graph G, every triplet of vertices
u, v, w in G, and every minimal set M w.r.t. w of k-valid pairwise color-disjoint u-v paths in G − w.
If k = 1, then any path in M contains exactly one external color w.r.t. w in M . By Lemma 4.10,

24

at most two paths in M contain only external colors. It follows that for k = 1, |M| ≤ 2 ≤ g(1), if
we choose the hidden constant in the O asymptotic notation to be at least 2.
Suppose by the inductive hypothesis that for any 1 ≤ i < k, we have |M| ≤ g(i). We can assume
that M is irreducible; otherwise, we apply the color contraction operation to any edge xy in M to
which the operation is applicable, and replace M with the set of paths Λxy (M), which is pairwise
color-disjoint, contains the same number of paths as M, and is minimal w.r.t. w by Lemma 4.6.
By Lemma 4.11, there are at most 3 paths in M, such that the subgraph of M induced by the
remaining paths of M has a u-v vertex-separator S satisfying |S| ≤ 2k+3. To simplify the argument,
in what follows, we assume that we already removed these 3 paths from M and that M already
has a u-v vertex-separator S satisfying |S| ≤ 2k + 3. We will add 3 to the upper bound of |M| at
the end to account for these removed paths. We can assume, without loss of generality, that S is
minimal (w.r.t. containment). S separates M into two subgraphs Mu and Mv such that u ∈ V (Mu ),
v ∈ V (Mv ), and there is no edge between Mu and Mv . We partition M into the following groups,
where each group excludes the paths satisfying the properties of the groups defined before it: (1)
The set of paths in M that contain a nonempty vertex in S; (2) the set of paths Mku consisting
of each path P in M such that all colors on P appear on vertices in Mu (these colors could still
appear on vertices in Mv as well); (3) the set of paths Mkv consisting of each path P in M such that
all colors on P appear on vertices in Mv ; and (4) the set M<k of remaining paths in M, satisfying
that each path contains a nonempty external vertex to w in M and contains less than k colors from
each of Mu and Mv . Note that by Observation 4.7, each path in M belongs to one of the 4 groups
above.
Since the paths in M are pairwise color-disjoint, no nonempty vertex in S can appear on two
distinct paths from group (1). Therefore, the number of paths in group (1) is at most |S| ≤ 2k + 3.
Observe, that the vertices in S contained in any path in groups (2)-(4) are empty vertices.
To upper bound the number of paths in group (2), for each path P , there is a last vertex xP
(i.e., farthest from u) in P that is in S. Fix a vertex x ∈ S, and let us upper bound the number
of paths P in group (2) for which x = xP . Let Pv be the subpath of P from x to v. Note that
since v is empty and all the vertices in S that are contained in paths in group (2) are empty, and
since M is irreducible, Pv must contain at least one color. Since all colors appearing on P appear
on vertices in Mu , all colors appearing on Pv appear in Mu . By Lemma 4.12, Mu is contained in a
single face f of Mv + x. Since f is a vertex-separator that separates V (Mu ) from V (Pv ) in G, by
Observation 4.1, every color that appears on Pv appears on f . By Lemma 4.10, there are at most
two x-v paths that contain only colors that appear on f . This shows that there are at most two
paths in group (2) for which x is the last vertex in S. Since |S| ≤ 2k + 3, this upper bounds the
number of paths in group (2) by 2(2k + 3) = 4k + 6. By symmetry, the number of paths in group
(3) is upper bounded by 4k + 6.
Finally, we upper bound the number of paths in group (4). Let S = {s2 , . . . , sr−1 }, where
r ≤ 2k + 5, and extend S by adding the two vertices s1 = u and sr = v to form the set A =
{s1 , s2 , . . . , sr }. For every two (distinct) vertices sj , sj 0 ∈ A, j, j 0 ∈ [r], j < j 0 , we define a set of
paths Pjj 0 in G − w whose endpoints are sj and sj 0 as follows. For each path P in group (4),
partition (the edges in) P into subpaths P1 , . . . , Pq satisfying the property that the endpoints of
each Pi , i ∈ [q], are in A, and no internal vertex to Pi is in A. Since each P is a u-v path, clearly,
P can be partitioned as such. For each Pi , i ∈ [q], such that Pi contains a vertex that contains
an external color to w in G − w, let Pi0 (possibly equal to Pi ) be a subpath in G − w between the
endpoints of Pi satisfying that χ(Pi0 ) ⊆ χ(Pi ) and χ(Pi0 ) is minimal w.r.t. containment (i.e., there
does not exist a path Pi00 in G − w between the endpoints of Pi satisfying χ(Pi00 ) ( χ(Pi0 )). Since
P contains a vertex that contains an external color to w in G − w, there exists an i ∈ [q] such that
Pi0 contains a vertex that contains an external color to w in G − w; otherwise, by concatenating (in
25

the right sequence) the Pi ’s that do not contain an external color to w (in G − w), with the Pi0 ’s
(instead of the Pi ’s) of the Pi ’s that contain an external color to w (in G − w), we would obtain a
u-v path P 0 in G − w satisfying χ(P 0 ) ( χ(P ) (since χ(P 0 ) ⊆ χ(P ) and P contains an external color
to w and P 0 does not), thus contradicting the minimality of M. Pick any i ∈ [q] satisfying that Pi0
contains a vertex that contains an external color to w in G − w, associate P with Pi0 , and assign
Pi0 to the set of paths Pjj 0 such that sj and sj 0 are the endpoints of Pi0 . Since each Pi0 contains an
external color that appears on P and the paths in M are pairwise-color disjoint, it follows that the
map that maps each P to its Pi0 is a bijection.
Therefore, to upper bound the number of paths in group (4), it suffices to upper bound the
number of paths assigned to the sets Pjj 0 , where j, j 0 ∈ [r], j < j 0 . Fix a set Pjj 0 . The paths in Pjj 0
have sj , sj 0 as endpoints, and are pairwise color-disjoint. Moreover, each path in Pjj 0 contains a
vertex that contains an external color to w in G − w. It follows from the previous statements that
Pjj 0 satisfies properties (i) and (ii) of Definition 4.4 w.r.t. G and w. Moreover, from the definition
of each path in Pjj 0 , Pjj 0 satisfies property (iii) of Definition 4.4 as well. Finally, observe that each
path Pi0 ∈ Pjj 0 was constructed based on a subpath Pi of a path P in group 4, and satisfying that
Pi has endpoints sj , sj 0 and no internal vertex on Pi is in A. Since P is a u-v path in M and S is
a vertex-separator of M , V (Pi ) is either contained in V (Mu ) ∪ S or in V (Mv ) ∪ S. Since P is in
group (4), P contains at most k − 1 colors from each of Mu and Mv . Since the vertices in S are
empty, we deduce that Pi contains at most k − 1 colors. Since χ(Pi0 ) ⊆ χ(Pi ), Pi0 contains at most
k − 1 colors as well, and hence, every path in Pjj 0 contains at most k − 1 colors. It follows that
Pjj 0 is a minimal set of (k − 1)-valid sj -sj 0 paths in G − w w.r.t. w. By the inductive hypothesis,

we have |Pjj 0 | ≤ g(k − 1). Since the number of sets Pjj 0 is at most 2k+5
, the number of paths in
2
group (4) is O(k 2 ) · g(k − 1).
It follows from the above that |M| ≤ g(k), where g(k) satisfies the recurrence relation g(k) ≤
3 + (2k + 3) + 2(4k + 6) + O(k 2 ) · g(k − 1) = O(k 2 ) · g(k − 1), where 3 accounts for the 3 paths
we removed from M at the beginning of the proof to get a small u-v vertex-separator. Solving the
aforementioned recurrence relation gives g(k) = O(ck k 2k ), where c > 1 is a constant. Adding 1 to
g(k) to account for the single path in M containing only internal colors w.r.t. w in M yields the
same asymptotic upper bound.
Theorem 4.14. Let G be a plane color-connected graph, let u, v, w ∈ V (G), and let P be a set of
2
2
minimal k-valid u-v paths w.r.t. w in G − w. Then |P| ≤ h(k), where h(k) = O(ck k 2k +k ), for
some constant c > 1.
Proof. The proof is by induction on k. If k = 1, then by minimality of P, we have P = M.
2
2
Lemma 4.13 gives an upper bound of O(ck k 2k ) = O(ck k 2k +k ) on |P|.
Assume by the inductive hypothesis that the statement of the lemma is true for 1 ≤ i < k. Let
M be a maximal set of pairwise color-disjoint paths in P. By Lemma 4.13, |M| ≤ g(k) = O(ck k 2k ).
The number of colors contained in vertices of M is at most r ≤ k · g(k). We group the paths in
P into r groups P1 , . . . , Pr , such that all the paths in Pi , i ∈ [r], share the same color ci , where
i ∈ [r], that is distinct from each color cj shared by the paths in Pj , for j 6= i. We upper bound the
number of paths in each Pi , i ∈ [r], to obtain an upper bound on |P|.
Let Gi be the graph obtained by removing color ci from each vertex in G that ci appears on,
and let Pi0 be the set of paths obtained from Pi by removing color ci from each vertex in Pi that ci
appears on. Clearly, every path in Pi0 is a (k − 1)-valid u-v path. Moreover, it is easy to verify that
Pi0 satisfies properties (i)-(iii) in Definition 4.4, and hence, Pi0 is minimal w.r.t. w in Gi − w. By
the inductive hypothesis, we have |Pi0 | ≤ h(k − 1). It follows that the total number of paths in P is
at most h(k), where h(k) satisfies the recurrence relation h(k) ≤ r · h(k − 1) ≤ k · g(k) · h(k − 1).
2
2
Solving the aforementioned recurrence relations yields h(k) = O((k · g(k))k ) = O(ck k 2k +k ).
26

The result of Theorem 4.14 will be employed in the next section in the form presented in the
following corollary:
Corollary 4.15. Let G be a plane color-connected graph, and let w ∈ V (G). Let G0 be a subgraph
of G − w, and let u, v ∈ V (G0 ). Every set P of minimal k-valid u-v paths in G0 w.r.t. w satisfies
2
2
|P| ≤ h(k), where h(k) = O(ck k 2k +k ), for some constant c > 1.
Proof. Contract every connected component of (G−w)−G0 into a single vertex containing the union
of the color-sets of the vertices in the component, and add k + 1 new distinct colors to the resulting
vertex. Denote the resulting graph by G00 . Observe that the resulting graph is color-connected,
and that every k-valid u-v path in G0 w.r.t. w is a k-valid u-v path in G00 w.r.t. w, and vice versa.
Therefore, every set P of minimal k-valid u-v paths in G0 w.r.t. w is also a set of minimal k-valid
u-v paths in G00 w.r.t. w. For any set P of minimal k-valid u-v paths w.r.t. w in G0 , by applying
Theorem 4.14 to P in G00 − w, the corollary follows.

5

The Algorithm

In this section, we present an FPT algorithm for Colored Path-Con, parameterized by both k
and the treewidth of the input graph. As pointed out in Section 4, there can be too many (i.e., more
than FPT-many) subsets of colors that appear in a bag, and hence, that the algorithm may need
to store/remember. To overcome this issue, we extend the notion of a minimal set of k-valid u-v
paths w.r.t. a vertex—from the previous section—to a “representative set” of paths w.r.t. a specific
bag and a specific enumerated configuration for the bag. This allows us to upper bound the size of
the table, in the dynamic programming algorithm, stored at a bag by a function of both k and the
treewidth of the graph.
Let (G, C, χ, s, t, k) be an instance of Colored Path-Con. The algorithm is a dynamic programming algorithm based on a tree decomposition of G. Let (V, T ) be a nice tree decomposition of
G. By Assumption 2.2, we can assume that s and t are nonadjacent empty vertices. We add s and
t to every bag in T , and now we have {s, t} ⊆ Xi , for every bag Xi ∈ T . For a bag Xi , we say that
v ∈ Xi is useful if |χ(v)| ≤ k. Let Ui be the set of all useful vertices in Xi and let Ui = Xi \ Ui . We
denote by Vi the set of vertices in the bags of the subtree of T rooted at Xi . For any two vertices
u, v ∈ Xi , let Giuv = G[(Vi \ Xi ) ∪ {u, v}]. We extend the notion of a minimal set of k-valid u-v
paths w.r.t. a vertex, developed in the previous section, to the set of vertices in a bag of T .
Definition 5.1. A set of k-valid u-v paths Puv in Giuv is minimal w.r.t. Xi if it satisfies the following
properties:
(i) There does not exist two paths P1 , P2 ∈ Puv such that χ(P1 ) ∩ χ(Xi ) = χ(P2 ) ∩ χ(Xi );
(ii) there does not exist two paths P1 , P2 ∈ Puv such that χ(P1 ) ⊆ χ(P2 ); and
(iii) for any P ∈ Puv there does not exist a u-v path P 0 in Giuv such that χ(P 0 ) ( χ(P ).
The following lemma uses the upper bound on the cardinality of a minimal set of k-valid u-v
paths w.r.t. a vertex, derived in Corollary 4.15 in the previous section, to obtain an upper bound
on the cardinality of a minimal set of k-valid u-v paths w.r.t. a bag of T :
Lemma 5.2. Let Xi be bag, u, v ∈ Xi , and Puv a set of k-valid u-v paths in Giuv that is minimal
2
2
w.r.t. Xi . Then the number of paths in Puv is at most h(k)|Xi | , where h(k) = O(ck k 2k +k ), for
some constant c > 1.
27

Proof. Let Xi \ {u, v} = {w1 , . . . , wr }, where r = |Xi | − 2. For each wj ∈ Xi , j ∈ [r], let Pj be a
minimal set of k-valid u-v paths w.r.t. wj in Giuv . Without loss of generality, we can pick Pj such
that there is no k-valid u-v path P in Giuv such that Pj ∪ {P } is minimal. From Corollary 4.15, we
2
2
have |Pj | ≤ h(k) = O(ck k 2k +k ), for some constant c > 1. For each P ∈ Puv , and each j ∈ [r],
define Cj = χ(P ) ∩ χ(wj ). Define the signature of P (w.r.t. the colors of w1 , . . . , wr ) to be the tuple
(C1 , . . . , Cr ). Observe that no two (distinct) paths P1 , P2 ∈ Puv have the same signature; otherwise,
since u and v appear on both P1 , P2 , χ(P1 ) ∩ χ(Xi ) = χ(P2 ) ∩ χ(Xi ), which contradicts condition
(i) of the minimality of Puv . For each P ∈ Puv , and each j ∈ [r], there is a path P 0 ∈ Pj such that
χ(P 0 ) ∩ χ(wj ) = Cj . If this were not true, then P would have been added to Pj for the following
reasons. Clearly, P does not contradict conditions (i) and (iii) of the minimality of Pj . It cannot
contradict (ii) either, because otherwise, and since P does not contradict (i), there would be a path
P 00 ∈ Pj such that χ(P 00 ) ( χ(P ), contradicting
the minimality of Puv . It follows that the number
Q
of signatures of paths in Puv is at most rj=1 |Pj | ≤ h(k)|Xi | . Since no two distinct paths in Puv
have the same signature, it follows that |Puv | ≤ h(k)|Xi | .
Definition 5.3. Let Xi be a bag in T . A pattern π for Xi is a sequence
(v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t), where σi ∈ {0, 1} and vi ∈ Ui . For a bag Xi , and a pattern
(v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) for Xi , we say that a sequence of paths S = (P1 , . . . , Pr−1 )
conforms to (Xi , π) if:
• For each j ∈ [r − 1], σj = 1 implies that Pj is an induced path from vj to vj+1 whose internal
vertices are contained in Vi \ Xi and Pj is empty otherwise; and
S
• |χ(S)| = | j∈[r−1] χ(Pj )| ≤ k.
Definition 5.4. Let Xi be a bag, π a pattern for Xi , and S1 , S2 two sequences of paths that conform
to (Xi , π). We write S1 i S2 if |χ(S1 ) ∪ (χ(S2 ) ∩ χ(Xi ))| ≤ |χ(S2 )|.
We note that at a certain point during the dynamic programming algorithm, we will have to
deal for a short while with sequences of walks instead of sequences of paths (until we refine them),
but the definition of a sequence of paths conforming to a bag and a pattern, and the relation ,
extend seamlessly to sequences of walks.
Lemma 5.5. Let Xi be a bag and π a pattern for Xi . The relation i is a transitive relation on
the set of all sequences of paths that conform to (Xi , π).
Proof. Let S1 , S2 , S3 be three sequences that conform to (Xi , π). Suppose that S1 i S2 and
S2 i S3 . We need to show that S1 i S3 . To simplify the notation in the proof, let A =
χ(S1 ), B = χ(S2 ), C = χ(S3 ), X = Xi . Since S1 i S2 , we have
|A ∪ B ∩ X| ≤ |B|
|A| + |B ∩ X| − |A ∩ B ∩ X| ≤ |B|,

(1)

and since S2 i S3 we have:
|B ∪ C ∩ X| ≤ |C|
|B| + |C ∩ X| − |B ∩ C ∩ X| ≤ |C|.

28

(2)

From Inequalities (1) and (2) we get:
≤

|C|

|A| + |C ∩ X| + |B ∩ X| − (|A ∩ B ∩ X| + |B ∩ C ∩ X| − |A ∩ B ∩ C ∩ X| + |A ∩ B ∩ C ∩ X|) ≤

|A| + |C ∩ X| + |B ∩ X| − |A ∩ B ∩ X| − |B ∩ C ∩ X|

|C|

|A| + |C ∩ X| + |B ∩ X| − (|A ∩ B ∩ X ∪ B ∩ C ∩ X| + |A ∩ B ∩ C ∩ X|) ≤

|C|

|A| + |C ∩ X| + |B ∩ X| − (|(A ∪ C) ∩ (B ∩ X)| + |A ∩ B ∩ C ∩ X|) ≤

|C|

|A| + |C ∩ X| + |B ∩ X| − (|B ∩ X| + |A ∩ B ∩ C ∩ X|) ≤

|C|

|A| + |C ∩ X| − |A ∩ B ∩ C ∩ X|) ≤

|C|

|A| + |C ∩ X| − |A ∩ C ∩ X|) ≤

|C|.

The last inequality proves that S1 i S3 .
Using the relation i on the set of sequences that conform to (Xi , π), we are now ready to define
the key notion of representative sets that makes the dynamic programming approach work:
Definition 5.6. Let Xi be a bag and π = (v1 , σ1 , v2 . . . , σr−1 , vr ) a pattern for Xi . A set Rπ of
sequences that conform to (Xi , π) is a representative set for (Xi , π) if:
(i) For every sequence S1 ∈ Rπ , and for every sequence S2 6= S1 that conforms to (Xi , π), if
S1 i S2 then S2 ∈
/ Rπ ;
(ii) for every sequence S ∈ Rπ , and for every path P ∈ S between vj and vj+1 , j ∈ [r − 1], there
does not exist a vj -vj+1 path P 0 in Givj vj+1 such that χ(P 0 ) ( χ(P ); and
(iii) for every sequence S ∈
/ Rπ that conforms to (Xi , π) and satisfies that no two paths in S share
a vertex that is not in Xi , there is a sequence W ∈ Rπ such that W i S.
Observation 5.7. Let Xi and Xj be two bags such that Xi ⊆ Xj , let π be a pattern for both Xi
and Xj , and let S, S 0 be two sequences that conform to both (Xi , π) and (Xj , π). If S j S 0 then
S i S 0 .
Proof. Since Xi ⊆ Xj , we have |χ(S) ∪ χ(S 0 ) ∩ χ(Xi )| ≤ |χ(S) ∪ χ(S 0 ) ∩ χ(Xj )|.
Lemma 5.8. Let Xi be a bag, π a pattern for Xi , and S1 , S10 , S2 , S20 , S, S 0 sequences that conform to
(Xi , π) and that satisfy the following: S10 i S1 , S20 i S2 , χ(S1 ) ∪ χ(S2 ) = χ(S), χ(S10 ) ∪ χ(S20 ) =
χ(S 0 ), and χ(S1 ) ∩ χ(S2 ) ⊆ χ(Xi ). Then S 0 i S.
Proof. Let A = χ(S1 ), B = χ(S2 ), C = χ(S), A0 = χ(S10 ), B 0 = χ(S20 ), C 0 = χ(S 0 ), and X = χ(Xi ).
Since S10 i S1 we have:
|A0 ∪ A ∩ X| ≤ |A|
|A0 | + |A ∩ X| − |A0 ∩ A ∩ X| ≤ |A|.

(3)

Since S20 i S2 we have:
|B 0 ∪ B ∩ X| ≤ |B|
|B 0 | + |B ∩ X| − |B 0 ∩ B ∩ X| ≤ |B|.
29

(4)

Adding Inequality (3) to (4) and subtracting |A ∩ B| from each side of the resulting inequality,
we obtain:
|A0 | + |B 0 | + |A ∩ X| + |B ∩ X| − |A0 ∩ A ∩ X| − |B 0 ∩ B ∩ X| − |A ∩ B| ≤ |A ∪ B|.

(5)

Replacing in the last Inequality (5) |A0 | + |B 0 | by |A0 ∪ B 0 | + |A0 ∩ B 0 |, and |A ∩ X| + |B ∩ X|
by |(A ∪ B) ∩ X| + |A ∩ B ∩ X|, observing that A ∩ B ∩ X = A ∩ B (because A ∩ B ⊆ X), and
simplifying, we get:
|A0 ∪ B 0 | + |(A ∪ B) ∩ X| + |A0 ∩ B 0 | − |A0 ∩ A ∩ X| − |B 0 ∩ B ∩ X| ≤ |A ∪ B|
0

0

|(A ∪ B ) ∪ (A ∪ B) ∩ X| + |(A0 ∪ B 0 ) ∩ (A ∪ B) ∩ X| + |A0 ∩ B 0 | − |A0 ∩ A ∩ X| − |B 0 ∩ B ∩ X| ≤ |A ∪ B|.

Replacing −|A0 ∩ A ∩ X| − |B 0 ∩ B ∩ X| in the last inequality with −(|A0 ∩ A ∪ B 0 ∩ B) ∩ X| +
∩ A ∩ B 0 ∩ B ∩ X|) = −(|A0 ∩ A ∪ B 0 ∩ B) ∩ X| + |A0 ∩ A ∩ B 0 ∩ B|) (because A ∩ B ⊆ X), and
observing that |(A0 ∩ A ∪ B 0 ∩ B) ∩ X| ≤ |(A0 ∪ B 0 ) ∩ (A ∪ B) ∩ X|, and |A0 ∩ A ∩ B 0 ∩ B| ≤ |A0 ∩ B 0 |,
we conclude that:
|A0

|(A0 ∪ B 0 ) ∪ (A ∪ B) ∩ X| ≤ |A ∪ B|.

(6)

Inequality (6) establishes that S 0 i S.
Lemma 5.9. Let Xi be bag, π a pattern for Xi , and Rπ be a representative set for (Xi , π). Then
2
2
2
the number of sequences in Rπ is at most h(k)|Xi | , where h(k) = O(ck k 2k +k ), for some constant
c > 1.
Proof. Let π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) and let vj and vj+1 be two consecutive vertices
in π such that σj = 1. For each j ∈ [r−1] such that σj = 1, let Pj be a minimal set of k-valid vj -vj+1
paths w.r.t. Xi . Without loss of generality, we can pick Pj such that there is no k-valid u-v path P
in Givj vj+1 such that Pj ∪ {P } is minimal w.r.t. Xi . From Lemma 5.2, it follows that |Pj | ≤ h(k)|Xi | ,
2

2

where h(k) = O(ck k 2k +k ), for some constant c > 1. For a sequence S = (P1 , . . . , Pr−1 ) in Rπ , we
define the signature of S (w.r.t. Xi ) to be the tuple (χ(P1 ) ∩ χ(Xi ), . . . , χ(Pr−1 ) ∩ χ(Xi )). Observe
that if S1 and S2 have the same signature w.r.t. Xi , then χ(S1 ) ∪ (χ(S2 ) ∩ χ(Xi )) = χ(S1 ) and
χ(S2 ) ∪ (χ(S1 ) ∩ χ(Xi )) = χ(S2 ); hence, either S1 i S2 or S2 i S1 . It follows from property
(i) of representative sets that no two sequences in Rπ have the same signature w.r.t. Xi . Now let
S = (P1 , . . . , Pr−1 ) be a sequence in Rπ with a signature (C1 , . . . , Cr−1 ). Note that if Cj 6= ∅,
then Pj is not the empty path, and hence σj = 1. We show that for each j ∈ [r − 1] such that
Cj 6= ∅, there is a path P ∈ Pj such that χ(P ) ∩ χ(Xi ) = Cj . Suppose, for a contradiction, that
this is not the case. Then for some j ∈ [r − 1] such that Cj 6= ∅, there is no path P ∈ Pj such
that χ(P ) ∩ χ(Xi ) = Cj . Clearly, Pj ∈
/ Pj , and therefore, by our choice of Pj , the set Pj ∪ {Pj }
is not a minimal set w.r.t. Xi . By assumption, Pj ∪ {Pj } does not contradict property (i) in the
definition of minimal set of paths w.r.t. Xi . Moreover, since S ∈ Rπ , it follows from property (ii)
of representative sets that Pj , and hence Pj ∪ {Pj }, satisfies property (iii) of minimal set of paths
w.r.t. Xi . Therefore, Pj ∪ {Pj } has to contradict property (ii) in the definition of minimal set of
paths w.r.t. Xi , and there are two paths Q1 , Q2 ∈ Pj ∪ {Pj } such that χ(Q1 ) ⊆ χ(Q2 ). However,
if χ(Q1 ) = χ(Q2 ), then Q1 and Q2 contradict property (i) of a minimal set of paths w.r.t. Xi , and
if χ(Q1 ) ( χ(Q2 ), then Q2 contradicts property (iii), and we already established that Pj ∪ {Pj }
satisfies properties (i) and (iii). Therefore, Pj ∪ {Pj } is a set of minimal paths w.r.t. Xi , which is
a contradiction. We conclude that, for each j ∈ [r − 1] such that Cj 6= ∅, there is a path P ∈ Pj
30

such that χ(P ) ∩ χ(Xi ) = Cj . It follows that the number of signatures of paths in Puv is at most
Qr−1
|Xi |2 . Since no two distinct sequences in R have the same signature, it follows
π
j=1 |Pj | ≤ h(k)
2

that |Rπ | ≤ h(k)|Xi | .
For each bag Xi , we maintain a table Γi that contains, for each pattern for Xi , a representative
set of sequences Rπ for (Xi , π). For two vertices u, v ∈ Xi and two u-v paths P, P 0 in Giuv , we say
0 )
that P 0 refines P if χ(P 0 ) ⊆ χ(P ). For two sequences S = (P1 , . . . , Pr−1 ) and S 0 = (P10 , . . . , Pr−1
that conform to (Xi , π), we say that S 0 refines S if each path Pj0 refines Pj , for j ∈ [r − 1].
Lemma 5.10. Let Xi be a bag, π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) a pattern for Xi , and
W = (W1 , . . . , Wr−1 ) a sequence of walks, where each Wj is a walk between vertices vj and vj+1 in
Givj vj+1 satisfying χ(Wj ) ≤ k. Then in time O∗ (2k ) we can compute a sequence S = (P1 , . . . , Pr−1 )
of induced paths, where each Pj is an induced path between vertices vj and vj+1 in Givj vj+1 such that
χ(Pj ) ⊆ χ(Wj ), for j ∈ [r − 1], and such that S satisfies property (ii) of representative sets.
Proof. For each walk Wj , j ∈ [r − 1], we do the following. For each subset C 0 ⊆ χ(W ) considered
in a nondecreasing order of cardinality, we form the subgraph G0 from Givj vj+1 by removing every
vertex x in Givj vj+1 that does not satisfy χ(x) ⊆ C 0 . We then check if there is a vj -vj+1 induced
path in G0 , and set Pj to this path if it exists. It is clear that the path Pj satisfies χ(Pj ) ⊆ χ(Wj )
and that the sequence S 0 = (P1 , . . . , Pr−1 ) conforms to π w.r.t. Xi and satisfies property (ii) of
representative sets. Since each Wj satisfies χ(Wj ) ≤ k, we can enumerate all subsets of χ(Wj ) in
time O∗ (2k ). Since checking if there is an induced vj -vj+1 path in G0 takes polynomial time, it
follows that computing Pj from Wj takes O∗ (2k ), and so does the computation of S.
For a bag Xi , pattern π for Xi , and a set of sequences R that conform to (Xi , π), we define the
procedure Refine() that takes the set R and outputs a set R0 of sequences that conform to (Xi , π),
and does not violate properties (i) and (ii). For each sequence S in R, we compute a sequence
S 0 that refines S and satisfies property (ii), and replace S with S 0 in R. Afterwards, we initialize
R0 = ∅, and order the sequences in R arbitrarily. We iterate through the sequences in R in order,
and add a sequence Sp to R0 if there is no sequence S already in R0 such that S i Sp , and there
is no sequence Sq ∈ R, q > p (i.e., Sq comes after Sp in the order), such that Sq  Sp .
Lemma 5.11. Let Xi be a bag, π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) a pattern for Xi , and W =
(W1 , . . . , Wr−1 ) a sequence of walks, where each Wj is a walk between vertices vj and vj+1 in Givj vj+1
satisfying χ(Wj ) ≤ k. The procedure Refine() on input W produces a set of sequences R0 that
conforms to (Xi , π) satisfying properties (i) and (ii), and such that for each sequence S ∈ W, there
is a sequence S 0 ∈ R0 satisfying S 0 i S. Moreover, the procedure runs in time O∗ (2k |W| + |W|2 ).
Proof. By Lemma 5.10, refining a sequence in W takes O∗ (2k ) time, and hence, refining all sequences
in W takes O∗ (2k |W|) time. After refining W, we initialize R0 to the empty set, and iterate through
the sequences in W, adding a sequence Sp ∈ W to R0 if there is no sequence S already in R0 such
that S i Sp ; clearly this takes O∗ (|W|2 ) time, and the lemma follows.
If a bag Xi is a leaf in T , then Xi = Vi = {s, t}, and there are only two patterns (s, 0, t) and
(s, 1, t) for Xi . Clearly, the only sequence that conforms to (s, 0, t) is the sequence (()) containing
exactly one empty path. Moreover, there is no edge st ∈ E(G). Therefore, there is no sequence
that conforms to (s, 1, t), and the following claim holds:
Claim 2. If a bag Xi is a leaf in T , then Γi = {((s, 0, t), {(())}), ((s, 1, t), ∅)} contains, for each
pattern for Xi , a representative set for (Xi , π).
31

We describe next how to update the table stored at a bag Xi , based on the tables stored at its
children in T . We distinguish the following cases based on the type of bag Xi .
Case 1. Xi is an introduce node with child Xj . Let Xi = Xj ∪ {v}.
Clearly, for every pattern π for Xi that does not contain v, we can set Γi [π] = Γj [π]. Γj [π] is a
representative set for (Xi , π) for the following reasons: (i) follows because every color in χ(Xi )\χ(Xj )
does not appear in Vj , since Xi is a vertex-separator in G separating v and Vj and colors are
connected. Hence, if two sequences in Γj [π] that conform to (Xi , π) contradict (i), they contradict
(i) w.r.t. (Xj , π) as well, but Γj [π] is a representative set for (Xj , π). For properties (ii) and (iii),
it is easy to observe that v does not appear on any path between two vertices in π having internal
vertices in Vi \ Xi , and hence, these properties are inherited from the child node Xj .
Now let π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) be a pattern such that vq = v, q ∈ {2, . . . , r−1},
and let π 0 = (v1 , σ1 , . . . vq−1 , 0, vq+1 , σq+1 , . . . , σr−1 , vr ). Note that since Xj is a separator between v
and Vj , the only possibility for a path from v to a different vertex in Xi to have all internal vertices
in Vi \ Xi is if it is a direct edge. Therefore, if σq−1 = 1 (resp. σq = 1) then vq−1 v (resp. vq v) is an
edge in G. Otherwise, there is no sequence that conforms to (Xi , π).
0 ) ∈ Γ [π 0 ], we replace
We obtain Γi [π] from Γj [π 0 ] as follows. For every S 0 = (P10 , P20 , . . . , Pr−2
j
the empty path corresponding to 0 between vq−1 and vq+1 in π 0 by two paths Pq−1 , Pq such that
Pq−1 = () (resp. Pq = ()) if σq−1 = 0 (resp. σq = 0) and Pq−1 = (vq−1 , v) (resp. Pq−1 = (v, vq ))
0
0 ,P
0
otherwise and we obtain S = (P10 , . . . , Pq−2
q−1 , Pq , Pq , . . . , Pr−2 ). Denote by Rπ the set of all
formed sequences S. Finally, we set Γi [π] = Refine(Rπ ). We claim that Γi [π] is a representative
set for (Xi , π).
Claim 3. If Xi is an introduce node with child Xj , and Γj contains for each pattern π 0 for Xj a
representative set for (Xj , π 0 ), then Γi [π] defined above is a representative set for (Xi , π).
Proof. It is clear that from the application of Refine(), Γi [π] does not contradict properties (i)-(ii)
of the definition of representative sets. Assume now that there exists a sequence S ∈
/ Γi [π] that
0
conforms to (Xi , π) such that S violates property (iii). We define the sequence S that conforms to
π 0 , and is the same as S on all paths that π and π 0 share. Since no two paths in S share a vertex
that is not in Xi (since S violates (iii)), and all paths in S 0 are also in S, it follows that no two paths
in S 0 share a vertex that is not in Xj . Since Γj [π 0 ] is a representative set for (Xj , π 0 ), it follows
that there exists S10 ∈ Γj [π 0 ] such that S10 j S 0 . Let S1 be the sequence obtained from S10 and
conforming to (Xi , π). Then S1 ∈ Rπ , and hence by Lemma 5.11, there is a sequence S2 ∈ Γi [π]
such that S2 i S1 . Since either both S1 and S contain v or none of them does, we have S1 i S.
By transitivity of i (Lemma 5.5), it follows that S2 i S. This contradicts the assumption that S
violates property (iii).
Case 2. Xi is a forget node with child Xj . Let Xi = Xj \ {v}.
Let π = (s = v1 , σ1 , . . . , σr−1 , vr = t) be a pattern for the vertices in Xi . For q ∈ [r − 1], such
0
that σq = 1, we define π q = (s = v10 , σ10 , . . . , σr0 , vr+1
= t) to be the pattern obtained from π by
0
0
inserting v between vq and vq+1 and setting σq = σq+1 = 1. More precisely, we set vp0 = vp and
0
0
σp0 = σp for 1 ≤ p ≤ q, vq+1
= v and σq+1
= 1, and finally vp0 = vp−1 and σp0 = σp−1 for q +2 ≤ p ≤ r.
We define Rπ as follows:
Rπ = Γj [π] ∪ {S = (P1 , . . . , Pq−1 , Pq ◦ Pq+1 , Pq+2 , . . . , Pr ) | (P1 , . . . , Pr ) ∈ Γj [π q ], q ∈ [r − 1] ∧ σq = 1}.

Finally, we set Γi [π] = Refine(Rπ ) and we claim that Γi [π] is a representative set for (Xi , π).
32

Claim 4. If Xi is a forget node with child Xj , and Γj contains for each pattern π 0 for Xj a
representative set for (Xj , π 0 ), then Γi [π] defined above is a representative set for (Xi , π).
Proof. It is straightforward to see that Γi [π] satisfies properties (i) and (ii) due to the way procedure
Refine() works. Assume for a contradiction that there exists a sequence S that violates property
(iii). We distinguish two cases.
First, suppose that no path in S contains the vertex v. Then this path conforms to the pattern π
in Xj . Since no two paths in S share a vertex that is not in Xi , and since Γj [π] is a representative set,
there exists S1 ∈ Γj [π] such that S1 j S. Then S1 ∈ Rπ , and hence by Lemma 5.11, Γi [π] contains
a sequence S2 such that S2 i S1 . Since S1 j S and Xi ( Xj , it follows from Observation 5.7 that
S1 i S. By transitivity of i , it follows that S2 i S, which is a contradiction to the assumption
that S violates property (iii).
Second, suppose that there is a path Pq in S that contains v on a path between vq and vq+1 . We
form a sequence S 0 from S by keeping every path P 6= Pq in S, and replacing Pq in the sequence
0
by the two subpaths of Pq , Pq0 = (vq , . . . , v) and Pq+1
= (v, . . . , vq+1 ). The sequence S 0 conforms to
q
(Xj , π ), and since no two paths in S share a vertex that is not in Xi , no two paths in S 0 share a
vertex that is not in Xj . Since Γj [π q ] is a representative set for (Xj , π q ), it follows that there exists
a sequence S10 ∈ Γj [π q ] such that S10 j S 0 . Let S1 be the sequence conforming to (Xi , π) obtained
from S10 by applying the operation ◦ to the two paths in S10 that share v. Then S1 ∈ Rπ . Therefore,
by Lemma 5.11, Γi [π] contains a sequence S2 such that S2 i S1 . Since S10 j S 0 , χ(S 0 ) = χ(S),
χ(S10 ) = χ(S1 ), and Xi ( Xj , it follows that S1 i S. By transitivity of i , it follows that S2 i S,
which is a contradiction to the assumption that S violates property (iii).
Case 3. Xi is a join node with children Xj , Xj 0 .
Let π = (s = v1 , σ1 , . . . , σr−1 , vr = t) be a pattern for Xi . Initialize Rπ = ∅. For every two
patterns π1 = (s = v1 , τ1 , . . . , τr−1 , vr = t) and π2 = (s = v1 , µ1 , . . . , µr−1 , vr = t) such that
σq = τq + µq , and for every two sequences S1 = (P11 , . . . , P1r−1 ) ∈ Γj [π1 ] and S2 = (P21 , . . . , P2r−1 ) ∈
Γj 0 [π2 ], we add the sequence S = (P1 , . . . , Pr−1 ) to Rπ , where Pq = P1q if P2q is the empty path,
otherwise, Pq = P2q , for q ∈ [r − 1]. We set Γi [π] = Refine(Rπ ), and we claim that Γi [π] is a
representative set for (Xi , π).
Claim 5. If Xi is a join node with children Xj , Xj 0 , and Γj (resp. Γj 0 ) contains for each pattern
π 0 for Xj = Xj 0 = Xi a representative set for (Xj , π 0 ) (resp. (π 0 , Xj 0 )), then Γi [π] defined above is
a representative set for (Xi , π).
Proof. Clearly Γi [π] satisfies properties (i) and (ii) due to the application of the procedure Refine().
To argue that Γi [π] satisfies property (iii), suppose not, and let S = (P1 , . . . , Pr−1 ) be a sequence
that violates property (iii). Notice that every path Pq , q ∈ [r − 1], is either an edge between two
vertices in Xi , or a path between two vertices in Xi such that its internal vertices are either all in
Vj \Xi or in Vj 0 \Xi ; this is true because Xi is a vertex-separator separating Vj \Xi from Vj 0 \Xi in G.
Define the two sequences S1 = (P11 , . . . , P1r−1 ) and S2 = (P21 , . . . , P2r−1 ) as follows. For q ∈ [r − 1],
if Pq is empty then set both P1q and P2q to the empty path; if Pq is an edge then set P1q = Pq and
P2q to the empty path. Otherwise, Pq is either a path in G[Vj ] or in G[Vj 0 ]; in the former case set
P1q = Pq and P2q to the empty path, and in the latter case set P2q = Pq and P1q to the empty path.
Since no two paths in S share a vertex that is not in Xi , and Xi = Xj = Xj 0 , no two paths in S1
(resp. S2 ) share a vertex that is not in Xj (resp. Xj 0 ). Let π1 = (s = v1 , τ1 , . . . , τr−1 , vr = t) and
π2 = (s = v1 , µ1 , . . . , µr−1 , vr = t) be the two patterns that S1 and S2 conform to, respectively, and
observe that, for every q ∈ [r − 1], we have σq = τq + µq . Since Γj [π1 ] and Γj 0 [π2 ] are representative
33

0 ) in Γ [π ] and S 0 = (Z 0 , . . . , Z 0
sets, it follows that there exist S10 = (Y10 , . . . , Yr−1
j 1
2
1
r−1 ) in Γj 0 [π2 ] such
0
0
0
0
0
0
0
0
that S1 j S1 and S2 j 0 S2 . Let S = (P1 , . . . , Pr−1 ), where Pq = Yq if Zq is the empty path,
otherwise, Pq = Zq0 , for q ∈ [r − 1]. The sequence S 0 conforms to π and is in Rπ . By Lemma 5.11,
Γi [π] contains a sequence S 00 such that S 00 i S 0 . From Observation 5.7, since Xi = Xj = Xj 0 , from
S10 j S1 and S20 j 0 S2 it follows that S10 i S1 and S20 i S2 . Since χ(S1 ) ∪ χ(S2 ) = χ(S) and
χ(S10 ) ∪ χ(S20 ) = χ(S 0 ), and since χ(S1 ) ∩ χ(S2 ) ⊆ χ(Xi ), by Lemma 5.8, it follows that S 0 i S.
Since S 00 i S 0 , by transitivity of i , it follows that S 00 i S, which concludes the proof.

We can now conclude with the following theorem:
Theorem 5.12. There is an algorithm that on input (G, C, χ, s, t, k) of Colored Path-Con,
2
either outputs a k-valid s-t path in G or decides that no such path exists, in time O? (f (k)6ω ),
2
2
where ω is the treewidth of G and f (k) = O(ck k 2k +k ), for some constant c > 1. Therefore,
Colored Path-Con parameterized by both k and the treewidth of the input graph is in FPT.
Proof. First, in time O(|V (G)|4 ), we can compute a branch decomposition of G, and hence a tree
decomposition, of width at most 3ω/2, where ω is the treewidth of G [21, 28, 29]. From this tree
decomposition, in polynomial time we can compute a nice tree decomposition (V, T ) of G whose
width is at most 3ω/2 and satisfying |V| = O(|V (G)|) [24]. The algorithm starts by removing the
colors of s and t from G, and decrements k by |χ(s)∪χ(t)| (see Assumption 2.2). Afterwards, if k < 0,
the algorithm concludes that there is no k-valid s-t path in G. If st ∈ E(G) and k ≥ 0, the algorithm
outputs the path (s, t). Now we know that s and t are not adjacent, and that χ(s) = χ(t) = ∅. The
algorithm then adds s and t to every bag in T , and executes the dynamic programming algorithm
based on (V, T ), described in this section, to compute a table Γi that contains, for each bag Xi in
T and each pattern π for Xi , a representative set Rπ for (Xi , π).
From Claims 2, 3, 4, 5, it follows, by induction on the height of the tree-decomposition (V, T )
(the base case corresponds to the leaves), that the root node Xr contains a representative set Γr [π]
for the sequence π = (s, 1, t). If Γr [π] is empty, the algorithm concludes that there is no k-valid
s-t path in G. Otherwise, noting that there is only one sequence S in the representative set Γr [π]
since Xr = {s, t} and s and t are empty, the algorithm outputs the k-valid s-t path P formed by S.
The correctness follows from the following argument, which shows that if there is a k-valid s-t path
in G, then the algorithm outputs such a path. Suppose that P 0 is a k-valid induced s-t path such
that there does not exist an s-t path P 00 in G satisfying χ(P 00 ) ( χ(P 0 ), and let S 0 = (P 0 ). Since
Grst = G, it follows that S 0 conforms to (Xr , π). Since S 0 contains exactly one path that is induced,
no two paths in S 0 share a vertex. Therefore, by property (iii) of representative sets, there exists
a sequence S in Γr [π] satisfying S r S 0 . Noting that a sequence in Γr [π] must consist of a single
k-valid s-t path, it follows that the algorithm correctly outputs such a path.
Next, we analyze the running time of the algorithm. We observe that among the three types
of bags in T , the worst running time is for a join bag. Therefore, it suffices to upper bound the
running time for a join bag, and since |V| = O(n), the upper bound on the overall running time
would follow.
Consider a join bag Xi with children Xj , Xj 0 . Let ω 0 be the width of T plus 1, which serves as an
upper bound on the bag size in T , and note that ω 0 ≤ 3ω/2 + 3, where the (additional) plus 2 is to
account for the vertices s and t that were added to each bag. The algorithm starts by enumerating
0
0
each pattern π for Xi . The number of such patterns is at most 2ω ·ω 0 ·ω 0 ! = O∗ (2ω ·ω 0 !), where ω 0 ·ω 0 !
0
is an upper bound on the number of ordered selections of a subset of vertices from the bag, and 2ω is
an upper bound on the number of combinations for the σi ’s in the selected pattern. Fix a pattern π
for Xi . To compute Γi [π], the algorithm enumerates all ways of partitioning π into pairs of patterns
0
π1 , π2 for the children bags; there are 2ω ways of partitioning π into such pairs, because for each
34

σi = 1 in π, the path between vi and vi+1 is either reflected in π1 or in π2 . For a fixed pair π1 , π2 ,
the algorithm iterates through all pairs of sequences in the two tables Γj [π1 ] and Γj 0 [π2 ]. Since
02
each table contains a representative set, by Lemma 5.9, the size of each table is O(h1 (k)ω ), where
2
2
h1 (k) = O(ck1 k 2k +k ), for some constant c1 > 1, and hence iterating over all pairs of sequences in
02
the two tables can be done in O(h1 (k)2ω ) time. From the above, it follows that the set Rπ can be
0
02
02
2
2
computed in time 2ω · O(h1 (k)2ω ) = O(h2 (k)2ω ), where h2 (k) = O(ck2 k 2k +k ), for some constant
c2 > 1, which is also an upper bound on the size of Rπ . By Lemma 5.11, applying Refine()
02
02
02
2
2
to Rπ takes time O∗ (2k h2 (k)2ω + h2 (k)4ω ) = O∗ (h3 (k)4ω ), where h3 (k) = O(ck3 k 2k +k ), for
some constant c3 > 1. It follows from all the above that the running time taken by the algorithm to
02
0
02
2
2
compute Γi is O∗ (h3 (k)4ω ·2ω ·ω 0 !) = O∗ (h4 (k)4ω ), where h4 (k) = O(ck4 k 2k +k ), for some constant
2
2
2
c4 > 1, and hence the running time of the algorithm is O? (f (k)6ω ), where f (k) = O(ck k 2k +k ),
for some constant c > 1.

6

Extensions and Applications

In this section, we extend the FPT results for Colored Path-Con w.r.t. the combined parameters
k and ω—the treewidth of the input graph, to show that Colored Path-Con parameterized by
both k and the length ` of the sought path is FPT. We also show some applications of these FPT
results. We formally define the problem Bounded-length Colored Path-Con:
Bounded-length Colored Path-Con
Given: A planar graph G; a set of colors C; χ : V −→ 2C ; two designated vertices s, t ∈ V (G);
and k, ` ∈ N
Question: Does there exist a k-valid s-t path of length at most ` in G?
We first start by showing that if we parameterize only by one of `, k then the problem is W[1]hard.
Theorem 6.1. Bounded-length Colored Path-Con is W[1]-hard parameterized by k.
Proof. We reduce from the W[1]-hard problem Clique. The reduction is similar to that in the
proof of Theorem 3.1. Let (G, k) be an instance of Clique, where V (G) = {v1 , . . . , vn } and
E(G) = {e1 , . . . , em }. We assume that the edges in E(G) are incident to at least k + 3 different
vertices. This assumption is safe because Clique is FPT for instances where the edges in E(G)
are incident to at most k + 2 different vertices. Similarly to the proof of Theorem 3.1, we start
by describing the instance I of Connected Obstacle Removal whose associated graph is the
desired instance of Bounded-length Colored
Path-Con.
Sm
1
The regions of I are O∪{Z0 , . . . , Zm }∪ i=1 {Oi , Oi2 , Oi3 }, depicted in Figure 9. The obstacles of I
are defined as follows. For each vertex vj ∈ V (G), the obstacle Vj corresponding to vj is the polygon
3
whose boundary is the boundary of the region formed by the union of O, and
S each O3 i such that vj
is incident to ei . More formally, the obstacle corresponding to vj is ∂(O ∪ vj ∈ei Oi ). Besides the
S
obstacles corresponding to the vertices of G, there are two auxiliary obstacles A1 = ∂(O ∪ i∈[m] Oi1 )
S
and A2 = ∂(O ∪ i∈[m] Oi2 ). Finally, we place s in Z0 , t in Zm , and ask whether there is a path

from s to t that intersects at most k + 2 obstacles and visits at most 3m − k2 + 1 regions (including
Z0 and Zm ).
Suppose that H is a complete subgraph of G with exactly k vertices. We define an s-t path P
as follows. P starts at s in Z0 . If for i ∈ [m], P enters Zi−1 and ei ∈ E(H), then P goes to Zi
through Oi3 ; otherwise, P goes to Zi through Oi1 and Oi2 . Since P does not enter the region O, and
enters region Oi3 if and only if edge ei is part of the clique H, P intersects an obstacle Vj if and only
35

if vj ∈ V (H). Hence, together with A1 and A2 , P intersects at most k + 2 obstacles. Moreover, P

visits regions Z0 , . . . , Zm , regions Oi3 for ei ∈ E(H) ( k2 times), and regions Oi1 , Oi2 for ei ∈
/ E(H)


k
k
(m − 2 times). Therefore, P visits exactly 3m − 2 + 1 regions.

Conversely, suppose that there is an s-t path P that visits at most 3m − k2 + 1 regions and
intersects at most k + 2 obstacles. It is easy to see that P does not visit region O. Furthermore, by
our assumption, the edges of G are incident to at least k + 3 vertices, and hence P cannot intersect
all the Oi3 ’s, for i ∈ [m]. Therefore, P visits Oi1 and Oi2 for some i ∈ [m], and hence intersects
A1

and A2 . Furthermore, since P visits at most 3m − k2 + 1 regions, P visits at least k2 different
Oi3 ’s. Since each Oi3 contains a pair of two obstacles Vj1 , Vj2 such that ei = vj1 vj2 , there are no
multiple edges in G (and hence, no two Oi3 ’s have the same set of obstacles), and P intersects at
most k obstacles that corresponds to vertices of G, it follows that P intersects exactly k obstacles
that correspond to vertices, and visits exactly k2 different Oi3 ’s. Moreover, for each pair of obstacles
Vj1 , Vj2 that P intersect, there has to be an Oi3 that contains exactly these two obstacles. This
means that there is an edge vj1 vj2 in G for each such pair, and hence a k-clique in G.

O13
O

Oi3

3
Om

s
Z0

t
O11

O12

Z1

Zi−1 Oi1

Oi2

Zi

1
2 Z
Zm−1 Om
Om
m

Figure 9: Illustration for the proof of Theorem 6.1.
Theorem 6.2. Bounded-length Colored Path-Con is W[1]-hard parameterized only by `.
Proof. The proof is similar to the proof of Lemma 3.5. We will describe the reduction from MultiColored Clique and point out the differences.
Let (G, k) be an instance of Multi-Colored Clique, where V (G) is partitioned into the color
classes C1 , . . . , Ck . We assume that all color classes have the same cardinality N . Let Cj = {uji |
i ∈ [N ]}. We describe how to construct an instance (G0 , C 0 , χ0 , s, t, k 0 , `) of Bounded-length
Colored Path-Con. For an edge e ∈ G, associate a distinct color ce , and define C 0 = {ce | e ∈
0 the set {c | e = uv ∈ E(G)∧u ∈ C ∧v ∈ C }.
E(G)}. Moreover, for convenience, we denote by Ci,j
e
i
j
To simplify the description of the construction, we start by defining a gadget that will serve as a
building block for this construction.
For a vertex uji in color class Cj , we define the gadget Gi,j , which is very similar to the one in
Lemma 3.5, as follows. First, we create a copy of each color class Cj 0 , j 0 6= j. Let the resulting
0
0
copies of the color classes be C10 , . . . , Ck−1
. We define the color of a copy v 0 of a vertex uji0 as
0

j j
0
0 0
0
χ0 (v 0 ) = Cj,j
0 \ {ce } if there is an edge e = ui ui0 , and χ (v ) = Cj,j 0 otherwise. Moreover, for each
0

0

i0 ∈ [N − 1] we connect the copies of vertices uji0 and uji0 +1 by an edge.
Next, we introduce k − 2 empty vertices yr , r ∈ [k − 2]. For r ∈ [k − 2], we connect all vertices
0
in Cr0 to yr , and connect yr to all vertices in Cr+1
. This completes the construction of gadget Gi,j ;
36

0
we refer to C10 and Ck−1
as the first and last color classes in gadget Gi,j , respectively. Observe that
0

each color ce for an edge e = uji uji0 appears exactly on
• all vertices in the copies of Cj 0 in the gadgets Gi∗ ,j for i∗ 6= i,
• all vertices in the copies of Cj in the gadgets Gi∗ ,j 0 for i∗ 6= i0 ,
0

• all vertices but the copy of uji0 in the copies of Cj 0 in the gadget Gi,j , and
• all vertices but the copy of uji in the copies of Cj in the gadget Gi0 ,j 0 .
0
Furthermore, every path from a vertex in C10 to a vertex in Ck−1
of length at most 2k − 2 contains
0
exactly one vertex from each Cr , r ∈ [k − 1], and contains all vertices yr , r ∈ [k − 2]. Moreover,
each such path contains all but at most one color from each Cj,j 0 , for all j 0 such that j 0 6= j and if
0
the path does not contain a color ce ∈ Cj,j 0 , then it contains a copy of a vertex uji0 such that there
0
is an edge e = uji uji0 in G.
We continue the construction similarly as in Lemma 3.5 by introducing k + 1 new empty vertices
z0 , . . . , zk , and connecting them as follows. For each color class Cj , j ∈ [k], and each vertex uji ∈ Cj ,
we create the gadget Gi,j , connect zj−1 to each vertex in the first color class of Gi,j , and connect
each vertex in the last color class of Gi,j to zj . Let G0 be the resulting graph. We now set s = z0 ,

t = zk , and k 0 = |E(G)| − k2 and ` = 2k 2 . We are nearly finished with the reduction. However,
we need to make the colors in G0 connected. To achieve this, we first introduce a new vertex o such
0
that χ(o) = C 0 . Now for each j ∈ [k], each j 0 6= j, and each i ∈ [N − 1] we connect the copy of ujN
0
0
in Gi,j with the copy of uj1 in Gi+1,j , and we connect the vertex o with the copies of uj1 in G1,j and
0
of ujN in GN,j , respectively. It is not hard to see that every color is now connected. See Figure 10
for an illustration of the construction, and Figure 11, which highlights the subgraph induced by one
color.
This completes the construction of the instance (G0 , C 0 , χ0 , s, t, k 0 , `) of Bounded-length Colored Path-Con.
Clearly, the reduction that takes an instance (G, k) of Multi-Colored Clique and produces
the instance (G0 , C 0 , χ0 , s, t, k 0 , `) of Bounded-length Colored Path-Con is computable in FPTtime. To show its correctness, suppose that (G, k) is a yes-instance of Multi-Colored Clique,
and let Q be a k-clique in G. Then Q contains a vertex from each Cj , for j ∈ [k]. For a vertex
uji ∈ Q, let Gi,j be its gadget, and define the path Pj as follows. In each color class in Gi,j , pick the
unique vertex that is a copy of a neighbor of uji in Q; define Pj to be the path in Gi,j induced by
the picked vertices, plus the empty vertices yr , r ∈ [k − 2], that appear in Gi,j . Finally, define P
to be the s-t path in G0 whose edges are: the (unique) edge between zr−1 and an endpoint of Pr ,
Pr , and the (unique) edge between an endpoint of Pr and zr , for r ∈ [k]. Clearly, the length of P is
exactly (2k − 2)k + 2k = 2k 2 = `. To show that P is k 0 -valid, observe that none of the nonempty
vertices in P contains a color of an edge between two vertices
in Q. This shows that the number

k
0
of colors that appear on P is at most k = |E(G)| − 2 , and hence, P is k 0 -valid. It follows that
(G0 , C 0 , χ0 , s, t, k 0 ) is a yes-instance of Bounded-length Colored Path-Con.
Conversely, suppose that P is a k 0 -valid s-t path in G0 of length at most 2k 2 . It is easy to see
that P does not contain o, because |χ(o)| = |E(G)|. Moreover, notice that the shortest path from
s to t in G − o has length 2k 2 and each s-t path of length 2k 2 must start at s, visit the gadgets
of exactly k vertices ujij ∈ Cj , for j ∈ [k], ij ∈ [N ], and end at t. Furthermore, the subpath of the

path in each gadget Gi,j has length exactly 2k − 2. We claim that Q = {ujij | j ∈ [k]} is a clique
in G. Recall that the subpath of P that traverses a gadget Gi,j contains all but at most one color
37

from each Cj,j 0 , for all j 0 such that j 0 6= j and if such path does not contain a color ce ∈ Cj,j 0 , then
0
0
it contains a copy of a vertex uji0 such that e = uji uji0 is in G. It follows that if P does not contain
0
the color ce , for an edge e = uji uji0 , then it has to traverse the gadgets for uji and the gadget for

0
uji0 . Since P traverses at most k gadgets and it does not contain k2 colors, it follows that there has
to be an edge between every pair of vertices in G for which P traverses the corresponding gadgets,
and Q is a clique in G. Since |Q| = k, it follows that Q is a k-clique in G, and that (G, k) is a
yes-instance of Multi-Colored Clique.

G1,1

o

s = z0

Gi,1

GN,1

G1,j

z1

zj−1

Gi,j

GN,j

G1,k

zj

zk−1

Gi,k

zk = t

GN,k

Figure 10: Illustration of the reduced instance for the proof of Theorem 6.2.
We now switch our attention to showing that Bounded-length Colored Path-Con parameterized by both k and ` is FPT. We start with the following lemma that enables us to upper bound
the treewidth of the input graph by a function of the parameter `:
Lemma 6.3. Let (G, C, χ, s, t, k, `) be an instance of Bounded-length Colored Path-Con,
and let v be a vertex in G such that dG (s, v) > ` + 1. Let G0 be the graph obtained from G by
contracting any edge uv that is incident to v, and let χ0 (x) = χ(u) ∪ χ(v), where x is the new vertex
resulting from contracting uv, and χ0 (w) = χ(w) for any w ∈ V (G)\{u, v}. Then (G0 , C, χ0 , s, t, k, `)
is a yes-instance of Bounded-length Colored Path-Con if and only if (G, C, χ, s, t, k, `) is.
Proof. Since G is color-connected and χ(x) = χ(u)∪χ(v), it is easy to see that G0 is color-connected
as well. Because dG (s, v) > ` + 1, any solution to (G, C, χ, s, t, k, `) does not contain any of u, v,
and hence, is a solution to (G0 , C, χ0 , s, t, k, `). Conversely, because dG (s, v) ≥ ` + 1, any solution to
(G0 , C, χ0 , s, t, k, `) does not contain x, and hence is a solution to (G, C, χ, s, t, k, `).
By Lemma 6.3, we may assume w.l.o.g. that in an instance (G, C, χ, s, t, k, `) of Boundedlength Colored Path-Con, every vertex v ∈ V (G) satisfies dG (s, v) ≤ ` + 1. Therefore, we may
assume that G has radius at most `+1, and hence G has treewidth at most 3·(`+1)+1 = 3`+4 [28].
At this point we draw the following observation. Although the treewidth of G is bounded by a
function of `, we cannot use the FPT algorithm for Colored Path, parameterized by k and the
treewidth of G, to solve Bounded-length Colored Path-Con because the k-valid path returned
38

G1,1

o

s = z0

Gi,1

G1,j

z1

zj−1

GN,1

Gi0,j

zj

GN,j

Figure 11: Illustration for the proof of Theorem 6.2. The red highlights a color representing the
edge between vertices u1i in C1 and uji0 in Cj .
by the algorithm for Colored Path-Con may have length exceeding the desired upper bound `.
In fact, extending the FPT results for Colored Path to Bounded-length Colored Path-Con
turns out to be a nontrivial task, that necessitates a nontrivial extension of the structural results
in Section 4, as well as the dynamic programming algorithm in Section 5. In particular, the color
contraction operation, on which the structural results developed in Section 4 hinge, is no longer
applicable since contracting an edge may decrease the distance between s and t in the resulting
instance, and hence, may not result in an equivalent instance of the problem. However, we will
show in the next subsection that we can extend the notion of a minimal set of k-valid paths between
two vertices to incorporate the length of these paths, while still be able to upper bound the size of
such a set by a function of both k and the length of these paths.

6.1

Extended Structural Results

We start with the following definition:
Definition 6.4. Let u, v, w ∈ V (G), and let λ ∈ [`]. Let P be a set of k-valid u-v paths in G − w,
each of length λ. The set P is said to be λ-minimal w.r.t. w if there does not exist two paths
P1 , P2 ∈ P such that χ(P1 ) ∩ χ(w) = χ(P2 ) ∩ χ(w).
Let u, v, w ∈ V (G), λ ∈ [`], and let P be a set of λ-minimal k-valid u-v paths in G − w. Let M
be a set of λ-minimal k-valid color-disjoint u-v paths in G − w. Let H be the subgraph of G − w
induced by the edges of the paths in P, and let M be that induced by the edges of the paths in M.
Lemma 6.5. M has a u-v vertex-separator of cardinality at most 2(λ + 1).
Proof. We proceed by contradiction, and assume that M does not have a u-v vertex-separator of
cardinality at most 2(λ + 1). By Menger’s theorem [9], there exists a set D = {P1 , . . . , Pr }, where
r ≥ 2λ+3, of vertex-disjoint u-v paths in M . Let u1 , . . . , ur be the neighbors of u in counterclockwise
order such that Pi contains ui , i ∈ [r], and let Qi be a path in M containing ui .
39

Since all paths in M have the same length λ, Definition 6.4 implies that Observation 4.5 holds.
Therefore, at most one path in M contains only internal colors w.r.t. w in M . By Observation 4.7,
any vertex on a path in M such that the vertex contains an external color w.r.t. w in M must be
incident to the external face to w in M . Choose r0 ∈ [r] such that |r0 − b 2r c| is minimum and Qr0
contains an external color w.r.t. w in M . Since Qr0 contains an external color w.r.t. w in M , Qr0
contains a vertex incident to the external face to w in M . Since all paths in D are u-v vertex-disjoint
paths, Qr0 contains vertices other than u and v from at least br/2c − 1 distinct paths (including
itself) in D. Since the paths in D are all vertex disjoint, it follows that |Qr0 | ≥ r/2 − 1, and hence
λ ≥ r/2 − 1, which implies that r ≤ 2(λ + 1). This contradicts our assumption that r ≥ 2λ + 3.
Lemma 6.6. |M| ≤ g(λ), where g(λ) = O(cλ λ3λ ), for some constant c > 1.
Proof. As in the proof of Lemma 6.5, Definition 6.4 implies that Observation 4.5 holds, and hence,
at most one path in M contains only internal colors w.r.t. w in G − w. Therefore, we upper bound
the number of paths in M that each contains at least one external color to w in G − w, and add
1 to g(λ) at the end. Henceforth, we shall assume that every path in M contains a color that is
external to w in M .
The proof is by induction on λ, over every color-connected plane graph G, every triplet of vertices
u, v, w in G, and every λ-minimal set M w.r.t. w in G − w of k-valid pairwise color-disjoint u-v
paths. If λ = 1, then |M| ≤ 1 ≤ g(1), if we choose g(1) to be at least 1.
Suppose, by the inductive hypothesis, that for any 1 ≤ i < λ, we have |M| ≤ g(i). By
Lemma 6.5, M has a u-v vertex-separator S satisfying |S| ≤ 2λ + 2. S separates M into two
subgraphs Mu and Mv such that u ∈ V (Mu ), v ∈ V (Mv ), and there is no edge between Mu and Mv .
We partition M into two groups: (1) The set of paths in M that each contains a nonempty vertex in
S; and (2) the set of remaining paths M∅ , which contains each path in M whose intersection with
S consists of only empty vertices. Since the paths in M are pairwise color-disjoint, no nonempty
vertex in S can appear on two distinct paths from group (1). Therefore, the number of paths in
group (1) is at most |S| ≤ 2λ + 2.
To upper bound the number of paths in group (2), suppose that S = {s2 , . . . , sr−1 }, where
r ≤ 2λ + 4, and extend S by adding the two vertices s1 = u and sr = v to form the set A =
{s1 , s2 , . . . , sr }. For every two (distinct) vertices sj , sj 0 ∈ A, j, j 0 ∈ [r], j < j 0 , we define a set of
paths Pjj 0 in G − w whose endpoints are sj and sj 0 as follows. For each path P in group (2),
partition P into subpaths P1 , . . . , Pq satisfying the property that the endpoints of each Pi , i ∈ [q],
are in A, and no internal vertex to Pi is in A. Since P contains a vertex that contains an external
color to w in G − w, there exists an i ∈ [q] such that Pi contains a vertex that contains an external
color to w in G − w; pick any such i ∈ [q], and assign Pi to the set of paths Pjj 0 such that sj
and sj 0 are the endpoints of Pi . Since each Pi contains an external color that appears on P and
the paths in M are pairwise-color disjoint, it follows that the map that maps each P to its Pi is a
bijection. Moreover, since each path P must intersect S \ {u, v}, the length of each path in Pjj 0 ,
for j, j 0 ∈ [r], j < j 0 , is strictly smaller than λ.
i0 , have
Fix a set Pjj 0 . For any fixed length i0 ∈ [λ − 1], the subset of paths in Pjj 0 of length i0 , Pjj
0
i0 contains a vertex
sj , sj 0 as endpoints, and are pairwise color-disjoint. Moreover, each path in Pjj
0
i0
that contains an external color to w in G − w. It follows from the previous statements that Pjj
0
i0 , i0 ∈ [λ − 1], is an i0 -minimal set of k-valid
satisfies Definition 6.4 w.r.t. G and w, and hence Pjj
0
i0 | ≤ g(i0 ). Since the number of
sj -sj 0 paths in G w.r.t. w. By the inductive hypothesis, we have |Pjj
0

2λ+4
0
0
sets Pjj is at most
, i ≤ λ − 1, and noting that g is an increasing function, the number of
2
paths in group (2) is O(λ2 ) · (λ − 1) · g(λ − 1) = O(λ3 ) · g(λ − 1).

40

It follows from the above that |M| ≤ g(λ), where g(λ) satisfies the recurrence relation g(λ) ≤
(2λ + 2) + O(λ3 ) · g(λ − 1) = O(λ3 ) · g(λ − 1). Solving the aforementioned recurrence relation gives
g(λ) = O(cλ λ3λ ), where c > 1 is a constant. Adding 1 to g(λ) to account for the single path in M
containing only internal colors w.r.t. w in M yields the same asymptotic upper bound.
Theorem 6.7. Let G be a plane color-connected graph, let u, v, w ∈ V (G), let λ ∈ [`], and let P
be a set of λ-minimal k-valid u-v paths w.r.t. w in G − w. Then |P| ≤ h(k, λ), where h(k, λ) =
O(cλk · k k · λ3λk ), for some constant c > 1.
Proof. The proof is by induction on k. If k = 0, then by minimality of P, there can be at most
one path in P, namely the path consisting of empty vertices. If k = 1, then by minimality of P, we
have P = M, and by Lemma 6.6, |P| = O(cλ λ3λ ) = O(cλk · k k · λ3λk ).
Assume by the inductive hypothesis that the statement of the lemma is true for 1 ≤ i < k. Let
M be a maximal set of pairwise color-disjoint paths in P. By Lemma 4.13, |M| ≤ g(λ) = O(cλ λ3λ ).
The number of colors contained in the vertices of M is at most r ≤ k · g(λ). We group the paths
in P into r groups P1 , . . . , Pr , such that all the paths in Pi , i ∈ [r], share the same color ci , where
i ∈ [r], that is distinct from each color cj shared by the paths in Pj , for j 6= i. We upper bound the
number of paths in each Pi , i ∈ [r], to obtain an upper bound on |P|.
Let Gi be the graph obtained by removing color ci from each vertex in G that ci appears on,
and let Pi0 be the set of paths obtained from Pi by removing color ci from each vertex in Pi that ci
appears on. Clearly, every path in Pi0 is a (k − 1)-valid u-v path of length λ. Moreover, it is easy to
verify that Pi0 satisfies Definition 6.4, and hence, Pi0 is λ-minimal w.r.t. w in Gi −w. By the inductive
hypothesis, we have |Pi0 | ≤ h(k − 1, λ). It follows that the total number of paths in P is at most
h(k, λ), where h(k, λ) satisfies the recurrence relation h(k, λ) ≤ r · h(k − 1, λ) ≤ k · g(λ) · h(k − 1, λ).
Solving the aforementioned recurrence relations yields h(k, λ) = O((k·g(λ))k ) = O(cλk ·k k ·λ3λk ).
The result of Theorem 6.7 will be employed in the next section in the form presented in the
following corollary:
Corollary 6.8. Let G be a plane color-connected graph, let w ∈ V (G), and let λ ∈ [`]. Let G0 be a
subgraph of G − w, and let u, v ∈ V (G0 ). Every set P of λ-minimal k-valid u-v paths in G0 w.r.t. w
satisfies |P| ≤ h(k, λ), where h(k, λ) = O(cλk · k k · λ3λk ), for some constant c > 1.
Proof. Contract every connected component of (G−w)−G0 into a single vertex containing the union
of the color-sets of the vertices in the component, and add k + 1 new distinct colors to the resulting
vertex. Denote the resulting graph by G00 . Observe that the resulting graph is color-connected, and
that every k-valid u-v path of length λ in G0 w.r.t. w is a k-valid u-v path of length λ in G00 w.r.t. w,
and vice versa. Therefore, every set P of λ-minimal k-valid u-v paths in G0 w.r.t. w is also a set of
λ-minimal k-valid u-v paths in G00 w.r.t. w. For any set P of λ-minimal k-valid u-v paths w.r.t. w
in G0 , by applying Theorem 6.7 to P in G00 − w, the corollary follows.

6.2

The Extended Algorithm

Let (G, C, χ, s, t, k, `) be an instance of Bounded-length Colored Path-Con. The algorithm
is a dynamic programming algorithm based on a tree decomposition of G. Let (V, T ) be a nice
tree decomposition of G. By Assumption 2.2, we can assume that s and t are nonadjacent empty
vertices. We add s and t to every bag in T , and from now on, we assume that {s, t} ⊆ Xi , for every
bag Xi ∈ T . For a bag Xi , we say that v ∈ Xi is useful if |χ(v)| ≤ k. Let Ui be the set of all useful
vertices in Xi and let Ui = Xi \ Ui . We denote by Vi the set of vertices in the bags of the subtree
of T rooted at Xi . For any two vertices u, v ∈ Xi , let Giuv = G[(Vi \ Xi ) ∪ {u, v}]. We extend the
41

notion of a λ-minimal set of k-valid u-v paths w.r.t. a vertex, developed in the previous section, to
the set of vertices in a bag of T .
Definition 6.9. Let λ ∈ [`]. A set of k-valid u-v paths Puv in Giuv is λ-minimal w.r.t. Xi if
each path in Puv has length exactly λ and there does not exist two paths P1 , P2 ∈ Puv such that
χ(P1 ) ∩ χ(Xi ) = χ(P2 ) ∩ χ(Xi ).
Lemma 6.10. Let Xi be bag, u, v ∈ Xi , λ ∈ [`] and Puv a λ-minimal set of k-valid u-v paths
w.r.t. Xi in Giuv . Then the number of paths in Puv is at most h(k, λ)|Xi | , where h(k, λ) = O(cλk ·
k k · λ3λk ), for some constant c > 1.
Proof. Let Xi \ {u, v} = {w1 , . . . , wr }, where r = |Xi | − 2. For each wj ∈ Xi , j ∈ [r], let Pj be a
λ-minimal set of k-valid u-v paths w.r.t. wj in Giuv . Without loss of generality, we can pick Pj such
that there is no k-valid u-v path P in Giuv such that Pj ∪ {P } is λ-minimal. From Corollary 6.8, we
have |Pj | ≤ h(k, λ) = O(cλk · k k · λ3λk ), for some constant c > 1. For each P ∈ Puv , and each j ∈ [r],
define Cj = χ(P ) ∩ χ(wj ). Define the signature of P (w.r.t. the colors of w1 , . . . , wr ) to be the tuple
(C1 , . . . , Cr ). Observe that no two (distinct) paths P1 , P2 ∈ Puv have the same signature; otherwise,
since u and v appear on both P1 , P2 , χ(P1 )∩χ(Xi ) = χ(P2 )∩χ(Xi ), which contradicts the definition
of the λ-minimality of Puv . For each P ∈ Puv , and each j ∈ [r], there is a path P 0 ∈ Pj such that
χ(P 0 ) ∩ χ(wj ) = Cj . Otherwise, Pj ∪ {P } satisfy Definition 6.4, which contradicts our assumption
that there is no k-valid u-v path P in Giuv such
Q that Pj ∪ {P } is λ-minimal. It follows that the
number of signatures of paths in Puv is at most rj=1 |Pj | ≤ h(k, λ)|Xi | . Since no two distinct paths
in Puv have the same signature, it follows that |Puv | ≤ h(k, λ)|Xi | .
We define the length of a sequence of paths (walks) S, denoted by |S|, to be the sum of the
lengths of the paths in S.
Definition 6.11. Let Xi be a bag and π = (v1 , σ1 , v2 . . . , σr−1 , vr ) a pattern for Xi . A set Rπ of
sequences of length at most ` that conform to (Xi , π) is a representative set for (Xi , π) if:
(i) For every sequence S1 ∈ Rπ , and for every sequence S2 6= S1 that conforms to (Xi , π), if
S1 i S2 and |S1 | ≤ |S2 | then S2 ∈
/ Rπ ; and
(ii) for every sequence S ∈
/ Rπ , |S| ≤ `, that conforms to (Xi , π) and satisfies that no two paths
in S share a vertex that is not in Xi , there is a sequence W ∈ Rπ such that W i S and
|W| ≤ |S|.
We mention that Lemma 5.5 and Observation 5.7 extend as they are to the current setting.
Lemma 6.12. Let Xi be bag, π a pattern for Xi , and Rπ a representative set for (Xi , π). Then
2
the number of sequences in Rπ is at most h(k, `)|Xi | , where h(k, `) = O(c`k · k k · `3`k ), for some
constant c > 1.
Proof. Let π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t), and let Λ = (λ
P1 , . . . , λr−1 ) be such that, for each
j ∈ [r − 1]: (1) λj = 0 if σj = 0 and λj ∈ [`] otherwise, and (2) r−1
j=1 λj ≤ `. For each λ ∈ [`], the
Pr−1
number of tuples Λ = (λ1 , . . . , λr−1 ) satisfying j=1 λj = λ is the number of weak compositions of λ

into r − 1 parts, which is λ+r−2
that the number of tuples Λ = (λ1 , . . . , λr−1 ) satisfying
r−2 . It follows


Pr−1
`+r−1
i |+`
≤ |Xr−2
≤ 2|Xi |+` . Therefore, if we upper bound the
j=1 λj ≤ ` is upper bounded by
r−2
2

k
3`k )
number of sequences in Rπ corresponding to some fixed tuple Λ by h1 (k, `)|Xi | = O(c`k
1 ·k ·`
2
2
|X
|+`
|X
|
|X
|
i
i
i
for some constant c1 > 1, then we obtain Rπ ≤ 2
· h1 (k, `)
≤ h(k, `)
, where h(k, `) =

42

O(c`k ·k k ·`3`k ), for some constant c > 1. Therefore, for the rest of the proof, we fix Λ = (λ1 , . . . , λr−1 )
Λ
and we let RΛ
π be the subset of Rπ such that for each sequence S = (P1 , . . . , Pr−1 ) in Rπ it holds
that the length of Pj is λj for each j ∈ [r − 1] such that σj = 1.
For each j ∈ [r − 1] such that σj = 1, let Pj be a λj -minimal set of k-valid vj -vj+1 paths
w.r.t. Xi . Without loss of generality, we can pick Pj such that there is no k-valid u-v path P of
length λj in Givj vj+1 such that Pj ∪ {P } is λj -minimal w.r.t. Xi . From Lemma 6.10, it follows that
λ k

3λ k

|Pj | ≤ h1 (k, λj )|Xi | , where h1 (k, λj ) = O(c1 j · k k · λj j ), for some constant c1 > 1.
For a sequence S = (P1 , . . . , Pr−1 ) in Rπ we define the signature of S (w.r.t. Xi ) to be the
tuple (χ(P1 ) ∩ χ(Xi ), . . . , χ(Pr−1 ) ∩ χ(Xi )). Observe that if S1 and S2 have the same signature
w.r.t. Xi , then χ(S1 ) ∪ (χ(S2 ) ∩ χ(Xi )) = χ(S1 ) and χ(S2 ) ∪ (χ(S1 ) ∩ χ(Xi )) = χ(S2 ); hence, either
S1 i S2 or S2 i S1 . Since all sequences in RΛ
π have the same length, it follows from property
(i) of representative sets that no two sequences in Rπ have the same signature w.r.t. Xi . Now let
S = (P1 , . . . , Pr−1 ) be a sequence in Rπ with a signature (C1 , . . . , Cr−1 ). Note that if Cj 6= ∅, then
Pj is not the empty path, and hence σj = 1 and the length of Pj is λj . For each j ∈ [r − 1] such that
Cj 6= ∅, there is a path P ∈ Pj such that χ(P ) ∩ χ(Xi ) = Cj ; otherwise, since χ(Pj ) ∩ χ(Xi ) = Cj
and the length of Pj is λj , Pj ∪ {Pj } would also be a λj -minimal set of paths w.r.t. Xi , which
contradicts our choice of Pj . It follows that the number of signatures of sequences in RΛ
π is at most
Qr−1
Qr−1
2
|X
|
Λ
i
. Since no two distinct sequences in Rπ have the same
j=1 h1 (k, λj ) ≤ h1 (k, `)
j=1 |Pj | ≤
2

2

2

|Xi | and |R | ≤ 2|Xi |+` · h (k, `)|Xi | ≤ h(k, `)|Xi | , where
signature, it follows that |RΛ
π
1
π | ≤ h1 (k, `)
h(k, `) = O(c`k · k k · `3`k ), for some constant c > 1.

For each bag Xi , we maintain a table Γi that contains, for each pattern for Xi , a representative
set of sequences Rπ for (Xi , π). For two vertices u, v ∈ Xi and two u-v paths P, P 0 in Giuv , we say
0 )
that P 0 refines P if χ(P 0 ) ⊆ χ(P ). For two sequences S = (P1 , . . . , Pr−1 ) and S 0 = (P10 , . . . , Pr−1
0
0
that conform to (Xi , π), we say that S refines S if each path Pj refines Pj , for j ∈ [r − 1].
Lemma 6.13. Let Xi be a bag, π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) a pattern for Xi , and
W = (W1 , . . . , Wr−1 ) a sequence such that each Wj is a walk between vertices vj and vj+1 in
Givj vj+1 satisfying χ(Wj ) ≤ k. Then in time O(r · (|V (G)| + |V (E)|)) we can compute a sequence
S = (P1 , . . . , Pr−1 ), where for each j ∈ [r − 1], Pj is an induced path between vj and vj+1 in Givj vj+1
such that χ(Pj ) ⊆ χ(Wj ) and the length of Pj is at most the length of Wj .
Proof. For each walk Wj , j ∈ [r − 1], we do the following. We form the subgraph G0 from Givj vj+1 by
removing every vertex x in Givj vj+1 that does not satisfy χ(x) ⊆ χ(Wj ). Clearly, Wj is a subgraph
of G0 , and hence there exists a vj -vj+1 path of length at most the length of Wj in G0 . We find
a shortest vj -vj+1 path in G0 in time O(|V (G)| + |E(G)|) and set Pj to this path. Clearly, the
computation of S takes time O(r · (|V (G)| + |E(G)|)).
For a bag Xi , pattern π for Xi , and a set of sequences (of walks) R that conform to (Xi , π),
we define the procedure Refine() that takes the set R and outputs a set R0 of sequences of length
at most ` that conform to (Xi , π), and does not violate property (i) of Definition 6.11. First, for
each sequence S in R, we compute a sequence S 0 that refines S and has length at most the length
of S, and replace S with S 0 in R. Afterwards, we initialize R0 = ∅, and order the sequences in R
arbitrarily. We iterate through the sequences in R in order, and add a sequence Sp to R0 if |Sp | ≤ `,
there is no sequence S already in R0 such that S i Sp and |S| ≤ |Sp |, and there is no sequence
Sq ∈ R, q > p (i.e., Sq comes after Sp in the order), such that Sq  Sp and |Sq | ≤ |Sp |.
Lemma 6.14. Let Xi be a bag, π a pattern for Xi , and W be a set of sequences of walks that
conforms to (Xi , π). The procedure Refine(), on input W, produces a set of sequences of induced
43

paths R0 that conform to (Xi , π) and satisfy property (i) of Definition 6.11, and such that for each
sequence S ∈ W with |S| ≤ `, there is a sequence S 0 ∈ R0 satisfying S 0 i S and |S 0 | ≤ |S|.
Moreover, the procedure runs in time O∗ (|W|2 ).
Proof. By Lemma 6.13, refining a sequence in W takes O(|V (G)|+|E(G)|) time, and hence, refining
all sequences in W takes O∗ (|W|) time. After refining W, we initialize R0 to the empty set, and
iterate through the sequences in W, adding a sequence Sp ∈ W to R0 if: |Sp | ≤ `, there is no sequence
S already in R0 such that S i Sp , and |S| ≤ |Sp |. Clearly, this takes O∗ (|W|2 ) time. Moreover,
for a sequence S ∈ W with |S| ≤ `, the refined sequence S 0 we obtained from the application of
Lemma 6.13 to S satisfies |S 0 | ≤ `. The lemma follows.
If a bag Xi is a leaf in T , then Xi = Vi = {s, t}, and there are only two patterns (s, 0, t) and
(s, 1, t) for Xi . Clearly, the only sequence that conforms to (s, 0, t) is the sequence (()) containing
exactly one empty path. Moreover, there is no edge st ∈ E(G). Therefore, there is no sequence
that conforms to (s, 1, t), and the following claim holds:
Claim 6. If a bag Xi is a leaf in T , then Γi = {((s, 0, t), {(())}), ((s, 1, t), ∅)} contains, for each
pattern for Xi , a representative set for (Xi , π).
We describe next how to update the table stored at a bag Xi , based on the tables stored at its
children in T . We distinguish the following cases based on the type of bag Xi .
Case 1. Xi is an introduce node with child Xj . Let Xi = Xj ∪ {v}.
Clearly, for every pattern π for Xi that does not contain v, we can set Γi [π] = Γj [π]. Γj [π] is a
representative set for (Xi , π) for the following reasons: (i) follows because every color in χ(Xi )\χ(Xj )
does not appear in Vj , since Xi is a vertex-separator in G separating v and Vj and colors are
connected. Hence, if two sequences in Γj [π] that conform to (Xi , π) contradict (i), they contradict
(i) w.r.t. (Xj , π) as well, thus contradicting that Γj [π] is a representative set for (Xj , π). For
property (ii), it is easy to observe that v does not appear on any path between two vertices in π
having internal vertices in Vi \ Xi , and hence, this property is inherited from the child node Xj .
Now let π = (v1 = s, σ1 , v2 , σ2 , . . . , σr−1 , vr = t) be a pattern such that vq = v, q ∈ {2, . . . , r−1},
and let π 0 = (v1 , σ1 , . . . vq−1 , 0, vq+1 , σq+1 , . . . , σr−1 , vr ). Note that since Xj is a separator between v
and Vj , the only possibility for a path from v to a different vertex in Xi to have all internal vertices
in Vi \ Xi is if it is a direct edge. Therefore, if σq−1 = 1 (resp. σq = 1) then vq−1 v (resp. vq v) is an
edge in G. Otherwise, there is no sequence that conforms to (Xi , π).
0 ) ∈ Γ [π 0 ], we replace
We obtain Γi [π] from Γj [π 0 ] as follows. For every S 0 = (P10 , P20 , . . . , Pr−2
j
0
the empty path corresponding to 0 between vq−1 and vq+1 in π by two paths Pq−1 , Pq such that
Pq−1 = () (resp. Pq = ()) if σq−1 = 0 (resp. σq = 0) and Pq−1 = (vq−1 , v) (resp. Pq−1 = (v, vq ))
0 ,P
0
0
otherwise and we obtain S = (P10 , . . . , Pq−2
q−1 , Pq , Pq , . . . , Pr−2 ). Denote by Rπ the set of all
formed sequences S. Finally, we set Γi [π] = Refine(Rπ ). We claim that Γi [π] is a representative
set for (Xi , π).
Claim 7. If Xi is an introduce node with child Xj , and Γj contains for each pattern π 0 for Xj a
representative set for (Xj , π 0 ), then Γi [π] defined above is a representative set for (Xi , π).
Proof. From the application of Refine(), it is clear that Γi [π] does not violate property (i) of the
definition of representative sets. Assume now that there exists a sequence S ∈
/ Γi [π] of length at
most ` that conforms to (Xi , π) and violates property (ii) of Definition 6.11. We define the sequence
S 0 that conforms to π 0 , and is the same as S on all paths that π and π 0 share. Since no two paths in
44

S share a vertex that is not in Xi (since S violates (ii)), and all paths in S 0 are also in S, it follows
that no two paths in S 0 share a vertex that is not in Xj . Moreover, |S 0 | ≤ |S| ≤ `. Since Γj [π 0 ]
is a representative set for (Xj , π 0 ), it follows that there exists S10 ∈ Γj [π 0 ] such that S10 j S 0 and
|S10 | ≤ |S 0 |. Let S1 be the sequence obtained from S10 and conforming to (Xi , π). Then S1 ∈ Rπ
and it is easy to verify that |S1 | ≤ `. Hence by Lemma 6.14, there is a sequence S2 ∈ Γi [π] such
that S2 i S1 and |S2 | ≤ |S1 |. Since either both S1 and S contain v or none of them does, we have
S1 i S and |S1 | ≤ |S|. By transitivity of i (Lemma 5.5) and of ≤, it follows that S2 i S and
|S2 | ≤ |S|. This contradicts the assumption that S violates property (ii).
Case 2. Xi is a forget node with child Xj . Let Xi = Xj \ {v}.
Let π = (s = v1 , σ1 , . . . , σr−1 , vr = t) be a pattern for Xi . For q ∈ [r − 1] such that σq = 1, we
0
define π q = (s = v10 , σ10 , . . . , σr0 , vr+1
= t) to be the pattern obtained from π by inserting v between
0
0
vq and vq+1 and setting σq = σq+1 = 1. More precisely, we set vp0 = vp and σp0 = σp for 1 ≤ p ≤ q,
0
0
vq+1
= v and σq+1
= 1, and finally vp0 = vp−1 and σp0 = σp−1 for q + 2 ≤ p ≤ r. We define Rπ as
follows:
Rπ = Γj [π] ∪ {S = (P1 , . . . , Pq−1 , Pq ◦ Pq+1 , Pq+2 , . . . , Pr ) | (P1 , . . . , Pr ) ∈ Γj [π q ], q ∈ [r − 1] ∧ σq = 1}.

Finally, we set Γi [π] = Refine(Rπ ) and we claim that Γi [π] is a representative set for (Xi , π).
Claim 8. If Xi is a forget node with child Xj , and Γj contains for each pattern π 0 for Xj a
representative set for (Xj , π 0 ), then Γi [π] defined above is a representative set for (Xi , π).
Proof. It is straightforward to see that Γi [π] satisfies property (i) due to the way procedure Refine()
works. Assume for a contradiction that there exists a sequence S that violates property (ii). We
distinguish two cases.
First, suppose that no path in S contains v. Then S conforms to (Xj , π). Since no two paths
in S share a vertex that is not in Xi , and since Γj [π] is a representative set, there exists S1 ∈ Γj [π]
such that S1 j S and |S1 | ≤ |S| ≤ `. Then S1 ∈ Rπ , and hence by Lemma 6.14, Γi [π] contains
a sequence S2 such that S2 i S1 and |S2 | ≤ |S1 |. Since S1 j S and Xi ( Xj , it follows from
Observation 5.7 that S1 i S. By transitivity of i , it follows that S2 i S. Moreover, |S2 | ≤ |S|,
which is a contradiction to the assumption that S violates property (ii).
Second, suppose that there is a path Pq in S between vq and vq+1 that contains v. We form a
sequence S 0 from S by keeping every path P 6= Pq in S, and replacing Pq in the sequence by the two
0
subpaths of Pq , Pq0 = (vq , . . . , v) and Pq+1
= (v, . . . , vq+1 ). The sequence S 0 conforms to (Xj , π q ),
and since no two paths in S share a vertex that is not in Xi , no two paths in S 0 share a vertex that
is not in Xj . Moreover, it is straightforward that |S 0 | = |S|. Since Γj [π q ] is a representative set
for (Xj , π q ), it follows that there exists a sequence S10 ∈ Γj [π q ] such that S10 j S 0 and |S10 | ≤ |S 0 |.
Let S1 be the sequence conforming to (Xi , π) obtained from S10 by applying the operation ◦ to the
two paths in S10 that share v. Then S1 ∈ Rπ and |S1 | = |S10 | ≤ `. Therefore, by Lemma 5.11,
Γi [π] contains a sequence S2 such that S2 i S1 . Since S10 j S 0 , χ(S 0 ) = χ(S), χ(S10 ) = χ(S1 ),
and Xi ( Xj , it follows that S1 i S. By transitivity of i , it follows that S2 i S. Moreover
|S2 | ≤ |S|, which is a contradiction to the assumption that S violates property (ii).
Case 3. Xi is a join node with children Xj , Xj 0 .

45

Let π = (s = v1 , σ1 , . . . , σr−1 , vr = t) be a pattern for Xi . Initialize Rπ = ∅. For every two
patterns π1 = (s = v1 , τ1 , . . . , τr−1 , vr = t) and π2 = (s = v1 , µ1 , . . . , µr−1 , vr = t) such that
σq = τq + µq , and for every two sequences S1 = (P11 , . . . , P1r−1 ) ∈ Γj [π1 ] and S2 = (P21 , . . . , P2r−1 ) ∈
Γj 0 [π2 ], we add the sequence S = (P1 , . . . , Pr−1 ) to Rπ , where Pq = P1q if P2q is the empty path,
otherwise, Pq = P2q , for q ∈ [r − 1]. We set Γi [π] = Refine(Rπ ), and we claim that Γi [π] is a
representative set for (Xi , π).
Claim 9. If Xi is a join node with children Xj , Xj 0 , and Γj (resp. Γj 0 ) contains for each pattern
π 0 for Xj = Xj 0 = Xi a representative set for (Xj , π 0 ) (resp. (π 0 , Xj 0 )), then Γi [π] defined above is
a representative set for (Xi , π).
Proof. Clearly Γi [π] satisfies property (i) due to the application of the procedure Refine(). To
argue that Γi [π] satisfies properties (ii), suppose not, and let S = (P1 , . . . , Pr−1 ) be a sequence that
violates property (ii). Notice that every path Pq , q ∈ [r − 1] is either an edge between two vertices in
Xi , or is a path between two vertices in Xi such that its internal vertices are either all in Vj \ Xi or
in Vj 0 \ Xi ; this is true because Xi is a vertex-separator separating Vj \ Xi from Vj 0 \ Xi in G. Define
the two sequences S1 = (P11 , . . . , P1r−1 ) and S2 = (P21 , . . . , P2r−1 ) as follows. For q ∈ [r − 1], if Pq is
empty then set both P1q and P2q to the empty path; if Pq is an edge then set P1q = Pq and P2q to the
empty path. Otherwise, Pq is either a path in G[Vj ] or in G[Vj 0 ]; in the former case set P1q = Pq and
P2q to the empty path, and in the latter case set P2q = Pq and P1q to the empty path. Since no two
paths in S share a vertex that is not in Xi , and Xi = Xj = Xj 0 , no two paths in S1 (resp. S2 ) share
a vertex that is not in Xj (resp. Xj 0 ). Moreover, it is easy to see that |S1 | + |S2 | = |S| ≤ `. Let
π1 = (s = v1 , τ1 , . . . , τr−1 , vr = t) and π2 = (s = v1 , µ1 , . . . , µr−1 , vr = t) be the two patterns that
S1 and S2 conform to, respectively, and observe that, for every q ∈ [r − 1], we have σq = τq + µq .
0 ) in
Since Γj [π1 ] and Γj 0 [π2 ] are representative sets, it follows that there exist S10 = (Y10 , . . . , Yr−1
0
0
0
0
0
0
0
Γj [π1 ] and S2 = (Z1 , . . . , Zr−1 ) in Γj 0 [π2 ] such that S1 j S1 , |S1 | ≤ |S1 | and S2 j 0 S2 , |S2 | ≤ |S2 |.
0 ), where P 0 = Y 0 if Z 0 is the empty path, otherwise, P = Z 0 , for q ∈ [r − 1].
Let S 0 = (P10 , . . . , Pr−1
q
q
q
q
q
0
The sequence S conforms to π, is in Rπ , and |S 0 | = |S10 |+|S20 | ≤ |S|. By Lemma 6.14, Γi [π] contains
a sequence S 00 such that S 00 i S 0 and |S 00 | ≤ |S 0 |. From Observation 5.7, since Xi = Xj = Xj 0 ,
from S10 j S1 and S20 j 0 S2 it follows that S10 i S1 and S20 i S2 . Since χ(S1 ) ∪ χ(S2 ) = χ(S) and
χ(S10 ) ∪ χ(S20 ) = χ(S 0 ), and since χ(S1 ) ∩ χ(S2 ) ⊆ χ(Xi ), by Lemma 5.8, it follows that S 0 i S.
Since S 00 i S 0 , by transitivity of i , it follows that S 00 i S. Moreover |S 00 | ≤ |S|, which concludes
the proof.
We can now conclude with the following theorem:
Theorem 6.15. There is an algorithm that on input (G, C, χ, s, t, k, `) of Bounded-length Colored Path-Con, either outputs a k-valid s-t path of length at most ` in G, or decides that no
2
such path exists, in time O? (f (k, `)37` ), where f (k, `) = O(c`k · k k · `3`k ), for some constant c > 1.
Therefore, Bounded-length Colored Path-Con parameterized by both k and ` is FPT.
Proof. If dG (s, t) > `, then, by definition, there is no s-t path of length at most `. Hence, we assume
that dG (s, t) ≤ `. By Lemma 6.3, if there exists a vertex v such that dG (s, v) > `+1, we can contract
any edge incident to v and obtain an equivalent instance. The contraction of a single edge can be
done in time polynomial in the size of the instance, and after applying Lemma 6.3 |E| times, we
would get a trivial instance. Moreover, from the proof of Lemma 6.3, it follows that we can obtain
a solution in the original instance from a solution in the contracted instance in polynomial time.
Therefore, we can assume for the rest of the proof that we applied Lemma 6.3 exhaustively, and
hence G has radius at most ` + 1 and treewidth ω that is at most 3` + 4 [28]. Moreover, a tree
decomposition of G of width ω can be computed in (polynomial) time O(` · n) [23]. From such
46

a tree decomposition, in polynomial time we can compute a nice tree decomposition (V, T ) of G
whose width is at most ω ≤ 3` + 4 and satisfying |V| = O(|V (G)|) [24].
The algorithm starts by removing the colors of s and t from G, and decrements k by |χ(s) ∪ χ(t)|
(see Assumption 2.2). Afterwards, if k < 0, the algorithm concludes that there is no k-valid s-t
path in G. If st ∈ E(G) and k ≥ 0, the algorithm outputs the path (s, t). Now we know that s
and t are not adjacent, and that χ(s) = χ(t) = ∅. The algorithm then adds s and t to every bag in
T , and executes the dynamic programming algorithm based on (V, T ), described in this section, to
compute a table Γi that contains, for each bag Xi in T and each pattern π for Xi , a representative
set Rπ for (Xi , π).
From Claims 6, 7, 8, 9, it follows, by induction on the height of the tree-decomposition (V, T )
(the base case corresponds to the leaves), that the root node Xr contains a representative set Γr [π]
for the sequence π = (s, 1, t). If Γr [π] is empty, the algorithm concludes that there is no k-valid
s-t path of length at most ` in G. Otherwise, noting that there is only one sequence S in the
representative set Γr [π] since Xr = {s, t} and s and t are empty, the algorithm outputs the k-valid
s-t path P of length at most ` formed by S. The correctness follows from the following argument,
which shows that if there is a k-valid s-t path of length at most ` in G, then the algorithm outputs
such a path. Suppose that P 0 is a k-valid induced s-t path of length at most ` and let S 0 = (P 0 ).
Since Grst = G, it follows that S 0 conforms to (Xr , π). Moreover |S 0 | ≤ ` and S 0 contains exactly
one path that is induced, hence no two paths in S 0 share a vertex. Therefore, by property (ii) of
representative sets, there exists a sequence S in Γr [π] satisfying S r S 0 and |S| ≤ |S 0 |. Noting that
a sequence in Γr [π] must consist of a single k-valid s-t path of length at most `, it follows that the
algorithm correctly outputs such a path.
Next, we analyze the running time of the algorithm. We observe that among the three types
of bags in T , the worst running time is for a join bag. Therefore, it suffices to upper bound the
running time for a join bag, and since |V| = O(n), the upper bound on the overall running time
would follow.
Consider a join bag Xi with children Xj , Xj 0 . Let ω 0 be the width of T plus 1, which serves as an
upper bound on the bag size in T . Therefore, we have ω 0 ≤ 3`+7, where the (additional) plus 2 is to
account for the vertices s and t that were added to each bag. The algorithm starts by enumerating
0
0
each pattern π for Xi . The number of such patterns is at most 2ω ·ω 0 ·ω 0 ! = O∗ (2ω ·ω 0 !), where ω 0 ·ω 0 !
0
is an upper bound on the number of ordered selections of a subset of vertices from the bag, and 2ω is
an upper bound on the number of combinations for the σi ’s in the selected pattern. Fix a pattern π
for Xi . To compute Γi [π], the algorithm enumerates all ways of partitioning π into pairs of patterns
0
π1 , π2 for the children bags; there are 2ω ways of partitioning π into such pairs, because for each
σi = 1 in π, the path between vi and vi+1 is either reflected in π1 or in π2 . For a fixed pair π1 , π2 ,
the algorithm iterates through all pairs of sequences in the two tables Γj [π1 ] and Γj 0 [π2 ]. Since
02
each table contains a representative set, by Lemma 6.12, the size of each table is h1 (k, `)ω , where
k
3`k ) for some constant c > 1, and hence iterating over all pairs of sequences
h1 (k, `) = O(c`k
1
1 ·k ·`
02
in the two tables can be done in O(h1 (k, `)2ω ) time. From the above, it follows that the set Rπ
0
02
02
k
3`k ),
can be computed in time 2ω · O(h1 (k, `)2ω ) = O(h2 (k, `)2ω ), where h2 (k, `) = O(c`k
2 ·k ·`
for some constant c2 > 1, which is also an upper bound on the size of Rπ . By Lemma 6.14,
02
applying Refine() to Rπ takes time O∗ (h2 (k, `)4ω ). It follows from all the above that the running
02
0
02
time taken by the algorithm to compute Γi is O∗ (h2 (k, `)4ω · 2ω · ω 0 !) = O∗ (h3 (k, `)4ω ), where
k
3`k ), for some constant c > 1, and hence the running time of the algorithm
h3 (k, `) = O(c`k
3
32 · k · `
is O? (f (k, `)37` ), where f (k, `) = O(c`k · k k · `3`k ), for some constant c > 1.

47

6.3

Applications

In this subsection, we describe some applications of Theorem 6.15. The first result is a direct
consequence of Theorem 6.15.
Corollary 6.16. For any computable function h, the restriction of Colored Path-Con to instances in which the length of the sought path is at most h(k) is FPT parameterized by k.
We note that the above restriction of Colored Path-Con is NP-hard, as a consequence of
(the proof of) Corollary 3.3.
Corollary 6.16 directly implies Kroman et al.’s results [25], showing that Obstacle Removal
parameterized by k is FPT for unit-disk obstacles and for similar-size fat regions with constant
overlapping number. Using Bereg and Kirkpatrick’s result [2], the length of a shortest k-valid path
for unit-disk obstacles is at most 3k (see also Lemma 3 in Korman et al. [25]). By Corollary 2 in [25],
the length of a shortest k-valid path for similar-size fat-region obstacles with constant overlapping
number is linear in k. Corollary 6.16 generalizes these FPT results, which required quite some effort,
and provides an explanation to why the problem is FPT for such restrictions, namely because the
path has length upper bounded by a function of the parameter. In particular, one may allow the
connected obstacles to be of various shapes and sizes, provided that the length of the path is upper
bounded by a function of the parameter.
The second application we describe is related to an open question posed in [12]. For an instance
I = (G, C, χ, s, t, k) of Colored Path-Con, and a color c ∈ C, define the intersection number
of c, denoted ι(c), to be the number of vertices in G on which c appears. Define the intersection
number of G, ι(G), as max{ι(c) | c ∈ C}. Consider the following problem:
Bounded-intersection Colored Path-Con
Given: A planar graph G such that ι(G) ≤ i; a set of colors C; χ : V −→ 2C ; two designated
vertices s, t ∈ V (G); and k, i ∈ N
Question: Does there exist a k-valid s-t path in G?
Again, the above problem is NP-hard, as a consequence of (the proof of) Corollary 3.3.
Corollary 6.17. Bounded-intersection Colored Path-Con is FPT parameterized by both k
and i.
Proof. Since the number of vertices in G on which any color c ∈ C appears is at most ι(G), the
length of any k-valid s-t path is O(k · i). The result now follows from Theorem 6.15.
The following corollary is a direct consequence of Corollary 6.17:
Corollary 6.18. For any computable function h, Bounded-intersection Colored Path-Con
restricted to instances (G, C, χ, s, t, k) satisfying ι(G) ≤ h(k) is FPT parameterized by k.
Corollary 6.17 has applications pertaining to instances of Connected Obstacle Removal
whose auxiliary graph is an instance of Bounded-intersection Colored Path-Con. In particular, an interesting case that was studied corresponds to the case in which the obstacles are convex
polygons, each intersecting at most a constant number of other polygons. The complexity of this
problem was left as an open question in [12, 18], and remains unresolved. The result in Corollary 6.18 subsumes this case, and even the more general case in which the obstacles are arbitrary
convex obstacles satisfying that each obstacle intersects a constant number of other obstacles, as it

48

is easy to see that the auxiliary graph of such instances will have a constant intersection number3 . In
fact, we can even allow the intersection number to be any (computable) function of the parameter:
Theorem 6.19. Let h be a computable function. The restriction of Connected Obstacle Removal to any set of convex obstacles in the plane satisfying that each obstacle intersects at most
h(k) other obstacles, is FPT parameterized by k.
Whereas the complexity of the problem in the above theorem is open, the theorem settles its
parameterized complexity by showing it to be in FPT.

References
[1] H. Alt, S. Cabello, P. Giannopoulos, and C. Knauer. On some connection problems in straightline segment arrangements. In Proceedings of EuroCG, pages 27–30, 2011.
[2] S. Bereg and D. Kirkpatrick. Approximating barrier resilience in wireless sensor networks. In
Proceedings of ALGOSENSORS, pages 29–40, 2009.
[3] R. Carr, S. Doddi, G. Konjevod, and M. Marathe. On the red-blue set cover problem. In
Proceedings of SODA, pages 345–353, 2000.
[4] D. Chan and D. Kirkpatrick. Multi-path algorithms for minimum-colour path problems with
applications to approximating barrier resilience. Theoretical Computer Science, 553:74–90,
2014.
[5] D. Chen and H. Wang. Computing shortest paths among curved obstacles in the plane. ACM
Transanctions on Algorithms, 11(4):26:1–26:46, 2015.
[6] Y. Chen, J. Flum, and M. Grohe. Machine-based methods in parameterized complexity theory.
Theoretical Computer Science, 339(2-3):167–199, 2005.
[7] Y. Chen, M. Grohe, and M. Grüber. On parameterized approximability. In Proceedings of
IWPEC, pages 109–120, 2006.
[8] H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fáry embeddings of planar
graphs. In Proceedings of STOC, pages 426–433. ACM, 1988.
[9] R. Diestel. Graph Theory, 4th Edition. Springer, 2012.
[10] R. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer
Science. Springer, Berlin, Heidelberg, 2013.
[11] E. Eiben, J. Gemmell, I. Kanj, and A. Youngdahl. Improved results for minimum constraint
removal. In Proceedings of AAAI. AAAI Press, 2018.
[12] L. Erickson and S. LaValle. A simple, but NP-hard, motion planning problem. In Proceedings
of AAAI. AAAI Press, 2013.
[13] I. Fáry. On straight line representation of planar graphs. Acta Universitatis Sezegediensis,
11:229–233, 1948.
3

Note that convexity is essential here, as otherwise, the intersection number of the auxiliary graph may be unbounded.

49

[14] M. Fellows, J. Guo, and I. Kanj. The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727–740, 2010.
[15] M. Garey and D. Johnson. Computers and Intractability. W.H. Freeman, 1979.
[16] A. Gorbenko and V. Popov. The discrete minimum constraint removal motion planning problem. In Proceedings of the American Institute of Physics, volume 1648. AIP Press, 2015.
[17] S. Hartung and R. Niedermeier. Incremental list coloring of graphs parameterized by conservation. Theoretical Computer Science, 494:86–98, 2013.
[18] K. Hauser. The minimum constraint removal problem with three robotics applications. International Journal of Robotics Research, 33(1):5–17, 2014.
[19] J. Hershberger, N. Kumar, and S. Suri. Shortest Paths in the Plane with Obstacle Violations.
In Proceedings of ESA, volume 87 of LIPIcs, pages 49:1–49:14, 2017.
[20] J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane.
SIAM Journal on Computing, 28(6):2215–2256, 1999.
[21] I. Hicks. Planar branch decompositions I: The ratcatcher. INFORMS Journal on Computing,
17(4):402–412, 2005.
[22] D. Johnson and M. Szegedy. What are the least tractable instances of Max independent set?
In Proceedings of SODA, pages 927–928. ACM/SIAM, 1999.
[23] I. Katsikarelis. Computing bounded-width tree and branch decompositions of k-outerplanar
graphs. CoRR, abs/1301.5896, 2013. URL: http://arxiv.org/abs/1301.5896.
[24] T. Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994.
[25] M. Korman, M. Löffler, R. Silveira, and D. Strash. On the complexity of barrier resilience for
fat regions. In Proceedings of ALGOSENSORS, pages 201–216, 2014.
[26] S. Kumar, T. Lai, and A. Arora. Barrier coverage with wireless sensors. In Proceedings of
MOBICOM, pages 284–298. ACM, 2005.
[27] D. Marx. Completely inapproximable monotone and antimonotone parameterized problems.
Journal of Computers and System Sciences, 79(1):144–151, 2013.
[28] N. Robertson and P. Seymour. Graph minors. III. planar tree-width. Journal of Combinatorial
Theory, Series B, 36(1):49 – 64, 1984.
[29] P. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217–241,
1994.
[30] K. Tseng and D. Kirkpatrick. On barrier resilience of sensor networks. In Proceedings of
ALGOSENSORS, pages 130–144, 2012.
[31] S. Yang. Some Path Planning Algorithms in Computational Geometry and Air Traffic Management. PhD thesis, University of New Yort at Stony Brook. Available at:
https://dspace.sunyconnect.suny.edu/handle/1951/59927, 2012.
[32] S. Yuan, S. Varma, and J. Jue. Minimum-color path problems for reliability in mesh networks.
In Proceedings of INFOCOM, pages 2658–2669, 2005.

50

