The Stackelberg Minimum Spanning Tree Game \\ on Planar and Bounded-Treewidth Graphs
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth.
planarStackMST.tex
\documentclass[11pt, a4paper]{article}
\usepackage[lmargin=30mm,rmargin=30mm,tmargin=25mm,bmargin=25mm]{geometry}
\renewcommand{\baselinestretch}{1.15}
\setlength{\footnotesep}{\baselinestretch\footnotesep}

\usepackage{subfigure, times, graphicx, amsthm, amsmath, amssymb, color, enumerate, verbatim}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}

\newcommand{\spl}{series-parallel}
\newcommand{\stackmst}{\textsc{StackMST}}

\newcommand{\paths}[4]{ \mathcal{P}(#1, #2, #3, #4) }
\newcommand{\redpaths}[4]{ \widetilde{\mathcal{P}}(#1, #2, #3, #4) }  
\newcommand{\bneck}[4]{ w(#1, #2, #3, #4) }
\newcommand{\redbneck}[4]{ \widetilde{w}(#1, #2, #3, #4) }

\DeclareMathOperator{\OPTsymbol}{OPT}
\newcommand{\OPT}[4]{\OPTsymbol_{#2}(#1,#3,#4)} %'value' of opt

\newcommand{\Q}{\mathcal{Q}}
\newcommand{\true}{\textrm{true}}
\newcommand{\false}{\textrm{false}}
\newcommand{\pcomp}{parallel-compatible}
\newcommand{\scomp}{series-compatible}
\DeclareMathOperator{\mc}{mc}


\title{The Stackelberg Minimum Spanning Tree Game \\ on Planar and Bounded-Treewidth Graphs}

\author{
Jean Cardinal\thanks{Universit\'e Libre de Bruxelles (ULB), D\'epartement d'Informatique, CP~212, B-1050 Brussels, Belgium, jcardin@ulb.ac.be.}
\and
Erik D. Demaine\thanks{MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA 02139, USA,  edemaine@mit.edu.}
\and
Samuel Fiorini\thanks{Universit\'e Libre de Bruxelles (ULB), D\'epartement de Math\'ematique, CP~216,  B-1050 Brussels, Belgium,  sfiorini@ulb.ac.be.}
\and 
Gwena\"el Joret\thanks{Universit\'e Libre de Bruxelles (ULB), D\'epartement d'Informatique, CP~212,  B-1050 Brussels, Belgium, gjoret@ulb.ac.be. G. Joret is a Postdoctoral Researcher of the Fonds National de la Recherche Scientifique (F.R.S.--FNRS).}
\and 
Ilan Newman\thanks{Department of Computer Science, University of Haifa, Haifa 31905, Israel, ilan@cs.haifa.ac.il.}
\and
Oren Weimann\thanks{Weizmann Institute of Science, Faculty of Mathematics and Computer Science, POB 26, Rehovot 76100, Israel, oren.weimann@weizmann.ac.il.}
}

\begin{document}
\sloppy

\date{}
\maketitle

\sloppy

\begin{abstract}
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07.
The game is played on a graph (representing a network), whose edges are colored either red or blue, 
and where the red edges have a given fixed cost (representing the competitor's prices).
The first player chooses an assignment of prices to the blue edges,
and the second player then buys the cheapest spanning tree, using any combination of red and blue edges.
The goal of the first player is to maximize the total price of purchased blue edges.

We study this problem in the cases of planar and bounded-treewidth graphs. 
We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth.
\end{abstract}

\section{Introduction}

%In the context of algorithmic game theory, pricing problems have recently drawn much attention. 
%Many of them originate from auction theory (see for instance \cite{BBM08,BK06,GHKKKS05}), while some others are related to combinatorial
%optimization problems on graphs (for instance~\cite{BHK08,GLSU09-journal,LMS98,RSM05,vH06,BGPW08}). We study a problem in the latter category.

A young startup company has just acquired a collection of point-to-point tubes
between various sites on the Interweb.  The company's goal is to sell the use
of these tubes to a particularly stingy client, who will buy a minimum-cost
spanning tree of the network.  Unfortunately, the company has a direct
competitor: the government sells the use of a different collection of
point-to-point tubes at publicly known prices.
Our goal is to set the company's tube prices to maximize the company's income,
given the government's prices and the knowledge that the client will buy a
minimum spanning tree made from any combination of company and government tubes.
Naturally, if we set the prices too high, the client will rather buy the
government's tubes, while if we set the prices too low, we unnecessarily
reduce the company's income.

\begin{figure}
\begin{center}
\includegraphics[scale=.4]{stackmst.pdf}
\end{center}
\caption{\label{fig:example}A sample instance of the {\stackmst} problem.
  The goal is to assign prices to the blue edges to maximize the total
  price of the blue edges purchased in a minimum spanning tree.}
\end{figure}

This problem is called the {\em Stackelberg Minimum Spanning Tree Game}
\cite{CDFJLNW-sub}, and is an example in the growing family of algorithmic
game-theoretic problems about combinatorial optimization in graphs
\cite{BHK08,GLSU09-journal,LMS98,RSM05,vH06,BGPW08}.
More formally, we are given an undirected graph $G$
(possibly with parallel edges, but no loops), whose edge set $E(G)$ is
partitioned into a {\em red edge set} $R(G)$ and a {\em blue edge set} $B(G)$.
We are also given a cost function $c:R(G)\to {\mathbb R}^+$ assigning a
positive cost to each red edge.  The {\stackmst} problem is to assign
a price $p(e)$ to each blue edge~$e$,
resulting in a weighted graph $(G,c \cup p)$,
to maximize the total price of blue edges in a minimum spanning tree.
We assume that, if there is more than one minimum spanning tree,
we obtain the maximum possible income.
(Otherwise, we could decrease the prices slightly
and get arbitrarily close to the same income.)
Figure~\ref{fig:example} shows an example.

This problem is thus a two-player two-level optimization problem,
in which the leader (the company) chooses a strategy (a price assignment),
taking into account the strategy of the follower (the client),
which is determined by a second-level optimization problem
(the minimum spanning tree problem).
Such a game is known as a {\em Stackelberg game} in economics~\cite{Stack34}.

The complexity and approximability of the \stackmst\ problem has been studied
in a previous paper~\cite{CDFJLNW-sub}, which shows the following results.
The problem is APX-hard, but can be approximated within a logarithmic factor.
Constant-factor approximation exist for the special cases in which the given
costs are bounded or take a bounded number of distinct values.  Finally, an
integer programming formulation has an integrality gap corresponding to the
best known approximation factors.

Instead of restricting the edge weights, we can restrict the class of allowed
graphs, with the hope of obtaining better approximation algorithms.
One natural class of graphs is {\em planar graphs}, on which many important
problems admit polynomial-time approximation schemes.
Many of these results use Baker's technique \cite{Baker94} or more
modern variations \cite{Klein05,Klein06,BKK07,DHM07,DHK09},
which ultimately rely on the ability to efficiently solve the problem
in graphs of bounded treewidth in polynomial time.
Such algorithms generally use dynamic programming,
using a textbook technique for well-behaved problems.
In particular, the problem of checking a graph-theoretic property
expressible in monadic second-order logic is fixed-parameter tractable
with respect to the treewidth of the graph; see~\cite{C08} for a survey.
However, few if any such dynamic programs have been developed for
a two-level optimization problem such as \stackmst,
and standard techniques do not seem to apply.

In this paper, we consider the {\stackmst} problem in these two graph
classes: planar graphs and bounded-treewidth graphs.
We prove in Section~\ref{Planar Graphs} that {\stackmst}
remains NP-hard when restricted to planar graphs.
We develop in Section~\ref{Bounded-Treewidth Graphs}
a polynomial-time dynamic programming algorithm
for {\stackmst} in graphs of bounded treewidth.
Along the way, we develop in Section~\ref{Series-Parallel Graphs}
a dynamic programing algorithm for series-parallel graphs,
or equivalently, biconnected graphs of treewidth at most~$2$,
which are also planar.

To our knowledge, our algorithms are the first examples of a two-level pricing
problem solved by dynamic programming on a graph decomposition tree.
We believe that this result provides insight into the structure of the problem,
and could be a stepping stone toward a polynomial-time approximation scheme
for planar graphs.
More generally, we believe that our techniques may be useful in the design of
dynamic programming algorithms for other pricing problems in graphs, including
pricing problems with many followers~\cite{BHK08,GLSU09-journal}, and
Stackelberg problems involving shortest paths~\cite{RSM05}
or shortest path trees~\cite{BGPW08}.

\section{Planar Graphs}
\label{Planar Graphs}

We consider the {\stackmst} problem on planar graphs. We strengthen the hardness result given in~\cite{CDFJLNW-sub} by showing that the problem
remains NP-hard in this special case. The reduction is from the {\em minimum connected vertex cover problem}, which is known to be NP-hard, 
even when restricted to planar graphs of maximum degree 4 (see Garey and Johnson~\cite{GJ}). The minimum connected vertex cover problem consists
of finding a minimum-size subset $C$ of the vertices of a graph, such that every edge has at least one endpoint in $C$, and $C$ induces
a connected graph.

\begin{theorem}
\label{thm-hard}
The {\stackmst} problem is NP-hard, even when restricted to planar graphs.
\end{theorem}

\begin{proof}
Given a planar graph $G = (V,E)$, with $|V|=n$ and $|E|=m$, we construct an instance of {\stackmst} with red costs in $\{1,2\}$. Let $G'=(V',R\cup B)$ be the graph for this instance, with $(R,B)$ a bipartition of the edge set. We first let $V'=V\cup E$. The set of blue edges $B$ is the set $\{ ve : e\in E, v\in e  \}$. Thus the blue subgraph is the vertex-edge incidence graph of $G$, which is clearly planar. Given a planar embedding of the blue subgraph, we connect all vertices $e\in E$ of $G'$ by a tree, all edges of which are red and have cost $1$. The graph can be kept planar by letting those red edges be nonintersecting chords of the faces of the embedding. Finally, we double all blue edges by red edges of cost 2. The whole construction is illustrated in figure~\ref{fig:redu1}.

\begin{figure}
\begin{center}
\subfigure[\label{fig:redu1}The graphs $G$ and $G'$.]{\includegraphics[angle=-90, scale=.45]{stackMSTredu1.pdf}}
\hspace{1cm}
\subfigure[\label{fig:redu2}A connected vertex cover in $G$ and the corresponding price function in $G'$.]{\includegraphics[angle=-90, scale=.45]{stackMSTredu2.pdf}}
\end{center}
\caption{Illustration of the proof of Theorem~\ref{thm-hard}.}
\end{figure}

% claim

Let $t$ be a positive integer. We show that the revenue for an optimal price function for $G'$ is at least $m + 2n - t - 1$ if and only if there exists a connected vertex cover of $G$ of size at most $t$.

\medskip

% <-

$(\Leftarrow)$
We first suppose that there exists such a connected vertex cover $C\subseteq V$, and show how to construct a price function yielding the given revenue.

From the set $C$, we can construct a tree made of blue edges that spans all vertices $e\in E$ of $G'$. The set of vertices of this tree is $C\cup E$, 
and its edges are of the form $ue\in E'$, with $u\in C$ and $e\in E$ (see figure~\ref{fig:redu2}). 
This tree has $t+m-1$ blue edges, to which we assign price $1$. Now we have to connect the remaining $n-t$ vertices belonging to $V$. Since the only red edges incident to these vertices have cost $2$, we can use $n-t$ blue edges of price $2$ to include these vertices in the minimum spanning tree. The price of the other blue edges is set to $\infty$. The revenue for this price function is exactly $(t+m-1) + 2(n-t) = m+2n-t-1$.

\medskip

% ->

$(\Rightarrow)$
Now suppose that we have a price function yielding revenue at least $m + 2n - t - 1$. We can assume (see~\cite{CDFJLNW-sub}) that all the prices belong to the set $\{ 1,2,\infty \}$. We also assume that the price function is optimal and minimizes the number of red edges in the resulting spanning tree $T$.

First, we observe that $T$ does not contain any red edge. 
By contradiction, if $T$ contains a red edge of cost 2, then this edge can be replaced by the parallel blue edge. 
On the other hand, if $T$ contains a red edge $f$ of cost 1, we consider the cut defined by removing $f$ from $T$. 
In the face used to define $f$, there exists a blue edge having its endpoints across the cut and does not belong to $T$. 
So we can use this blue edge, with a price equal to 1, to reconnect the tree.

Now let us consider the blue edges of price $1$ in $T$. 
We claim that the graph $H$ induced by these edges contains all vertices $e\in E$ of $G'$ and is connected.

Clearly, all vertices $e\in E$ of $G'$ are incident to a blue edge of price $1$, otherwise it can be reconnected to $T$ with a red edge of cost $1$, and $T$ is not minimum. 
Thus $E \subseteq V(H)$, where $V(H)$ is the vertex set of $H$. 
Letting $C := V(H)\cap V$, we conclude that $C$ is a vertex cover of the original graph $G$.

Now we show that $H$ is connected. Suppose otherwise; then there exist two vertices of $G'$ in $E$ that are connected by a red edge of cost $1$, and belonging to two different connected components $H_1$ and $H_2$ of $H$. 
Consider the (blue) edge that connects $H_1$ and $H_2$ in $T$.
This edge cannot have price 2 in $T$, since $H_1$ and $H_2$ are connected by a red edge of cost $1$. 
Hence the blue edge has price 1 and belongs to $H$.
Therefore $H$ is connected and $C$ is a connected vertex cover of $G$.

Finally the remaining vertices $V-C$ of $G'$ must be leaves of $T$, since otherwise they belong to a cycle containing a red edge of cost $1$. The total cost of $T$ is therefore $(m+|C|-1) + 2(n-|C|) = m + 2n - |C| - 1$. Since we know this is at least $m + 2n - t - 1$, we conclude that $|C|\leq t$.
\end{proof}

\section{Series-Parallel Graphs}
\label{Series-Parallel Graphs}

We now describe a polynomial-time dynamic programming algorithm for solving
the {\stackmst} problem on series-parallel graphs.  These graphs are the
biconnected graphs excluding $K_4$ as a minor, or equivalently,
biconnected graphs with treewidth at most~$2$.

We use the following inductive definition of (connected) series-parallel graphs. Consider a connected graph $G$ with two distinguished vertices
$s$ and $t$. The graph $(G,s,t)$ is a {\sl series-parallel} graph if 
either $G$ is a single edge $(s,t)$, or $G$ is a {\sl series} or {\sl parallel} composition
of two series-parallel graphs $(G_{1},s_{1},t_{1})$ and $(G_{2},s_{2},t_{2})$.
The series composition of $G_1$ and $G_2$ is formed by setting  $s = s_{1}, t=t_{2}$ and identifying $t_1=s_2$; the parallel composition is formed by identifying $s = s_{1}=s_{2}$ and $t=t_{1}=t_{2}$.

\begin{theorem}
\label{th-sp}
The {\stackmst} problem can be solved in $O(m^4)$ 
time on series-parallel graphs.
\end{theorem}

\subsection{Definitions}
\label{sec-def}

Let us fix an instance of {\stackmst}, that is, a graph $G$ with $E(G) = R(G) \cup B(G)$ endowed 
with a cost function $c: R(G) \to \mathbb{R}_{+}$. Denote by $c_{1}, c_{2}, \dots, c_{k}$ the different values taken
by $c$, in increasing order. Let also $c_{0}:=0$.\medskip

For two distinct vertices $s,t \in V(G)$ of $G$ and
a subset $F \subseteq B(G)$ of blue edges, define $\paths{G}{F}{s}{t}$
as the set of $st$-paths in the graph $(V(G), R(G) \cup F)$.
Let also $\redpaths{G}{F}{s}{t}$ denote the subset of paths in $\paths{G}{F}{s}{t}$
that contain at least one red edge. 
A lemma of Cardinal {\it et al}.~\cite{CDFJLNW-sub} can be restated as follows.

\begin{lemma}[\cite{CDFJLNW-sub}]
\label{lem-opt-for-fixed-blue}
Suppose that $G$ contains a red spanning tree, and let $F\subseteq B(G)$ be 
an acyclic subset of blue edges. Then, the maximum revenue achievable by the leader,
over solutions where the set of blue edges bought by the follower is exactly $F$,
is obtained by setting the price of each edge $st \not\in F$ to $+\infty$, and the price
of each edge $st\in F$ to
$$
\min\left\{ \max_{e\in P\cap R(G)} c(e) \mid P\in \redpaths{G}{F}{s}{t} \right\}.
$$
\end{lemma}

This lemma states that if we know the set of blue edges that will eventually be bought, the price of a selected 
blue edge $st$ is given by the minimum, over the paths from $s$ to $t$, of the largest red cost on this path.

Motivated by this result, we introduce some more notations. 
For a subset $Z \subseteq E(G)$ of edges, we define $\mc(Z)$ as the maximum 
cost of a red edge in $Z$ if $Z \cap R(G) \neq \varnothing$, as $c_{0}=0$ otherwise.
(The two letters $\mc$ stand for ``max cost''.)
We define $\bneck{G}{F}{s}{t}$ as
%
$$
\bneck{G}{F}{s}{t}:= \left\{
\begin{array}{ll}
\min \left\{\mc(P) \mid P \in \paths{G}{F}{s}{t}\right\} & 
\textrm{ if } \paths{G}{F}{s}{t} \neq \varnothing; \\
c_{k}  & \textrm{ otherwise}.
\end{array}
\right.
$$
%
Similarly,
%
$$
\redbneck{G}{F}{s}{t}:= \left\{
\begin{array}{ll}
\min \left\{\mc(P) \mid P \in \redpaths{G}{F}{s}{t}\right\} & 
\textrm{ if } \redpaths{G}{F}{s}{t} \neq \varnothing; \\
c_{k}  & \textrm{ otherwise}.
\end{array}
\right.
$$
Thus, the price assigned to the edge $st\in F$ in Lemma~\ref{lem-opt-for-fixed-blue} is $\redbneck{G}{F}{s}{t}$.
Also, we will consider graphs that do not necessarily contain a red spanning tree;
this is why we need to treat the case where $\paths{G}{F}{s}{t}$ or $\redpaths{G}{F}{s}{t}$ is empty in the above definitions.
\bigskip

In what follows, we let $[k] := \{ 0,1,\ldots , k\}$.
Our dynamic programming solution for series-parallel graphs associates a value to each pair $(H, q)$, 
where $q\in [k]^2$, and $H$ is a graph appearing in the series-parallel decomposition of $G$.


A subset $F\subseteq B(G)$ of blue edges {\sl realizes} $q=(i,j)\in [k]^2$ in $(G,s,t)$ if 
$F$ is acyclic and $\bneck{G}{F}{s}{t}=c_{i}$. Although this property does not depend on $j$, 
the formulation will appear to be convenient. Similarly, we say that $q$ is {\sl realizable} in $(G,s,t)$ if
there exists such a subset $F$.

For $j\in [k]$ and distinct vertices $s,t\in V(G)$, let $G^+$ denote the graph
$G$ with an additional red edge between $s$ and $t$ of cost $c_j$. 
We define 
%
$$
\OPT{G}{(i,j)}{s}{t} := \max\left.\left\{ \sum_{uv \in F} \redbneck{G^{+}}{F}{u}{v}
\,\right| F\subseteq B(G), F \textrm{ realizes } (i,j)  \textrm{ in } (G,s,t) \right\},
$$
%
if such a subset $F$ exists, and set $\OPT{G}{(i,j)}{s}{t} := -\infty$ otherwise.\medskip 

Intuitively, we want to keep track of optimal acyclic subsets of blue edges for every graph $G$ 
obtained during the construction of a series-parallel graph. The problem is, that the weights of the blue edges in the optimal solution
might change as we compose graphs in the series-parallel decomposition. However, the weights of edges
depend only on the maximum red costs, or {\em bottlenecks}, of the new $st$-paths that will be added to $G$. We can thus 
prepare $\OPT{G}{}{s}{t}$ for every possible set of bottlenecks. These bottlenecks are the values $j$ in what precedes. 

Note that by Lemma~\ref{lem-opt-for-fixed-blue}, if $G$ has
a red spanning tree, then the maximum revenue achievable by the leader on instance $G$  equals
%
$$
\max_{i\in [k]}  \OPT{G}{(i,k)}{s}{t}.
$$
This will be the result returned by the dynamic programming solution.
%

\subsection{Series Compositions}
\label{sec-series}

Let $q=(i,j)$, $q_{1}=(i_{1},j_{1})$, and $q_{2}=(i_{2},j_{2})$, with $q,q_1,q_2\in [k]^2$.
We say that the pair $(q_{1},q_{2})$ is {\sl {\scomp}} with $q$ if
%
\begin{enumerate}[(S1)]
\item \label{cond-series-i} $\max\{i_{1}, i_{2}\} = i$;
\item \label{cond-series-j1} $\max\{j, i_{2}\} = j_{1}$, and
\item $\max\{j, i_{1}\} = j_{2}$,
\end{enumerate}
%
Notice that $(q_{1},q_{2})$ is {\scomp} with $q$ if and only if 
$(q_{2},q_{1})$ is. 

This condition allows us to use the following recursion in our dynamic programming algorithm.
\begin{lemma}
\label{lem-opt-series}
Suppose that
$(G,s,t)$ is a series composition of $(G_{1},s_{1},t_{1})$ and $(G_{2},s_{2},t_{2})$, and that
$q \in [k]^2$ is realizable in $(G,s,t)$. Then
$$
\OPT{G}{q}{s}{t} = \max \left\{ \OPT{G_{1}}{q_{1}}{s_{1}}{t_{1}} + \OPT{G_{2}}{q_{2}}{s_{2}}{t_{2}} \mid (q_1,q_2)\text{\ is\ \scomp\ with\ }q \right\}.
$$
\end{lemma}

We now prove that the recursion is valid. We need the following lemmas. In what follows, 
$(G,s,t)$ is a series composition of $(G_{1},s_{1},t_{1})$ and $(G_{2},s_{2},t_{2})$; 
$q, q_{1}, q_{2} \in [k]^2$ with $q=(i,j)$, $q_{1}=(i_{1},j_{1})$, and $q_{2}=(i_{2},j_{2})$
are such that $(q_{1},q_{2})$ is {\scomp} with $q$;
and $F_{\ell} \subseteq B(G_{\ell})$ realizes $q_{\ell}$ in $(G_{\ell},s,t)$, for $\ell=1,2$.

We first observe that $F := F_{1} \cup F_{2}$ realizes $q$.

\begin{lemma}
\label{lem-series-F}
$F$ realizes $q$  in $(G,s,t)$.
\end{lemma}
%
\begin{proof}
Since $V(G_{1}) \cap V(G_{2}) = \{t_{1}\}$ ($=\{s_{2}\}$),
the set $F$ is clearly acyclic. It remains to show $\bneck{G}{F}{s}{t}=c_{i}$.
Every $st$-path in $\paths{G}{F}{s}{t}$ is the combination of 
an $s_{1}t_{1}$-path  of $\paths{G_{1}}{F_{1}}{s_{1}}{t_{1}}$ with
an $s_{2}t_{2}$-path  of $\paths{G_{2}}{F_{2}}{s_{2}}{t_{2}}$. 
It follows
%
$$
\bneck{G}{F}{s}{t} = \max \left\{ \bneck{G_{1}}{F_{1}}{s_{1}}{t_{1}}, 
\bneck{G_{2}}{F_{2}}{s_{2}}{t_{2}}\right\} 
= \max\{c_{i_{1}},c_{i_{2}}\}
= c_{i},
$$
where the last equality is from~(S\ref{cond-series-i}).
\end{proof}

The proof of the next lemma is illustrated on Figure~\ref{fig-series}. It motivates the definition of series-compatibility.
\begin{lemma}
\label{lem-series-bneck}
Let $G^{+}$ be the graph $G$ augmented with a red edge $st$ of cost $c_j$,
and $G_{\ell}^{+}$ (for $\ell = 1,2$) the graph $G_{\ell}$ augmented with a red edge $s_{\ell}t_{\ell}$ of cost $c_{j_{\ell}}$.
Then for $\ell=1,2$ and every edge $uv \in F_{\ell}$, 
$$
\redbneck{G^{+}}{F}{u}{v} = \redbneck{G_{\ell}^{+}}{F_{\ell}}{u}{v}.
$$
\end{lemma}
%
\begin{proof}
We prove the statement for $\ell = 1$, the case $\ell = 2$ follows by symmetry.
Let $uv \in F_{1}$, and let $e=st$ and $e_{1}=s_{1}t_{1}$ be the
additional red edges in  $G^{+}$ and $G^{+}_{1}$, respectively.

We first show:

\begin{claim}
\label{claim-series-bneck-geq}
$\redbneck{G^{+}}{F}{u}{v} \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$.
\end{claim}
%
\begin{proof}
The claim is true if $\redpaths{G^{+}}{F}{u}{v}=\varnothing$, since then
$\redbneck{G^{+}}{F}{u}{v} = c_{k} \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$. 
Suppose thus $\redpaths{G^{+}}{F}{u}{v} \neq \varnothing$,
and let $P \in \redpaths{G^{+}}{F}{u}{v}$. 
It is enough to show that $\mc(P) \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$.
This clearly holds if $e \notin E(P)$, as $P$ belongs then
also to $\redpaths{G_{1}^{+}}{F_{1}}{u}{v}$ (recall that $|V(G_{1}) \cap V(G_{2})|=1$).
Hence, we may assume $e\in E(P)$. It follows $s_{1},t_{1} \in V(P)$. 

Let $P_{1}$ denote the path 
of $\redpaths{G_{1}^{+}}{F_{1}}{u}{v}$ obtained by replacing 
the subpath $s_{1}Pt_{1}$ of $P$ with the edge $e_{1}$.
Using~(S\ref{cond-series-j1}), we obtain
%
$$
\mc(s_{1}Pt_{1}) = \max\{c_{j}, \mc(t_{2}Pt_{1})\} \geq \max\{c_{j}, c_{i_{2}}\}=c_{j_{1}},
$$
%
implying $\mc(P) \geq \mc(P_{1}) \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$.
\end{proof}

Conversely, we prove: 

\begin{claim}
\label{claim-series-bneck-leq}
$\redbneck{G^{+}}{F}{u}{v} \leq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$. 
\end{claim}
%
\begin{proof}
Again, this trivially holds if $\redpaths{G_{1}^{+}}{F_{1}}{u}{v}$ is empty.
Suppose thus $\redpaths{G_{1}^{+}}{F_{1}}{u}{v} \neq \varnothing$, and
let $P_{1} \in \redpaths{G_{1}^{+}}{F_{1}}{u}{v}$. Similarly as before, it is enough to show
that $\redbneck{G^{+}}{F}{u}{v} \leq \mc(P_{1})$. This is true
if $e_{1} \notin E(P_{1})$, since then $P_{1} \in \redpaths{G^{+}}{F}{u}{v}$.
Assume thus  $e_{1} \in E(P_{1})$. 

If $\paths{G_{2}}{F_{2}}{s_{2}}{t_{2}} = \varnothing$, then $i_{2}=k$ and
$\mc(P_{1}) \geq c_{j_{1}} = \max \{c_{j}, c_{i_{2}}\} = c_{k} \geq \redbneck{G^{+}}{F}{u}{v}$
by~(S\ref{cond-series-j1}).
We may thus assume that $\paths{G_{2}}{F_{2}}{s_{2}}{t_{2}}$   contains a
path $P_{2}$; we choose $P_{2}$ such that $\mc(P_{2}) = c_{i_{2}}$. 

Denote by $P$ the path obtained
from $P_{1}$ by replacing the edge $e_{1}$ with the combination
of edge $e$ and path $P_{2}$. Since $P \in \redpaths{G^{+}}{F}{u}{v}$, 
(S\ref{cond-series-j1}) yields
%
\begin{align*}
\mc(P_{1})  &= \max\left\{ c_{j_{1}}, \mc(P_{1} - e_{1})\right\} \\
&= \max\left\{ c_{j}, c_{i_{2}}, \mc(P_{1} - e_{1})\right\} \\
&= \max\left\{c_{j}, \mc(P_{2}), \mc(P_{1} - e_{1})\right\} \\
&= \mc(P) \\
&\geq \redbneck{G^{+}}{F}{u}{v}.
\end{align*}
\end{proof}

The lemma follows from Claims~\ref{claim-series-bneck-geq} and~\ref{claim-series-bneck-leq}.
\end{proof}

\begin{figure}
\begin{center}
\includegraphics[scale=.3, angle=-90]{series.pdf}
\end{center}
\caption{\label{fig-series}Series composition: illustration of the proof of Lemma~\ref{lem-series-bneck}.}
\end{figure}

We are now ready to prove the correctness of the recursion step in Lemma~\ref{lem-opt-series}.
%
\begin{proof}[Proof of Lemma~\ref{lem-opt-series}]
Let $q$ and $G^{+}$ be defined as before.
We first show:
\begin{claim}
\label{claim-opt-series-exists}
There exist $q_{1}, q_{2}\in [k]^2$ such that $(q_{1},q_{2})$ is {\scomp} with $q$
and $\OPT{G}{q}{s}{t} \leq \OPT{G_{1}}{q_{1}}{s}{t} + \OPT{G_{2}}{q_{2}}{s}{t}$.
\end{claim}
%
\begin{proof}
Let $F\subseteq B(G)$ be a subset of blue edges realizing
$q$ in $(G,s,t)$ such that
%
$$
\OPT{G}{q}{s}{t} = \sum_{uv \in F} \redbneck{G^{+}}{F}{u}{v}.
$$
% 
For $\ell=1,2$, let also $F_{\ell}:=F \cap E(G_{\ell})$ and $q_{\ell} :=(i_{\ell}, j_{\ell})$, with
$i_{\ell}$ the index such that $c_{i_{\ell}} = \bneck{G_{\ell}}{F_{\ell}}{s_{\ell}}{t_{\ell}}$, and $j_{\ell} := \max\{j, i_{\ell+1}\}$ 
(indices are taken modulo 2). 
$F_{\ell}$ ($\ell=1,2$) clearly realizes $q_{\ell}$  in $(G_{\ell},s_{\ell},t_{\ell})$.
It is also easily verified that $(q_{1}, q_{2})$
is {\scomp} with $q$. Hence we can apply Lemma~\ref{lem-series-bneck}:
%
\begin{align*}
\OPT{G}{q}{s}{t} &= \sum_{uv \in F} \redbneck{G^{+}}{F}{u}{v} \\
 &= \sum_{uv \in F_{1}} \redbneck{G^{+}_{1}}{F_{1}}{u}{v} 
+  \sum_{uv \in F_{2}} \redbneck{G^{+}_{2}}{F_{2}}{u}{v} \\
&\leq \OPT{G_{1}}{q_{1}}{s_{1}}{t_{1}} + \OPT{G_{2}}{q_{2}}{s_{2}}{t_{2}},
\end{align*}
%
as claimed.
\end{proof}

We now prove:

\begin{claim}
\label{claim-opt-series-forall}
$\OPT{G}{q}{s}{t} \geq \OPT{G_{1}}{q_{1}}{s_{1}}{t_{1}} + \OPT{G_{2}}{q_{2}}{s_{2}}{t_{2}}$
holds for every $q_{1}, q_{2}\in [k]^2$ such that $(q_{1},q_{2})$ is {\scomp} with $q$.
\end{claim}
%
\begin{proof}
Suppose that $(q_{1},q_{2})$ is {\scomp} with $q$.
Let $F_{\ell}\subseteq B(G_{\ell})$ 
($\ell=1,2$) be a subset of blue edges of $G_{\ell}$ such that
%
$$
\OPT{G_{\ell}}{q_{\ell}}{s_{\ell}}{t_{\ell}} 
= \sum_{uv \in F_{\ell}} \redbneck{G^{+}_{\ell}}{F_{\ell}}{u}{v}.
$$
%
By Lemma~\ref{lem-series-F}, $F:= F_{1} \cup F_{2}$ realizes
$q$ in $(G,s,t)$. Using again Lemma~\ref{lem-series-bneck}, we have:
%
\begin{align*}
\OPT{G}{q}{s}{t} &\geq \sum_{uv \in F} \redbneck{G^{+}}{F}{u}{v} \\
&= \sum_{uv \in F_{1}} \redbneck{G^{+}_{1}}{F_{1}}{u}{v} 
+  \sum_{uv \in F_{2}} \redbneck{G^{+}_{2}}{F_{2}}{u}{v} \\
&= \OPT{G_{1}}{q_{1}}{s_{1}}{t_{1}} + \OPT{G_{2}}{q_{2}}{s_{2}}{t_{2}},
\end{align*}
%
and the claim follows.
\end{proof}

The lemma follows from Claims~\ref{claim-opt-series-exists} and~\ref{claim-opt-series-forall}.
\end{proof}

\subsection{Parallel Compositions}
\label{sec-parallel}

The recursion step for parallel compositions follows a similar scheme.
Let $q,q_1,q_2\in [k]^2$ with $q=(i,j)$, $q_{1}=(i_{1},j_{1})$, and $q_{2}=(i_{2},j_{2})$.
We say that the pair $(q_{1},q_{2})$ is {\sl {\pcomp}} with $q$ if
%
\begin{enumerate}[(P1)]
\item \label{cond-parallel-one-false} at least one of $i_{1},i_{2}$ is non-zero; 
\item \label{cond-parallel-i} $\min\{i_{1}, i_{2}\} = i$;
\item \label{cond-parallel-j1} $\min\{j, i_{2}\} = j_{1}$, and
\item $\min\{j, i_{1}\} = j_{2}$,
\end{enumerate}
%
The recursion step for parallel composition is as follows.

\begin{lemma}
\label{lem-opt-parallel}
Suppose that $(G,s,t)$ is a parallel composition of $(G_{1},s,t)$ and $(G_{2},s,t)$, and that
$q \in [k]^2$ is realizable in $(G,s,t)$. Then
$$
\OPT{G}{q}{s}{t} = \max \{ \OPT{G_{1}}{q_{1}}{s}{t} + \OPT{G_{2}}{q_{2}}{s}{t} \mid  
(q_{1},q_{2})\text{\ is \pcomp\ with\ } q \}.
$$
\end{lemma}

In what follows, $(G,s,t)$ is a parallel composition of $(G_{1},s,t)$ and $(G_{2},s,t)$;
$(q_{1},q_{2})$ is {\pcomp} with $q$; and 
$F_{\ell} \subseteq B(G_{\ell})$ realizes $q_{\ell}$ in $(G_{\ell},s,t)$, for $\ell=1,2$.
Also, $F := F_{1} \cup F_{2}$.

Similarly to Lemma~\ref{lem-series-F}, the definition of parallel-compatibility implies the following lemma.
\begin{lemma}
\label{lem-parallel-F}
$F$ realizes $q$ in $(G,s,t)$.
\end{lemma}
%
\begin{proof}
We have to prove that $F$ is acyclic and that $\bneck{G}{F}{s}{t}=c_{i}$.

First, suppose that $(V(G), F)$ contains a cycle $C$.
Since $F_1$ and $F_{2}$ are both acyclic, $C$ includes the vertices $s$ and $t$, and moreover
$E(G_1) \cap E(C)$, $E(G_2) \cap E(C)$ are both non-empty.
But then, there is an $st$-path in $(V(G), F_{\ell})$ for $\ell=1,2$, 
implying $i_{1}=i_{2}=0$, which contradicts
(P\ref{cond-parallel-one-false}). Hence, $F$ is acyclic. 

Now, since each path of $\paths{G}{F}{s}{t}$ is included in 
either $\paths{G_{1}}{F_{1}}{s}{t}$ or $\paths{G_{2}}{F_{2}}{s}{t}$,
it follows $\bneck{G}{F}{s}{t} = 
\min\{ \bneck{G_{1}}{F_{1}}{s}{t}, \bneck{G_{2}}{F_{2}}{s}{t}\} = \min\{c_{i_{1}},c_{i_{2}}\}$,
which equals $c_{i}$ by (P\ref{cond-parallel-i}).
\end{proof}

The next lemma is the analogue of Lemma~\ref{lem-series-bneck} for parallel compositions.
\begin{lemma}
\label{lem-parallel-bneck}
Let $G^{+}$ be the graph $G$ augmented with a red edge $st$ of cost $c_j$,
and let $G_{\ell}^{+}$ (for $\ell = 1,2$) be the graph $G_{\ell}$ augmented with a red edge $s_{\ell}t_{\ell}$ of cost $c_{j_{\ell}}$.
Then for $\ell=1,2$ and every edge $uv \in F_{\ell}$, 
$$
\redbneck{G^{+}}{F}{u}{v} = \redbneck{G_{\ell}^{+}}{F_{\ell}}{u}{v}.
$$
\end{lemma}
%
\begin{proof}
We prove the statement for $\ell=1$, the case $\ell=2$ follows by symmetry.
Let $e=st$ and $e_{1}=s_{1}t_{1}$ be the additional red edges in $G^{+}$ and $G^{+}_{1}$, respectively.

Let $uv \in F_{1}$.
Observe  that $\redpaths{G^{+}}{F}{u}{v}$ is empty if and only if
$\redpaths{G_{1}^{+}}{F_{1}}{u}{v}$ is. If both are empty, then 
$\redbneck{G^{+}}{F}{x}{y} = \redbneck{G_{1}^{+}}{F_{1}}{u}{v}=c_{k}$, and the claim holds.
Hence, we may assume 
$\redpaths{G^{+}}{F}{u}{v} \neq \varnothing$ and  $\redpaths{G_{1}^{+}}{F_{1}}{u}{v} \neq \varnothing$.

We first show:

\begin{claim}
\label{claim-par-leq}
$\redbneck{G^{+}}{F}{u}{v} \leq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$.
\end{claim}
%
\begin{proof}
Let $P_{1} \in \redpaths{G_{1}^{+}}{F_{1}}{u}{v}$.
It is enough to show $\redbneck{G^{+}}{F}{u}{v} \leq \mc(P_{1})$.
If $e_{1} \notin E(P_{1})$, then $P_{1} \in \redpaths{G^{+}}{F}{u}{v}$, and 
$\redbneck{G^{+}}{F}{u}{v} \leq \mc(P_{1})$ holds by definition. Hence we may assume 
$e_{1} \in E(P_{1})$. 

By (P\ref{cond-parallel-j1}), we have $j_{1}=\min\{j,i_{2}\}$. If $j_{1}=j$, then replacing
the edge $e_{1}$ of $P_{1}$ by $e$ yields 
a path $P \in \redpaths{G^{+}}{F}{u}{v}$ with $\mc(P) = \mc(P_{1})$,
implying $\redbneck{G^{+}}{F}{u}{v} \leq \mc(P_{1})$. Similarly, if $j_{1}=i_{2} < j$, then
$i_{2} < k$, implying that $\paths{G_{2}}{F_{2}}{s}{t}$ is not empty. 
Replacing in $P_{1}$ the edge $e$ with any path 
$P_{2} \in \paths{G_{2}}{F_{2}}{s}{t}$ 
with  $\mc(P_{2})=c_{i_{2}}$ gives again a
path $P$ with $\mc(P) = \mc(P_{1})$. 
While the path $P_{2}$ does not necessarily contain a red edge,
the path $P$, on the other hand, cannot be completely blue. This is 
because otherwise $F$ contains the
cycle $P \cup \{uv\}$, contradicting the fact that $F$ is acyclic (as follows 
from Lemma~\ref{lem-parallel-F}). Hence, 
$P\in \redpaths{G^{+}}{F}{u}{v}$, and
$\redbneck{G^{+}}{F}{u}{v} \leq \mc(P) = \mc(P_{1})$.
Claim~\ref{claim-par-leq} follows.
\end{proof}

Conversely, we prove:

\begin{claim}
\label{claim-par-geq}
$\redbneck{G^{+}}{F}{u}{v} \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$.
\end{claim}
%
\begin{proof}
Let $P \in \redpaths{G^{+}}{F}{u}{v}$. Again, it is enough to
show $\mc(P) \geq \redbneck{G_{1}^{+}}{F_{1}}{u}{v}$. 
This clearly holds if $P \in \redpaths{G^{+}_{1}}{F_{1}}{u}{v}$. 
Hence, we may assume $s,t \in V(P)$, and that the subpath $sPt$ of $P$ either
belongs to $\paths{G_{2}}{F_{2}}{s}{t}$, or corresponds to the edge $e$.

In the first case, $c_{i_{2}} \leq \mc(sPt)$ holds by definition.
Moreover, $j_{1} \leq i_{2}$ follows from (P\ref{cond-parallel-j1}). Therefore, replacing
the subpath $sPt$ of $P$ with the edge $e_{1}$ yields 
a path $P_{1}\in \redpaths{G_{1}^{+}}{F_{1}}{u}{v}$
with $\mc(P_{1}) \leq \mc(P)$, implying $\redbneck{G_{1}^{+}}{F_{1}}{u}{v} \leq \mc(P)$.

Similarly, (P\ref{cond-parallel-j1}) implies $j_{1} \leq j$ in the second case.
Hence, replacing the edge $e$ of $P$ with $e_{1}$ results in   
a path $P_{1}\in \redpaths{G_{1}^{+}}{F_{1}}{u}{v}$ with
$\mc(P_{1}) \leq \mc(P)$, showing $\redbneck{G_{1}^{+}}{F_{1}}{u}{v} \leq \mc(P)$. This completes
the proof of Claim~\ref{claim-par-geq}.
\end{proof}

Lemma~\ref{lem-parallel-bneck} follows from Claims~\ref{claim-par-leq} and~\ref{claim-par-geq}.
\end{proof}

Using the two previous lemmas, the proof of Lemma~\ref{lem-opt-parallel} is
the same as that of Lemma~\ref{lem-opt-series} for series composition. We omit it.

\subsection{The Algorithm}
\label{sec-algo}

A series-parallel decomposition of a connected 
series-parallel graph can be computed in linear time~\cite{VTL82}.
Given such a decomposition, Lemmas~\ref{lem-opt-series} and~\ref{lem-opt-parallel}
yield the following algorithm: consider each graph $(H,s,t)$ in the decomposition 
tree in a bottom-up fashion. If $H$ is a single edge, compute $\OPT{H}{q}{s}{t}$
for every $q\in [k]^2$. If $(H,s,t)$ is a series or parallel composition of 
$(H_{1},s_{1},t_{1})$ and $(H_{2},s_{2},t_{2})$, 
compute $\OPT{H}{q}{s}{t}$ for every $q\in [k]^2$ based on the 
previously computed values for $(H_{1},s_{1},t_{1})$ and $(H_{2},s_{2},t_{2})$,
relying on Lemmas~\ref{lem-opt-series} and~\ref{lem-opt-parallel}.

For every $q=(i,j)\in[k]^2$, there are $O(k)$ possible values for either series-compatible
or parallel-compatible pairs $(q_1,q_2)$. Hence every step costs $O(k)$ times. Since
there are $O(k^2)$ possible values for $q$, and $O(m)$ graphs in the decomposition of $G$,
the overall complexity is $O(k^3m) = O(m^4)$.

This results in a polynomial-time algorithm computing the maximum revenue
achievable by the leader. Moreover, using Lemmas~\ref{lem-series-F} and~\ref{lem-parallel-F},
it is not difficult to keep track at each step of a witness $F \subseteq B(H)$ for
$\OPT{H}{q}{s}{t}$, whenever $\OPT{H}{q}{s}{t} > -\infty$. 
This proves Theorem~\ref{th-sp}.

\section{Bounded-Treewidth Graphs}
\label{Bounded-Treewidth Graphs}

%A \emph{tree decomposition}~\cite{RobertsonSeymour1986} of a graph $G=(V,E)$ is a pair
%$(\mathcal{X},\mathcal{T})$, where $\mathcal{X}$ is a family of
%subsets of $V$, and $\mathcal{T}$ is a tree over $\mathcal{X}$,
%satisfying the following conditions:
%\begin{enumerate}
%\item $\bigcup_{X\in \mathcal{X}}X=V$
%\item $\forall (u,v) \in E : \{u,v\} \subseteq X$ for some $X \in
%\mathcal{X}$,
%\item $\forall v \in V : \{X \in \mathcal{X} \,|\, v \in V(X) \}$ is
%connected in $\mathcal{T}$.
%\end{enumerate}
%The \emph{width} of $\mathcal{T}$ is $\max_{X \in
%\mathcal{X}}|X|-1$, and the \emph{treewidth} of $G$ is the minimum
%width over all tree decompositions of $G$. Thus, a tree has treewidth 1, and series-parallel graphs have treewidth 2.

In the previous section, we gave a polynomial-time algorithm for solving the
{\stackmst} problem on series-parallel graphs, which are biconnected graphs of
treewidth~$2$.  In this section, we show how to extend the algorithm to any
graph of bounded treewidth, as indicated by the following theorem.

\begin{theorem}
\label{th-tw}
The {\stackmst} problem can be solved in $m^{O(\omega^2)}$ 
time on graphs of treewidth $\omega$.
\end{theorem}


The {\em treewidth} of a graph can be defined in several ways. We follow Abrahamson and Fellows~\cite{AbrahamsonFellows1995} and characterize a graph of treewidth $\omega$ as an \emph{$\omega$-boundaried graph}. An $\omega$-boundaried graph is a graph with $\omega$
distinguished vertices (called \emph{boundary vertices}), each uniquely labeled by a label in
$\{1,\dots,\omega\}$. $\omega$-boundaried graphs are formed recursively by the following composition operators:
\begin{enumerate}
\item The null operator $\varnothing$ creates a boundaried graph
which has only boundary vertices, and they are all isolated.
\item The binary operator $\oplus$ takes the disjoint union
of two $\omega$-boundaried graphs by identifying the $i$th
boundary vertex of the first graph with the $i$th boundary vertex of
the second graph. If there are only two boundary vertices $s$ and $t$ then this is exactly a parallel-composition.
\item The unary operator $\eta$ introduces a new isolated vertex and makes
this the new vertex with label 1 in the boundary. The previous
vertex that was labeled 1 is removed from the boundary but not from
the graph.
\item The unary operator $\epsilon$ adds an edge between the vertices labeled
1 and 2 in the boundary.
\item Unary operators that permute the labels of the boundary vertices.
\end{enumerate}

Any $\omega$-boundaried graph (and hence any graph of treewidth $\omega$) can be constructed by applying
$O(\omega n)$ compositions according to the above five operators. This construction as well as the boundary vertices can be found in linear time~\cite{Bodlaender1996}.

\subsection{Definitions}
Given an $\omega$-boundaried graph $G=(V,E)$ and two distinct boundary vertices $a,b \in \{1,2,\ldots,\omega\}$, we call an $ab$-path \emph{internal} if the only boundary vertices it passes through are $a$ and $b$. We slightly modify the definition of $\paths{G}{F}{a}{b}$,  
$\redpaths{G}{F}{a}{b}, \bneck{G}{F}{a}{b},$ and $\redbneck{G}{F}{a}{b}$ from the previous section to only include internal $ab$-paths. 

As in the series-parallel case, we want to keep track of optimal acyclic subsets of blue edges for every graph $G$ 
obtained during the construction of a bounded-treewidth graph. Notice that the weights of edges in an optimal solution depend only on the bottlenecks of the new internal paths that will be added to $G$. We thus prepare $OPT(G)$s for every possible set of bottlenecks (the $j_{ab}$s in what follows) between any two boundary vertices $a$ and $b$.

Let $I_{\omega \times \omega}$ be a matrix of pairs where $I[a,b]=I[b,a]=(i_{ab},j_{ab})$ for some $i_{ab},j_{ab}\in \{0,1,\ldots,k\}$.
Let $OPT_{I}(G)$ be the optimal solution to \stackmst\ (that is, an acyclic subset of blue edges $F$) on the graph
$G^+$ obtained from $G$ by adding a red edge connecting $a$ and $b$ of cost $c_{j_{ab}}$ for every pair of distinct boundary vertices 
$a,b\in \{1,2,\ldots,\omega\}$, subject to the conditions that for every distinct $a,b\in \{1,2,\ldots,\omega\}$ we have $ \bneck{G}{F}{a}{b}=c_{i_{ab}}$.


During the construction, we store for every graph $G$ the partial solutions $OPT_{I}(G)$ for every possible $I$.
In cases where $OPT_{I}(G)$ is undefined (no proper $F$ exists), we set $OPT_{I}(G)=-\infty$. Also, we abuse the notation $OPT_{I}(G)$ for denoting both the acyclic subset $F$ and its revenue.


\subsection{The Algorithm.}
We now describe our bounded-treewidth algorithm by showing how to maintain the $OPT_I$ information as $G$ is constructed by the five operators. We present the algorithm along with a proof sketch of its correction.
We use $(i_{ab},j_{ab})$ to denote $I$'s pairs, $(i^1_{ab},j^1_{ab})$ for $I_1$'s pairs, $(i^2_{ab},j^2_{ab})$ for $I_2$'s pairs, and $(i'_{ab},j'_{ab})$ for $I'$'s pairs.

We begin with the null operator $\varnothing$ that creates a new graph $G$ with isolated vertices labeled $1,\ldots,\omega$. 
Therefore, we set $OPT_{I}(G)=0$ (associated with $F=\varnothing$) for every $I$ whose entries are all of the form $(k,j_{ab})$. The value $i_{ab}$ is required to be $k$ as there are no internal paths at all; the $j_{ab}$s can be arbitrary values in $\{0,1,\ldots,k\}$. For all other $I$s we set $OPT_{I}(G)=-\infty$.


If $G=G_1\oplus G_2$, then $OPT_{I}(G)= \max\{OPT_{I_1}(G) \cup OPT_{I_2}(G)\}$. This operator is a lot like a parallel-composition of series-parallel graphs. Indeed, in the following conditions on the compatibility of $I,I_1,I_2,$ the first four conditions are exactly the same as in a parallel-composition, only they must hold for every pair of boundary vertices (whereas in the series-parallel case there was only one pair). The fifth condition makes sure that the blue edges that will be purchased do not form a cycle.
Therefore, if $G=G_1\oplus G_2$, we require that
\begin{enumerate}
  \item at least one of $i^1_{ab},i^2_{ab}$ is non-zero,
  \item $i_{ab}=\min\{i^1_{ab},i^2_{ab}\}$, 
  \item $j^1_{ab} = \min\{j_{ab},i^2_{ab}\}$, 
  \item $j^2_{ab} = \min\{j_{ab},i^1_{ab}\}$, 
\end{enumerate}
%
for every distinct $a,b\in \{1,\ldots,\omega\}$, and moreover that
%
\begin{enumerate}
\item[5.] the graph $H$ is acyclic, where $V(H) = \{1,\ldots,\omega\}$ and distinct $a,b \in V(H)$ are adjacent in $H$
if $i_{ab}=0$.  %had to split because a,b here not the same as a,b above
\end{enumerate}
\noindent 

 If $G=\eta(G')$, then a new isolated boundary vertex $v$ with label 1 is created, and the old 1-labeled vertex $u$ is now no longer a boundary vertex. Since no edges are modified, the optimal solutions for $G'$ and $G$ are the same and we set $OPT_{I}(G)= OPT_{I'}(G')$. Notice that an $ab$-path between two distinct boundary vertices $a, b \ne u$ that go through $u$ 
is not an {\em internal} path in $G'$, but could be in $G$ (if the path does not contain any other boundary vertex). 
This fact is captured by the first two of the following four conditions. If $G=\eta(G')$
we require that, for every distinct $a,b\in \{2,\ldots,\omega\}$,
\begin{enumerate}
\item $i_{ab}=\min \big \{i'_{ab},\max\{i'_{a1},i'_{1b}\}\big\}$, 
\item $j'_{ab}=\min \big \{j_{ab},\max\{j_{a1},j_{1b}\}\big\}$,
\item $i_{a1}=k$, (there is no internal path incident to $v$ as it is isolated)
\item $j'_{a1}=k$. (there will be no new internal paths originating from $u$)
\end{enumerate}


If $G=\epsilon(G')$, then $G$ is obtained from $G'$ by adding an edge $e$ between vertices labeled $1$ and $2$. 
Notice that $\epsilon(G')=G'\oplus G''$ where $G''$ is the boundaried graph which has only boundary vertices, and its only edge is $e$. Thus, instead of dealing with the $\epsilon$ operator we can introduce two new null-like operators that create a graph $G$ isomorphic to $G''$
with the edge $e$ being red and blue, respectively.
    \begin{itemize}
      \item If $e$ is red with cost $c(e)$ then we set $OPT_{I}(G)=0$ (associated with $F=\varnothing$) for every $I$ whose entries are all of the form  $(k,j_{ab})$ (the $j_{ab}$s can be anything in $\{0,1,\ldots,k\}$) except that $i_{12}=c(e)$.  For all other $I$s we set $OPT_{I}(G)=-\infty$.
     
      \item If $e$ is blue then we set $OPT_{I}(G)=0$ (associated with $F=\varnothing$) for every $I$ whose entries are all of the form  $(k,j_{ab})$ (the $j_{ab}$s can be anything in $\{0,1,\ldots,k\}$). 
      
      In addition, we set $OPT_{I}(G)= p(e)$  for every $I$ whose entries are all of the form  $(k,j_{ab})$ except that $i_{12}=0$. 
This corresponds to setting $F=\{e\}$. For such a $I$, the price $p(e)$ assigned to $e$ is determined as follows.
%Recall that $e$'s price is determined according to all cycles that include $e$ (i.e, all paths between $1$ and $2$).
Let $P_{12}$ be the set of all ordered sequences of the form $a_1$-$a_2$-$\ldots$-$a_t$ where every $a_i\in \{1,2,\ldots,\omega\}$ is a unique boundary vertex, $a_1=1$, $a_t=2$, and $2\le t \le \omega$ (if $t=2$ then the path is simply $1$-$2$). Every such sequence, together with $e$ could close a cycle when new internal paths will be added. 
We therefore set
    $$p(e)=\min_{a_1\text{-}\ldots\text{-}a_t \in P_{12}} \max_{2\le i\le t}  j_{a_{i-1}a_i} $$
    For all other $I$s we set $OPT_{I}(G)=-\infty$.
    \end{itemize}

Unary operators that permute the labels of the boundary vertices are trivial to handle. They merely represent a permutation of $I$.

\paragraph{Time Complexity.}
The composition operators require us to check every combination of at most three different $I$s for compatibility.    
There are $k^{\omega^2}$ possible $I$s, so we need to check $O(k^{3\omega^2})$ combinations. Each check requires at least $O(\omega^2)$ time to read the $I$s. 

The most time-consuming check is the one of the $\epsilon$ operator when it adds a blue edge $e$. This might require figuring out $p(e)$. 
Notice that $|P_{12}| < \omega!$, so we can perform the check in $O(\omega!)$ time. 
The total complexity of the above algorithm is therefore bounded by
$O(k^{3 \omega^2}\cdot\omega!)=m^{O(\omega^2)}$.\bigskip

Although the problem is polynomial for every constant value of $\omega$, it is unclear whether there exists a fixed-parameter algorithm
of complexity $O(f(\omega) n^c)$ for an arbitrary (possibly large) function $f$ of $\omega$ and a constant $c$.
In fact, we conjecture that under reasonable complexity-theoretic assumptions, such an algorithm does not exist. 

\small
\bibliographystyle{alpha}
\bibliography{planarStackMST}


\end{document} 





planarStackMST.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{GvLSU09}

\bibitem[AF93]{AbrahamsonFellows1995}
K.~R. Abrahamson and M.~R. Fellows.
\newblock Finite automata, bounded treewidth, and well-quasiordering.
\newblock In {\em Graph Structure Theory (ed. N. Robertson and P. Seymour)},
  pages 539--564, 1993.

\bibitem[Bak94]{Baker94}
B.~S. Baker.
\newblock Approximation algorithms for {NP}-complete problems on planar graphs.
\newblock {\em J. ACM}, 41(1):153--180, 1994.

\bibitem[BGPW08]{BGPW08}
D.~Bil{\`o}, L.~Gual{\`a}, G.~Proietti, and P.~Widmayer.
\newblock Computational aspects of a 2-player {S}tackelberg shortest paths tree
  game.
\newblock In {\em Proc. 4th Workshop on Internet and Network Economics
  ({WINE})}, volume 5385 of {\em Lecture Notes in Computer Science}, pages
  251--262. Springer-Verlag, 2008.

\bibitem[BHK08]{BHK08}
P.~Briest, M.~Hoefer, and P.~Krysta.
\newblock Stackelberg network pricing games.
\newblock In {\em Proc. 25th International Symposium on Theoretical Aspects of
  Computer Science ({STACS})}, pages 133--142, 2008.

\bibitem[BKMK07]{BKK07}
Glencora Borradaile, Claire Kenyon-Mathieu, and Philip~N. Klein.
\newblock A polynomial-time approximation scheme for {S}teiner tree in planar
  graphs.
\newblock In {\em Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms},
  2007.

\bibitem[Bod96]{Bodlaender1996}
H.~L. Bodlaender.
\newblock A linear time algorithm for finding tree-decompositions of small
  treewidth.
\newblock {\em SIAM J. Comput.}, 25:1305--1317, 1996.

\bibitem[CDF{\etalchar{+}}07]{CDFJLNW-sub}
J.~Cardinal, E.~D. Demaine, S.~Fiorini, G.~Joret, S.~Langerman, I.~Newman, and
  O.~Weimann.
\newblock The {S}tackelberg minimum spanning tree game.
\newblock In {\em Proc. 10th international Workshop on Algorithms and Data
  Structures (WADS)}, volume 4619 of {\em Lecture Notes in Computer Science},
  pages 64--76. Springer-Verlag, 2007.
\newblock To appear in Algorithmica.

\bibitem[Cou08]{C08}
B.~Courcelle.
\newblock Graph structure and monadic second-order logic: Language theoretical
  aspects.
\newblock In {\em Proc. International Conference on Automata, Languages, and
  Programming ({ICALP})}, volume 5125 of {\em Lecture Notes in Computer
  Science}, pages 1--13. Springer-Verlag, 2008.

\bibitem[DHK09]{DHK09}
Erik~D. Demaine, MohammadTaghi Hajiaghayi, and {Ken-ichi} Kawarabayashi.
\newblock Approximation algorithms via structural results for apex-minor-free
  graphs.
\newblock In {\em Proc. 36th International Colloquium on Automata, Languages
  and Programming (ICALP)}, 2009.

\bibitem[DHM07]{DHM07}
E.~D. Demaine, M.~Hajiaghayi, and B.~Mohar.
\newblock Approximation algorithms via contraction decomposition.
\newblock In {\em Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms
  ({SODA})}, pages 278--287, 2007.

\bibitem[GJ79]{GJ}
M.~R. Garey and D.~S. Johnson.
\newblock {\em Computers and Intractability, A Guide to the Theory of
  {NP}-Completeness}.
\newblock W.H. Freeman and Company, New York, 1979.

\bibitem[GvLSU09]{GLSU09-journal}
A.~Grigoriev, J.~van Loon, R.~Sitters, and M.~Uetz.
\newblock Optimal pricing of capacitated networks.
\newblock {\em Networks}, 53(1):79--87, 2009.

\bibitem[Kle05]{Klein05}
Philip~N. Klein.
\newblock A linear-time approximation scheme for {TSP} for planar weighted
  graphs.
\newblock In {\em Proc. 46th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 146--155, 2005.

\bibitem[Kle06]{Klein06}
Philip~N. Klein.
\newblock A subset spanner for planar graphs, with application to subset {TSP}.
\newblock In {\em Proc. 38th ACM Symposium on Theory of Computing (STOC)},
  pages 749--756, 2006.

\bibitem[LMS98]{LMS98}
M.~Labb\'e, P.~Marcotte, and G.~Savard.
\newblock A bilevel model of taxation and its application to optimal highway
  pricing.
\newblock {\em Management Science}, 44(12):1608--1622, 1998.

\bibitem[RSM05]{RSM05}
S.~Roch, G.~Savard, and P.~Marcotte.
\newblock An approximation algorithm for {S}tackelberg network pricing.
\newblock {\em Networks}, 46(1):57--67, 2005.

\bibitem[vH06]{vH06}
S.~van Hoesel.
\newblock An overview of {S}tackelberg pricing in networks.
\newblock Research Memoranda 042, Maastricht : METEOR, Maastricht Research
  School of Economics of Technology and Organization, 2006.

\bibitem[vS34]{Stack34}
H.~von Stackelberg.
\newblock {\em Marktform und Gleichgewicht (Market and Equilibrium)}.
\newblock Verlag von Julius Springer, Vienna, 1934.

\bibitem[VTL82]{VTL82}
J.~Valdes, R.~E. Tarjan, and E.~L. Lawler.
\newblock The recognition of series parallel digraphs.
\newblock {\em SIAM J. Comput.}, 11(2):298--313, 1982.

\end{thebibliography}
