%% LyX 1.5.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[runningheads,a4paper]{llncs}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Bold symbol macro for standard LaTeX users
\providecommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}

\setlength{\parskip}{\medskipamount} 
\setlength{\parindent}{0pt} 
\usepackage{float}


\def\l{\ell}
\def\la{\lambda}
\def\eps{\varepsilon}

\usepackage{rotating}

\floatstyle{ruled} 
\newfloat{algorithm}{tbp}{loa} 
\floatname{algorithm}{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{theorem}


%\theorembodyfont{\rmfamily} 
%\newtheorem{rem}{Remark} 
%\theorembodyfont{} 
%\newtheorem{theorem}{Theorem} 
%\newtheorem{lemma}{Lemma} 
%\newtheorem{corollary}{Corollary} 
%\newtheorem{defi}{Definition} 
\usepackage{pst-all}


%\usepackage[usenames,dvipsnames]{pstricks} 
\usepackage{epsfig}

\usepackage{pst-grad}
 
% For gradients 
\usepackage{pst-plot}
 
% For axes
\def\eps{\varepsilon}

 
%\usepackage{babel}
\makeatother



\begin{document}
\title{Determining a Minimum Spanning Tree \\with Disjunctive Constraints}

\author{Andreas Darmann\inst{1}, Ulrich Pferschy\inst{2} \and Joachim Schauer\inst{2}}
\institute{University of Graz, Institute of Public Economics, Universitaetsstr.~15, 8010 Graz, Austria,\\
\email{andreas.darmann@uni-graz.at}
\and
University of Graz, Department of Statistics and Operations Research Universitaetsstr.~15, 8010 Graz, Austria,
\email{\{joachim.schauer,pferschy\}@uni-graz.at}}
\maketitle



\begin{abstract}
\noindent
For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges 
which can not be both included in the spanning tree at the same time.
These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph.
Edges in the conflict graph connect conflicting edges of the original graph.
It is shown that the problem becomes strongly $\mathcal{NP}$-hard even if the connected components of the conflict graph consist only
of paths of length two.
On the other hand, for conflict graphs consisting of disjoint edges (i.e.\ paths of length one) the problem remains
polynomially solvable.

\vspace*{1ex}
\noindent
\textbf{Key words: minimum spanning tree, conflict graph.} 
\end{abstract}

\section{Introduction}


The minimum spanning tree problem (MST) is a classical problem in combinatorial optimization.
It has been extensively studied within its original framework as well as in connection with 
fields as social choice theory, in particular with aspects of fair division.
The issue of fairly assigning the costs of a minimum spanning tree to individuals
(represented by nodes) has first been raised by Bird~\cite{bird}, recent works often consider characterizations of 
fair division rules (e.g.,\ Bogomolnaia and Moulin~\cite{moulin}, Dutta and Kar~\cite{dutta}
and Kar~\cite{kar}). Another approach to fairness in connection with spanning trees, based on preference relations
on the edges instead of monetary costs, has been considered in Darmann, Klamler and Pferschy~\cite{Darmann}.\\
This paper however deals with a different aspect of the link to social choice theory:
the minimum spanning tree problem with conflict graph (MSTCG) addresses the question
of finding a minimum spanning tree in a weighted, undirected graph, given there are 
incompatibilities for certain pairs of edges. The incompatibilities mean
that from each such conflicting pair of edges at most one edge can occur in
the spanning tree.

A practical example could be the installation of an oil pipeline system connecting various countries. Each country needs to be connected to the pipeline system,
but there are many ways to hook them up. Such a situation can be represented by means of a weighted undirected graph: the nodes are the countries, the edges 
are the possible links between the countries and the edge weights are the costs of the respective link between the countries. 
The cheapest way to install the system corresponds to a minimum spanning tree in the graph.
However, for technical or political reasons many different firms can be required to install the system, and we assume that each link can 
be constructed by exactly one firm. 
Now certain conflicts may arise. A reason might be, that some firms are not willing to cooperate with each other, and thus certain links (edges) cannot
both be contained in a solution. The MSTCG asks for the cheapest way to install the pipeline system subject to these conflicts.  

It is natural to represent such symmetric conflict
relations by means of an undirected {\em conflict graph}, %$\bar{G}=(E,\bar{E})$, 
where every vertex of the conflict graph corresponds uniquely to an
edge in the original graph and an edge in the conflict graph implies
that the two adjacent vertices, i.e.\ edges in the original graph,
cannot occur together in an MST solution.

For a formal definition of the \textit{minimum spanning tree problem
with conflict graph}, let $G=(V,E)$ be an undirected connected
graph with $n$ vertices and $m$ edges, where each edge $e$ has
associated a weight $w(e)$ ($w$ is a weight function $w:E\rightarrow\mathbb{R}$).
Furthermore, an undirected graph $\bar{G}=(E,\bar{E})$ represents
a conflict graph where each of the $m$ vertices corresponds uniquely
to an edge $e\in E$ of $G$. An edge $\bar{e}=(i,j)\in\bar{E}$ implies
that the two vertices incident to $\bar{e}$ -- that is, the two edges
$i,j\in E$ -- cannot occur together in a spanning tree of $G$. 
In contrast to $G$, $\bar{G}$ is not necessarily connected and may
contain isolated vertices (i.e.\ edges of $G$ which can be combined
with every other edge in the minimum spanning tree solution). MSTCG
asks for a minimum spanning tree $T$ in $G$, given that adjacent
vertices in $\bar{G}$ are not both together included in $T$.

\smallskip{}
 For a set of vertices $F\subseteq V$ in $G$ let $E(F)$ be the
set of edges in $G$ that have both of its endpoints in $F$. Then
MSTCG can be stated by the following integer linear programming (ILP) formulation: \begin{eqnarray}
(MSTCG)\quad & \min & \sum_{e\in E}w(e)*x_{e}\label{eqn:ILP}\\
 & \mbox{s.t.} & \sum_{e\in E}x_{e}=n-1\label{eqn:card}\\
 &  & \sum_{e\in E(F)}x_{e}\leq|F|-1\quad\forall\,\emptyset\not=F\subseteq V\label{eqn:subtour}\\
 &  & x_{e}+x_{f}\leq1\quad\forall\,(e,f)\in\bar{E}\label{eq:conflict}\\
 &  & x_{e}\in\{0,1\}\quad\forall\, e\in E\label{eqn:integer}\end{eqnarray}\\

 Obviously, (\ref{eqn:ILP})--(\ref{eqn:subtour}) and (\ref{eqn:integer}) is a classical
ILP-model for MST (e.g.\, see~\cite{Ahuja}):
\begin{itemize} 
 \item the constraint (\ref{eqn:card}) ensures that $n-1$ edges are chosen,
\item the constraint (\ref{eqn:subtour}) implies that the chosen edges do not form a cycle and
\item the constraint (\ref{eqn:integer}) states that $x_{e}$ is a binary variable, indicating whether or not edge $e$ is being contained in the spanning tree.
\end{itemize}
The remaining constraint (\ref{eq:conflict}) adds the conflict relations represented by the conflict graph. It is worth noting that,
in contrast to the classical minimum spanning tree problem, due to this conflict constraint there might be no 
feasible solution for MSTCG even if the graph $G$ is connected. 

\bigskip{}
 In this paper we will characterize the complexity of MSTCG and identify
the graph classes for the conflict graph $\bar{G}$ where the problem
changes from polynomially solvable to strongly $\mathcal{NP}$-hard.\footnote{A problem 
is said to be strongly $\mathcal{NP}$-hard if it is $\mathcal{NP}$-hard even when its numerical 
parameters are bounded by a polynomial in the length of the input, i.e.\ the number of input values.}
These are graphs whose connected components are edges resp.\ paths
of length two (we define the length of a path as the number of edges
in the path). For obvious illustrative reasons we introduce the following
terminology.

\begin{definition}A $2$-ladder is an undirected graph whose components
are paths of length one, i.e.\ edges connecting pairs of vertices.
\end{definition}

\begin{definition}A $3$-ladder is an undirected graph whose components
are paths of length two.\end{definition}

\smallskip{}
It will be shown in Section~\ref{sec:hard} that MSTCG is already strongly $\mathcal{NP}$-hard
if the underlying conflict graph is a $3$-ladder. In particular we show that, given that the conflict graph is a $3$-ladder, 
MSTCG is $\mathcal{NP}$-hard even when the edge weights are restricted to $\{0,1\}$.  
On the other hand, it can be shown by a matroid intersection argument in Section~\ref{sec:poly} that the problem
remains polynomially solvable for a $2$-ladder as a conflict graph.

In contrast to the latter result, it should be noted that the shortest
path problem with pairwise disjoint forbidden pairs of edges (i.e.\ with
a $2$-ladder conflict graph) is known to be strongly $\mathcal{NP}$-hard~\cite{gj79}.
Results of the same flavour were recently derived for the classical
0-1 knapsack problem with conflict graphs. 
While this problem is strongly $\mathcal{NP}$-hard for arbitrary conflict graphs, 
it was shown in~\cite{pfsch08} that pseudopolynomial algorithms (and hence
also fully polynomial approximation schemes) exist if the given conflict
graph is a tree, a graph of bounded treewidth or a chordal graph.
Bin packing problems with special classes of conflict graphs were considered
from an approximation point of view by~\cite{jaoe97}
and~\cite{jan99}.
Complexity results for different classes of conflict graphs for a scheduling problem
under makespan minimization are given in~\cite{boja95}.
Further references on combinatorial optimization problems with conflict
graphs can be found in~\cite{pfsch08}.


\section{A strongly $\mathcal{NP}$-hardness result for MSTCG}
\label{sec:hard}

In this section we show that MSTCG is already strongly $\mathcal{NP}$-hard
if the conflict graph $\bar{G}$ is a $3$-ladder. E.g.\ for $e_{1},e_{2},e_{3}\in E$
let a component of $\bar{G}$ be made up of the path $(e_{1},e_{2},e_{3})$.
Then, in terms of the underlying graph $G$, a feasible spanning tree
for MSTCG that contains $e_{2}$ must include neither edge $e_{1}$
nor edge $e_{3}$. However, a feasible tree that contains $e_{1}$
must not contain $e_{2}$, but it may contain $e_{3}$.


\subsection{The idea of the reduction}

We reduce an $\mathcal{NP}$-complete subproblem of 3-SAT on the decision
problem corresponding to MSTCG with a $3$-ladder as conflict graph.
\\
 Let $I$ be an arbitrary instance of 3-SAT with $k$ clauses $C_{1},\ldots,C_{k}$
and $n$ variables $x_{1},\ldots,x_{n}$, such that each literal $x_{i}$
occurs in $\l_{i}$ clauses and its negation $\bar{x}_{i}$ occurs
in $\bar{\l}_{i}$ clauses. We restrict ourselves to instances with
$\l_{i}+\bar{\l}_{i}\leq5$. The decision problem whether or not there
exists a satisfying truth assignment for $I$ is $\mathcal{NP}$-complete~\cite{gj79}.
Considering this decision problem, we construct an instance $I'$ of MSTCG
by defining a graph $G_{3-SAT}$ and a conflict graph $\bar{G}_{3-SAT}$
as described in Subsection~\ref{sub:G_{3-SAT} and quer}.\\
It should be emphasized that in the graph $G_{3-SAT}$ some nodes represent the clauses in $I$, whereas some edges
represent the literals occuring in $I$. 

However, the reduction of the above subproblem of 3-SAT to MSTCG is then performed in two steps (it is presented in full detail in Subsection~\ref{reduction}).
Given that $I$ is a ``YES''-instance of $I$, we construct an optimal solution $T$ with weight $k$ of the instance $I'$ of MSTCG from a satisfying truth assignment
for $I$. This is basically done by first choosing those edges to be in $T$ that represent literals set ``TRUE'' under the truth assignment.  
The rest of the tree is being constructed in a quite straightforward way by regarding the conflict graph $\bar{G}_{3-SAT}$.\\
On the other hand, we show that an optimal solution $T$ with weight $k$ implies the existence of a satisfying truth assignment for $I$. 
Here the main idea is to show that for each clause of $I$ at least one edge that represents one of the literals that make up the clause is contained in the tree.
Thus, as a consequence of the conflict graph, the truth assignment that sets ``TRUE'' exactly those literals that are contained in the tree $T$ constitutes a 
satisfying truth assignment for $I$.

\subsection{\label{sub:G_{3-SAT} and quer}The graphs $G_{3-SAT}$ and $\bar{G}_{3-SAT}$}

\subsubsection{Construction of $G_{3-SAT}$}

Unless otherwise stated, each edge of $G_{3-SAT}$ has zero weight.
The graph $G_{3-SAT}$ is being built as follows (see Figure~\ref{fig:G-3SAT}):
For each variable $x_{i}$, $1\leq i\leq n$, we introduce

\begin{itemize}
\item the edges $x_{i}=(a_{i},b_{i})$ and $\bar{x}_{i}=(\bar{a}_{i},\bar{b}_{i})$
corresponding to the literals with the same label, 
\item a vertex $i$ that is connected to $b_{i}$ and $\bar{b}_{i}$ via
the edges $y_{i}$ and $\bar{y}_{i}$ respectively and 
\item one path of length $\l_{i}$ starting in vertex $i$
and ending in $a_{i}$. Let the edges of this path starting at $i$
be called $w_{i0},w_{i1},w_{i2},\ldots$\ . %w_{i3},w_{i4}$. 
Each vertex of this path is connected to vertex $b_{i}$ by the edges
$z_{i1},z_{i2},\ldots$\ , where $z_{ij}$ is adjacent to $w_{i(j-1)}$,
$j\geq1$. An analogous path is defined for $i$ and $\bar{a}_{i}$
with the corresponding connections to $\bar{b}_{i}$. 
\end{itemize}
For each clause $C_{j}$, $1\leq j\leq k$,

\begin{itemize}
\item a vertex labelled $C_{j}$ is introduced, 
\item for each $x_{i}$ contained in clause $C_{j}$ we insert a path of
length 4 consisting of edges $(e_{ij}, f_{ij}, g_{ij}, h_{ij})$
starting in vertex $a_{i}$ and ending in vertex $C_{j}$. 
Furthermore, a shortcut is constructed by joining vertex $a_{i}$ to the vertex
incident to $f_{ij}$ and $g_{ij}$ via an edge $\Delta_{ij}$.


Analogously, the path $(\bar{e}_{ij},\bar{f}_{ij},\bar{g}_{ij},\bar{h}_{ij})$
connects $\bar{a}_{i}$ with $C_{j}$ if literal $\bar{x}_{i}$ is
contained in $C_{j}$ with an analogous shortcut $\bar{\Delta}_{ij}$.

\end{itemize}
Finally, edges connecting the parts of $G_{3-SAT}$ described
above are introduced. For $1\leq i\leq n-1$ we introduce an edge
connecting vertex $i$ with vertex $i+1$.

A weight of $1$ is associated with all edges $g_{ij}$ and $\bar{g}_{ij}$.
Note that these are the only edges of non-zero weight in $G_{3-SAT}$.
%Furthermore each of the edges $x_{i}$ and $\bar{x}_{i}$ need to 
%be connected with the clauses $C_{j}$ in which the corresponding 
%literal occurs (at most 5 edges for each variable). For literal $x_{i}$, 
%this is done by inserting an edge $e_{ij}$ adjacent to $x_{i}$ and 
%$f_{ij}$ but not to $g_{ij}$ and an edge $\Delta_{ij}$ adjacent 
%to $x_{i}$, $f_{ij}$ and $g_{ij}$. Again in an analogous way edges 
%are inserted for literal $\bar{x}_{i}$.



\subsubsection{Construction of $\bar{G}_{3-SAT}$}

The conflict graph $\bar{G}_{3-SAT}$ on the edges of $G_{3-SAT}$
is defined in the following way. %For a variable $x_{i}$ let $l$ be the number of clauses containing 
%literal $x_{i}$ and $\bar{l}$ the number of clauses containing literal 
%$\bar{x}_{i}$ ($l+\bar{l}\leq5$). 
Denote the clauses containing literal $x_{i}$ resp.\ $\bar{x}_{i}$
by $C_{x_{i0}},\ldots, C_{x_{i(\l_{i}-1)}}$ resp.\ $C_{\bar{x}_{i0}},\ldots, C_{\bar{x}_{i(\bar{l}_{i}-1)}}$,
where the order in which theses clauses are chosen is arbitrary but
fixed. Then we introduce in $\bar{G}_{3-SAT}$ the edge $(w_{i0},f_{ix_{i0}})$
and the paths $(z_{i1},w_{i1},f_{ix_{i1}}),\ldots,(z_{i\l_{i}-1},w_{i\l_{i}-1},f_{ix_{i\l_{i}-1}})$.
Again we construct equivalent components of $\bar{G}_{3-SAT}$ for
the clauses $C_{\bar{x}_{i0}},\ldots, C_{\bar{x}_{i(\bar{\l}_{i}-1)}}$
containing literal $\bar{x}_{i}$.

%%%% dirty format
Furthermore we add the edges $(x_{i},\bar{x}_{i})$, the edges
$(\Delta_{ix_{i0}},g_{ix_{i0}}),\ldots,(\Delta_{ix_{i(\l i-1)}},$ $g_{ix_{i(\l_{i}-1)}})$
and the edges 
$(\bar{\Delta}_{i\bar{x}_{i0}},\bar{g}_{i\bar{x}_{i0}}),\ldots, (\bar{\Delta}_{i\bar{x}_{i(\bar{\l}_{i}-1)}}, \bar{g}_{i\bar{x}_{i(\bar{\l}_{i}-1)}})$.
This procedure is performed for all variables.

\begin{remark}Note that $\bar{G}_{3-SAT}$ is not a $3$-ladder. To
be more precise, $\bar{G}_{3-SAT}$ consists of a subgraph being a
$3$-ladder, a subgraph which is made up of components consisting
of a single edge, and of isolated vertices. However, by introducing
{}``dummy edges'' $\bar{G}_{3-SAT}$ can easily be transformed into
a $3$-ladder.\end{remark}

\begin{sidewaysfigure}[h] \centering \scalebox{0.54} {\begin{pspicture}(0,-11.035781)(37.617813,11.055781) \definecolor{color651b}{rgb}{0.9764705882352941,0.9764705882352941,0.9764705882352941} \psdots[dotsize=0.2](8.863125,9.084219) \psdots[dotsize=0.2](5.863125,7.084219) \psdots[dotsize=0.2](8.863125,7.084219) \psdots[dotsize=0.2](11.863125,7.084219) \psdots[dotsize=0.2](11.863125,6.084219) \psdots[dotsize=0.2](8.863125,6.084219) \psdots[dotsize=0.2](5.863125,6.084219) \psdots[dotsize=0.2](11.863125,4.084219) \psdots[dotsize=0.2](8.863125,4.084219) \psdots[dotsize=0.2](5.863125,4.084219) \psdots[dotsize=0.2](12.863125,1.0842187) \psdots[dotsize=0.2](12.863125,-1.9157813) \psdots[dotsize=0.2](16.863125,-4.915781) \psline[linewidth=0.04cm](8.863125,9.084219)(5.863125,7.084219) \psline[linewidth=0.04cm](8.863125,9.084219)(11.863125,7.084219) \psline[linewidth=0.04cm](8.863125,9.084219)(8.863125,4.084219) \psline[linewidth=0.04cm](11.863125,7.084219)(11.863125,4.184219) \psline[linewidth=0.04cm](5.863125,7.084219)(5.863125,4.084219) \psline[linewidth=0.04cm](12.863125,1.0842187)(12.863125,-1.9157813) \psdots[dotsize=0.2](20.863125,-1.9157813) \psdots[dotsize=0.2](20.863125,1.0842187) \psline[linewidth=0.04cm](20.863125,1.0842187)(20.863125,-1.9157813) \psline[linewidth=0.04cm](20.863125,-1.9157813)(16.863125,-4.915781) \psline[linewidth=0.04cm](12.863125,-1.9157813)(16.863125,-4.915781) \psline[linewidth=0.04cm](12.863125,1.0842187)(8.863125,6.084219) \psline[linewidth=0.04cm](12.863125,1.0842187)(8.863125,4.084219) \psline[linewidth=0.04cm](20.863125,1.0842187)(16.863125,-4.915781) \psline[linewidth=0.04cm](12.863125,1.0842187)(16.863125,-4.915781) \psdots[dotsize=0.2](13.663125,-0.11578125) \psdots[dotsize=0.2](20.063126,-0.11578125) \psdots[dotsize=0.2](14.363125,-1.2157812) \psdots[dotsize=0.2](19.363125,-1.2157812) \psdots[dotsize=0.2](15.163125,-2.4157813) \psdots[dotsize=0.2](18.563126,-2.4157813) \psdots[dotsize=0.2](15.963125,-3.5157812) \psdots[dotsize=0.2](17.763124,-3.5157812) \psline[linewidth=0.04cm](12.863125,-1.9157813)(13.663125,-0.11578125) \psline[linewidth=0.04cm](12.863125,-1.9157813)(14.363125,-1.2157812) \psline[linewidth=0.04cm](12.863125,-1.9157813)(15.163125,-2.4157813) \psline[linewidth=0.04cm](12.863125,-1.9157813)(15.963125,-3.6) \psline[linewidth=0.04cm](17.75,-3.65)(20.863125,-1.92) \psline[linewidth=0.04cm](18.563126,-2.4157813)(20.863125,-1.9157813) \psline[linewidth=0.04cm](19.363125,-1.2157812)(20.863125,-1.9157813) \psline[linewidth=0.04cm](20.063126,-0.11578125)(20.863125,-1.9157813) \psdots[dotsize=0.2](16.863125,-6.915781) \psline[linewidth=0.07cm,linestyle=dotted,dotsep=0.16cm](16.863125,-7.0157814)(16.863125,-10.915781) \psdots[dotsize=0.2](16.863125,-10.915781) \psdots[dotsize=0.2](25.863125,-1.9157813) \psdots[dotsize=0.2](7.863125,-1.9157813) \psdots[dotsize=0.2](25.863125,1.0842187) \psdots[dotsize=0.2](7.863125,1.0842187) \psdots[dotsize=0.2](32.863125,-1.9157813) \psdots[dotsize=0.2](32.863125,1.0842187) \psdots[dotsize=0.2](0.863125,-1.9157813) \psdots[dotsize=0.2](0.863125,1.0842187) \psline[linewidth=0.04cm](25.863125,1.0842187)(25.863125,-1.8157812) \psline[linewidth=0.04cm](32.863125,1.0842187)(32.863125,-2.0157812) \psline[linewidth=0.04cm](7.863125,1.0842187)(7.863125,-1.9157813) \psline[linewidth=0.04cm](0.863125,1.0842187)(0.863125,-1.8157812) \psline[linewidth=0.07cm,linestyle=dotted,dotsep=0.16cm](1.363125,-0.91578126)(7.363125,-0.91578126) \psline[linewidth=0.07cm,linestyle=dotted,dotsep=0.16cm](26.363125,-0.91578126)(32.363125,-0.91578126) \psline[linewidth=0.04cm](16.863125,-6.915781)(25.863125,-1.9157813) \psline[linewidth=0.04cm](16.863125,-6.915781)(25.863125,1.0842187) \psline[linewidth=0.04cm](16.863125,-6.915781)(7.863125,1.0842187) \psline[linewidth=0.04cm](16.863125,-6.915781)(7.863125,-1.9157813) \psline[linewidth=0.04cm](16.863125,-10.915781)(32.863125,-1.9157813) \psline[linewidth=0.04cm](16.863125,-10.915781)(32.863125,1.0842187) \psline[linewidth=0.04cm](16.863125,-10.915781)(0.863125,1.0842187) \psline[linewidth=0.04cm](16.863125,-10.915781)(0.863125,-1.9157813) \psline[linewidth=0.04cm](16.863125,-4.915781)(16.863125,-6.915781) \psdots[dotsize=0.2](19.403126,10.484219) \psdots[dotsize=0.2](16.403126,8.484219) \psdots[dotsize=0.2](19.403126,8.484219) \psdots[dotsize=0.2](22.403126,8.484219) \psdots[dotsize=0.2](22.403126,7.4842186) \psdots[dotsize=0.2](19.403126,7.4842186) \psdots[dotsize=0.2](16.403126,7.4842186) \psdots[dotsize=0.2](22.403126,5.4842186) \psdots[dotsize=0.2](19.403126,5.4842186) \psdots[dotsize=0.2](16.403126,5.4842186) \psline[linewidth=0.04cm](19.403126,10.484219)(16.403126,8.484219) \psline[linewidth=0.04cm](19.403126,10.484219)(22.403126,8.484219) \psline[linewidth=0.04cm](19.403126,10.484219)(19.403126,5.4842186) \psline[linewidth=0.04cm](22.403126,8.484219)(22.403126,5.584219) \psline[linewidth=0.04cm](16.403126,8.484219)(16.403126,5.4842186) \psdots[dotsize=0.2](31.403126,10.484219) \psdots[dotsize=0.2](28.403126,8.484219) \psdots[dotsize=0.2](31.403126,8.484219) \psdots[dotsize=0.2](34.403126,8.484219) \psdots[dotsize=0.2](34.403126,7.4842186) \psdots[dotsize=0.2](31.403126,7.4842186) \psdots[dotsize=0.2](28.403126,7.4842186) \psdots[dotsize=0.2](34.403126,5.4842186) \psdots[dotsize=0.2](31.403126,5.4842186) \psdots[dotsize=0.2](28.403126,5.4842186) \psline[linewidth=0.04cm](31.403126,10.484219)(28.403126,8.484219) \psline[linewidth=0.04cm](31.403126,10.484219)(34.403126,8.484219) \psline[linewidth=0.04cm](31.403126,10.484219)(31.403126,5.4842186) \psline[linewidth=0.04cm](34.403126,8.484219)(34.403126,5.584219) \psline[linewidth=0.04cm](28.403126,8.484219)(28.403126,5.4842186) \psline[linewidth=0.07cm,linestyle=dotted,dotsep=0.16cm](22.903126,6.4842186)(27.803125,6.4842186) \psdots[dotsize=0.2](19.763124,-8.715781) \psdots[dotsize=0.2](22.763124,-6.5157814) \psdots[dotsize=0.2](25.663124,-4.315781) \psdots[dotsize=0.2](28.963125,-1.8157812) \psdots[dotsize=0.2](13.863125,-8.715781) \psdots[dotsize=0.2](10.963125,-6.5157814) \psdots[dotsize=0.2](8.063125,-4.315781) \psdots[dotsize=0.2](4.763125,-1.8157812) \psdots[dotsize=0.2](18.863125,-5.1157813) \psdots[dotsize=0.2](20.663124,-3.5157812) \psdots[dotsize=0.2](22.263124,-2.1157813) \psdots[dotsize=0.2](23.963125,-0.61578125) \psdots[dotsize=0.2](14.863125,-5.1157813) \psdots[dotsize=0.2](13.063125,-3.5157812) \psdots[dotsize=0.2](11.463125,-2.1157813) \psdots[dotsize=0.2](9.763125,-0.61578125) \psline[linewidth=0.04cm](25.763124,1.1442188)(11.763125,4.084219) \psline[linewidth=0.04cm](11.903125,6.0442185)(25.763124,1.1442188) \psline[linewidth=0.04cm](0.843125,1.0042187)(5.883125,4.084219) \psline[linewidth=0.04cm](0.843125,1.0042187)(5.883125,6.184219) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](12.883125,1.1442188)(16.383125,5.4842186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](12.883125,1.1442188)(16.383125,7.4442186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](12.883125,1.1442188)(25.483126,5.3442187) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](12.883125,1.1442188)(25.483126,7.4442186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.843125,1.1442188)(9.523125,1.7042187) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.843125,1.0042187)(8.823125,2.5442188) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](20.863125,1.1442188)(28.423124,5.4842186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](20.863125,1.1442188)(28.423124,7.4442186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.763126,1.1442188)(23.943125,5.3442187) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.903126,1.1442188)(23.943125,7.4442186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.903126,1.1442188)(34.443127,5.4842186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.903126,1.1442188)(34.303123,7.4442186) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](31.363125,5.4842186)(29.263124,1.1442188) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](31.363125,7.584219)(29.263124,1.1442188) \usefont{T1}{ptm}{m}{n} \rput(8.9,9.5){\Large $C_1$} \usefont{T1}{ptm}{m}{n} \rput(18.9,10.6){\Large $C_i$} \usefont{T1}{ptm}{m}{n} \rput(30.9,10.6){\Large $C_k$} \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](25.903126,-1.9357812)(23.943125,-0.67578125) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](25.763124,-1.9357812)(22.263124,-2.0757813) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](25.903126,-1.9357812)(20.723125,-3.4757812) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](25.763124,-1.9357812)(18.903126,-5.1557813) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.863125,-1.9157813)(28.963125,-1.8157812) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.863125,-1.9157813)(25.663124,-4.315781) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.863125,-1.9157813)(22.863125,-6.5157814) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](32.863125,-1.9157813)(19.863125,-8.715781) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.863125,-1.9157813)(9.78,-0.53) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.863125,-1.9157813)(11.463125,-2.1157813) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.863125,-1.9157813)(13.063125,-3.5157812) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](7.863125,-1.9157813)(14.863125,-5.1157813) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](0.863125,-1.9157813)(4.863125,-1.8157812) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](0.863125,-1.9157813)(8.063125,-4.315781) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](0.863125,-1.9157813)(11.063125,-6.5157814) \psline[linewidth=0.04cm,linestyle=dashed,dash=0.16cm 0.16cm](0.863125,-1.9157813)(13.863125,-8.715781) \usefont{T1}{ptm}{m}{n} \rput(12.2,-0.3){\huge $x_1$} \usefont{T1}{ptm}{m}{n} \rput(21.4,-0.3){\huge $\bar{x}_1$} \usefont{T1}{ptm}{m}{n} \rput(26.5,-0.3){\huge $\bar{x}_2$} \usefont{T1}{ptm}{m}{n} \rput(33.5,-0.3){\huge $\bar{x}_n$} \usefont{T1}{ptm}{m}{n} \rput(7.11,-0.3){\huge $x_2$} \usefont{T1}{ptm}{m}{n} \rput(0,-0.3){\huge $x_n$} \usefont{T1}{ptm}{m}{n} \rput(8.35,8.1){\huge $h_{11}$} \usefont{T1}{ptm}{m}{n} \rput(6.35,8.1){\huge $h_{n1}$} \usefont{T1}{ptm}{m}{n} \rput(11.3,8.1){\huge $\bar{h}_{21}$} \usefont{T1}{ptm}{m}{n} \rput(9.5,6.5){\huge $g_{11}$} \usefont{T1}{ptm}{m}{n} \rput(6.5,6.5){\huge $g_{n1}$} \usefont{T1}{ptm}{m}{n} \rput(12.6,6.5){\huge $\bar{g}_{21}$} \usefont{T1}{ptm}{m}{n} \rput(8.35,4.9){\huge $f_{11}$} \usefont{T1}{ptm}{m}{n} \rput(6.35,4.9){\huge $f_{n1}$} \usefont{T1}{ptm}{m}{n} \rput(12.4,4.9){\huge $\bar{f}_{21}$} \usefont{T1}{ptm}{m}{n} \rput(9.6,3){\huge $e_{11}$} \usefont{T1}{ptm}{m}{n} \rput(12.2,3){\huge $\Delta_{11}$} \usefont{T1}{ptm}{m}{n} \rput(14.752031,-3.8){\huge $y_1$} \usefont{T1}{ptm}{m}{n} \rput(19.1,-3.8){\huge $\bar{y}_1$} \usefont{T1}{ptm}{m}{n} \rput(17.2,-5.4){\huge $1$} \usefont{T1}{ptm}{m}{n} \rput(17.2,-7.4){\huge $2$} \usefont{T1}{ptm}{m}{n} \rput(17.2,-11.4){\huge $n$} \usefont{T1}{ptm}{m}{n} \rput(13.2,-0.3){\Large $z_{14}$} \usefont{T1}{ptm}{m}{n} \rput(13.7,-1.15){\Large $z_{13}$} \usefont{T1}{ptm}{m}{n} \rput(14.3,-1.95){\Large $z_{12}$} \usefont{T1}{ptm}{m}{n} \rput(15,-2.75){\Large $z_{11}$} \usefont{T1}{ptm}{m}{n} \rput(20.515,-0.3){\Large $\bar{z}_{14}$} \usefont{T1}{ptm}{m}{n} \rput(20.015,-1.15){\Large $\bar{z}_{13}$} \usefont{T1}{ptm}{m}{n} \rput(19.4,-1.9){\Large $\bar{z}_{12}$} \usefont{T1}{ptm}{m}{n} \rput(18.71,-2.77){\Large $\bar{z}_{11}$} \usefont{T1}{ptm}{m}{n} \rput(13.7,0.6){\Large $w_{14}$} \usefont{T1}{ptm}{m}{n} \rput(14.55,-0.6){\Large$w_{13}$} \usefont{T1}{ptm}{m}{n} \rput(15.3,-1.8){\Large $w_{12}$} \usefont{T1}{ptm}{m}{n} \rput(16,-2.8){\Large $w_{11}$} \usefont{T1}{ptm}{m}{n} \rput(16.55,-3.7){\Large $w_{10}$} \usefont{T1}{ptm}{m}{n} \rput(19.9,0.6){\Large $\bar{w}_{14}$} \usefont{T1}{ptm}{m}{n} \rput(19.05,-0.6){\Large $\bar{w}_{13}$} \usefont{T1}{ptm}{m}{n} \rput(18.3,-1.8){\Large $\bar{w}_{12}$} \usefont{T1}{ptm}{m}{n} \rput(17.6,-2.8){\Large $\bar{w}_{11}$} \usefont{T1}{ptm}{m}{n} \rput(16.85,-4.16){\Large $\bar{w}_{10}$} \usefont{T1}{ptm}{m}{n} \rput(5.2,6.5){\Large $1$} \usefont{T1}{ptm}{m}{n} \rput(8.2,6.5){\Large $1$} \usefont{T1}{ptm}{m}{n} \rput(11.3,6.5){\Large $1$} 

\usefont{T1}{ptm}{m}{n} \rput(12.2,0.9){\huge $a_1$}
\usefont{T1}{ptm}{m}{n} \rput(12.2,-1.8){\huge $b_1$}

\usefont{T1}{ptm}{m}{n} \rput(21.4,0.9){\huge $\bar{a}_1$}
\usefont{T1}{ptm}{m}{n} \rput(21.4,-1.8){\huge $\bar{b}_1$}

\usefont{T1}{ptm}{m}{n} \rput(7.11,0.9){\huge $a_2$} 
\usefont{T1}{ptm}{m}{n} \rput(7.11,-1.8){\huge $b_2$} 

\usefont{T1}{ptm}{m}{n} \rput(26.5,0.9){\huge $\bar{a}_2$} 
\usefont{T1}{ptm}{m}{n} \rput(26.5,-1.8){\huge $\bar{b}_2$} 


\usefont{T1}{ptm}{m}{n} \rput(0,0.9){\huge $a_n$} 
\usefont{T1}{ptm}{m}{n} \rput(0,-1.8){\huge $b_n$} 

\usefont{T1}{ptm}{m}{n} \rput(33.5,0.9){\huge $\bar{a}_n$} 
\usefont{T1}{ptm}{m}{n} \rput(33.5,-1.8){\huge $\bar{b}_n$} 


\end{pspicture}
} 
\caption{\label{fig:G-3SAT}The graph $G_{3-SAT}$}
\end{sidewaysfigure}  


\subsection{\label{reduction}MSTCG with a 3-ladder conflict graph is strongly $\mathcal{NP}$-hard}

\begin{theorem} Let $G=(V,E)$ be an undirected graph and let the conflict
graph $\bar{G}=(E,\bar{E})$ be a $3$-ladder. Then MSTCG is strongly
$\mathcal{NP}$-hard. \end{theorem} \textbf{Proof.}\\
 Let $I$ be an instance of 3-SAT where each variable occurs in at
most 5 clauses. Let the instance $I'$ of $MSTCG$ be defined by the
graph $G_{3-SAT}$ and the conflict graph $\bar{G}_{3-SAT}$ constructed
as described in Section~\ref{sub:G_{3-SAT} and quer}. Let $\tau$
be the set of feasible solutions of $I'$. \\
 Let $T\in\tau$. It is easy to see that $T$ must have a weight of
at least $k$: The set $G_{j}:=\{g_{qj}|1\leq q\leq n\}\cup\{\bar{g}_{qj}|1\leq q\leq n\}$
is a cut set, i.e.\ it separates the vertex $C_{j}$ from the rest
of the graph. Therefore, every spanning tree must contain at least
one edge from $G_{j}$. %Since $T$ is a tree, for each of the $k$ vertices 
%$C_{j}$ at least one edge of the set $G_{j}:=\{g_{qj}|1\leq q\leq n\}\cup\{\bar{g}_{qj}|1\leq q\leq n\}$ 
%has to be contained in $T$. 
Since each of the mentioned edges has a weight of $1$ we have $w(T)\geq k$.\\
 We proof the theorem by showing that the following equivalence holds:
\[
\exists\mbox{ a satisfying truth assignment for }I\Longleftrightarrow\exists\ T\in\tau:w(T)\leq k\]
 {}``$\Longrightarrow$'': Given a satisfying truth assignment $t_{I}$
for instance $I$ we construct a feasible solution $T$ of $I'$ with
$w(T)=k$ in a quite straightforward way. Let $T:=\emptyset$ and let $X:=\{x_{i_{1}},\ldots,x_{i_{r}}\}$
and $\bar{X}=\{\bar{x}_{k_{1}},\ldots,\bar{x}_{k_{s}}\}$ be the sets
of literals set {}``TRUE'' under $t_{I}$ (recall that setting literal
$\bar{x}_{k_{j}}$ {}``TRUE'' means to set variable $x_{k_{j}}$
{}``FALSE'', $1\leq j\leq s$). \[
T:=T\cup X\cup\bar{X}\]
 \[
T:=T\cup\{y_{i}\}\cup\{\bar{y}_{i}\}\quad\forall\, i\ \in\{1,\ldots,n\}\]
 \[
T:=T\cup\{(i,i+1)\}\quad\forall\, i\ \in\{1,\ldots,n-1\}\]


Label all clauses $C_{j}$ {}``unmarked''. Let $C(x_{i})$ (resp.\ $C(\bar{x}_{i})$)
be the set of all clauses containing $x_{i}$ (resp.\ $\bar{x}_{i}$).
We complete $T$ by performing the following algorithmic statements:

\hspace*{0.5cm} for $i\in\{i_{1},\ldots,i_{r}\}$:\\
 \hspace*{1.0cm} $T:=T\cup\{\bar{w}_{i0}\}$\\
 \hspace*{1.0cm} for $j\in\{1,\ldots,\l_{i}\}$:\\
 \hspace*{1.5cm} $T:=T\cup \{z_{ij}\}$\\
 \hspace*{1.0cm} for $j'\in\{1,\ldots,\bar{\l}_{i}\}$:\\
 \hspace*{1.5cm} $T:=T\cup\{\bar{w}_{ij'}\}$\\
 \hspace*{1.0cm} for $C_{j}\ \in C(x_{i})$:\\
 \hspace*{1.5cm} $T:=T\cup\{e_{ij},f_{ij},h_{ij}\}$\\
 \hspace*{1.5cm} if $C_{j}$ is {}``unmarked'':\hfill{}$(a)$\\
 \hspace*{2.0cm} $T:=T\cup\{g_{ij}\}$\\
 \hspace*{2.0cm} Label $C_{j}$ {}``marked''.\\
 \hspace*{1.0cm} for $C_{j}\ \in C(\bar{x}_{i})$:\\
 \hspace*{1.5cm} $T:=T\cup\{\bar{\Delta}_{ij},\bar{e}_{ij},\bar{h}_{ij}\}$
\bigskip{}


\hspace*{0.5cm} for $k\in\{k_{1},\ldots,k_{s}\}$:\\
 \hspace*{1.0cm} $T:=T\cup\{ w_{k0}\}$\\
 \hspace*{1.0cm} for $j\in\{1,\ldots,\bar{\l}_{k}\}$:\\
 \hspace*{1.5cm} $T:=T\cup\{\bar{z}_{kj}\}$\\
 \hspace*{1.0cm} for $j'\in\{1,\ldots,\l_{k}\}$:\\
 \hspace*{1.5cm} $T:=T\cup \{w_{kj'}\}$\\
 \hspace*{1.0cm} for $C_{j}\ \in C(\bar{x}_{k})$:\\
 \hspace*{1.5cm} $T:=T\cup\{\bar{e}_{kj},\bar{f}_{kj},\bar{h}_{kj}\}$\\
 \hspace*{1.5cm} if $C_{j}$ is {}``unmarked'':\hfill{}$(a)$\\
 \hspace*{2.0cm} $T:=T\cup\{\bar{g}_{kj}\}$\\
 \hspace*{2.0cm} Label $C_{j}$ {}``marked''.\\
 \hspace*{1.0cm} for $C_{j}\ \in C(x_{k})$:\\
 \hspace*{1.5cm} $T:=T\cup\{\Delta_{kj},e_{kj},h_{kj}\}$

\medskip{}
 It is easy to check that $T$ is a feasible solution of $I'$. Since
$t_{I}$ is a satisfying truth assignment for $I$, each clause $C_{j}$
contains a literal set {}``TRUE''. As mentioned before, in order
to reach a vertex $C_{j}$ at least one edge with weight $1$ has
to be added to $T$. By $(a)$ in the construction of $T$ for each
vertex $C_{j}$ exactly one such edge is contained in $T$. Thus we
get $w(T)=k$. \medskip{}


{}``$\Longleftarrow$'': 
Let $T\in\tau$ with $w(T)=k$. Since each
vertex $C_{j}$ has to be reached, at least one edge $G_{j}=\{g_{qj}|1\leq q\leq n\}\cup\{\bar{g}_{qj}|1\leq q\leq n\}$
has to be contained in $T$, $1\leq j\leq k$. However, since each
edge of $G_{j}$ has weight $1$, exactly one edge of $G_{j}$ is
contained in $T$, $1\leq j\leq k$. Recall that each vertex $C_{j}$
corresponds to a clause with the same label. Let for vertex (clause)
$C_{j}$ the edge $g_{ij}$ be the unique edge in $T$ that is an
element of $G_{j}$. We will now show that this implies $x_{i}\in T$
and $\bar{x}_{i}\notin T$:\\
 Let $\gamma$ be the vertex incident to both $g_{ij}$ and $f_{ij}$.
As $T$ is a tree there has to be a unique simple path $p$ in $T$
between vertex $\gamma$ and vertex $1$. Due to the fact that $g_{ij}$
is the only edge in $T$ that is contained in the set $G_{j}$ the
path $p$ cannot pass through vertex $C_{j}$. Analogously, $p$ cannot
pass through any of the vertices $C_{r}\not=C_{j}$, $1\leq r\leq k$.
Furthermore, the edge $\Delta_{ij}$ cannot be contained in $p$ because
the edge $(\Delta_{ij},g_{ij})$ is a component of the conflict graph
$\bar{G}_{3-SAT}$. Thus $f_{ij},e_{ij}\in p$ (and hence $f_{ij},e_{ij}\in T$)
has to hold.

Now assume $x_{i}\notin T$. Then in order to reach vertex $1$ the
path $p$ must contain $w_{i(\l_{i}-1)}$. Note that $w_{i(\l_{i}-1)}\in T$
implies $z_{i(\l_{i}-1)}\notin T$ because of $\bar{G}_{3-SAT}$.
Analogously, we have $w_{ik}\in T$ and $z_{ik}\notin T$ for $1\leq k\leq\l_{i}-2$
and $w_{i0}\in T$ as well. Thus we have $w_{ik}\in T$ for all $0\leq k\leq\l_{i}-1$
which contradicts $f_{ij}\in T$ due to the construction of $\bar{G}_{3-SAT}$.
Hence $x_{i}\in T$, and again by $\bar{G}_{3-SAT}$ we get $\bar{x_{i}}\notin T$.

Summarizing the facts we have that for each vertex $C_{j}$ exactly
one edge $x_{i}$, resp.\ $\bar{x}_{i}$, is contained in $T$ that
is connected to $C_{j}$ by the path $(e_{ij},f_{ij},g_{ij},h_{ij})$,
resp.\ $(\bar{e}_{ij},\bar{f}_{ij},\bar{g}_{ij},\bar{h}_{ij})$.
That is, for each clause at least one of the literals the clause is
made up of is contained in the tree. Thus, the truth assignment that
sets a variable $x_{i}$ {}``TRUE'' if $x_{i}\in T$ and $x_{i}$
{}``FALSE'' if $\bar{x}_{i}\in T$ constitutes a satisfying truth
assignment for $I$. %Thus, the truth assignment that sets a literal $x_{i}$ (resp. $\bar{x}_{i}$) {}``TRUE'' if $x_{i}\in T$ 
%(resp. $\bar{x}_{i}\in T$) and {}``FALSE'' otherwise constitutes a satisfying truth assignment for $I$.
\hfill{}$\square$

Since MSTCG is strongly $\mathcal{NP}$-hard given the conflict graph
is a $3$-ladder, MSTCG is also strongly $\mathcal{NP}$-hard in case
the conflict graph is a path. Finally both results obviously imply
that MSTCG is strongly $\mathcal{NP}$-hard for general conflict graphs.
\begin{corollary}Given the conflict graph is a path, MSTCG is strongly
$\mathcal{NP}$-hard.\end{corollary} \begin{corollary}MSTCG is strongly $\mathcal{NP}$-hard.\end{corollary}


\section{MSTCG with disjoint conflicting pairs of edges is in $\mathcal{P}$}
\label{sec:poly}

In this section we focus on the MSTCG where the conflict graph is
a $2$-ladder, i.e.\ the conflict graph represents pairwise disjoint
forbidden pairs of edges of $E$. %Thus, we are given a connected graph $G=(V,E)$ and a conflict graph 
%$\bar{G}=(E,\bar{E})$ such that, for some $1\leq k\leq n$, $\bar{E}=\{(e_{1},e_{2})\ldots(e_{2k-1},e_{2k})\}$ 
%for some edges $e_{i}\not=e_{j}\in E$, $1\leq i<j\leq2k$. 
We will first give a representation of the set $\tau$ of feasible
solutions of this problem by using matroid intersection. With the
help of that representation, Edmonds' famous matroid-intersection
theorem (Edmonds~\cite{edmonds}, cf.~\cite{schr03}) yields that
an optimal solution of MSTCG with disjoint conflicting pairs of edges
can be computed in polynomial time.

Let us consider the ILP-formulation of our problem. Condition~(\ref{eqn:subtour})
of this formulation induces the well-known \textit{graphic-matroid}.
To be more precise, the graphic matroid $\mathcal{M}_{1}=(E,\mathcal{I}_{1})$
is being formed by all subsets of $E$ which do not form a cycle~\cite{schr03}.
More formally, $\mathcal{I}_{1}$ is the set of all subsets of $E$
such that ~(\ref{eqn:subtour}) is satisfied. Obviously a base of
$\mathcal{M}_{1}$ consists of $n-1$ edges (a base corresponds to
a spanning tree) and thus (\ref{eqn:card}) is satisfied by all bases
of $\mathcal{M}_{1}$. However, the fact that the conflict graph $\bar{G}$
is being made up of disjoint conflicting pairs of edges of $G$ induces
a matroid as well. As we will show below, defining $\mathcal{I}_{2}$
as the set of all subsets of $E$ that do not contain a conflicting
pair of edges (represented by $\bar{G}$) yields a matroid $\mathcal{M}_{2}=(E,\mathcal{I}_{2})$.
This matroid will be called \textit{conflict-free matroid}. More formally,
the conflict-free matroid $\mathcal{M}_{2}=(E,\mathcal{I}_{2})$ is
defined by \[
\mathcal{I}_{2}:=\{E'\subseteq E|\nexists(e,f)\in\bar{E}:\{e,f\}\subseteq E').\]


\begin{lemma} $\mathcal{M}_{2}=(E,\mathcal{I}_{2})$ is a matroid.
\end{lemma}

\textbf{Proof.} \\
 Obviously, $\emptyset\in\mathcal{I}_{2}$ is satisfied. \\
 Let $J$ be an element of $\mathcal{I}_{2}$ and $I$ any subset
of $J$. Then $I$ cannot include a conflicting pair as $J$ does
not and hence $I\in\mathcal{I}_{2}$ holds. Thus $J\in\mathcal{I}_{2}$
implies $I\in\mathcal{I}_{2}$ for all $I\subseteq J$.\\
 Let $I,J\in\mathcal{I}_{2}$ and $|I|<|J|$, then we have to show
that $(I\cup\{z\})\in\mathcal{I}_{2}$ for some $z\in J\setminus I$:

\begin{itemize}
\item \textit{Case~1:} $I\subset J$. This case is trivial. 
\item \textit{Case~2:} $I\cap J=\emptyset$. Assume that no such edge $z$
exists: Then for every edge $e\in J$ the set $(I\cup\{e\})$ is not
in $\mathcal{I}_{2}$. This implies that there exists an edge $e^{c}\in I$
such that $(e,e^{c})$ is a conflicting pair in $(I\cup\{e\})$. But
since $\bar{G}$ is a $2$-ladder for each edge $e'\in E$ there is
at most one edge that is in conflict with $e'$. Hence, every edge
$e^{c}\in I$ can belong to only one conflicting pair $(e,e^{c})$
with $e\in J$. Thereby, we get a contradiction to $|I|<|J|$. 
\item \textit{Case~3:} $I\cap J\neq\emptyset$. Let $I':=I\setminus(I\cap J)$
and $J':=J\setminus(I\cap J)$. Then we have $I',J'\in\mathcal{I}_{2}$,
$|I'|<|J'|$ and $I'\cap J'=\emptyset$. From \textit{Case~2} we
get that there is a $z\in J'$ such that $(I'\cup\{z\})\in\mathcal{I}_{2}$.
It follows from $z\in J$ that $z$ can not be in conflict with any
edge in $I\cap J$ and hence $(I\cup\{z\})\in\mathcal{I}_{2}$. 
\end{itemize}
\hfill{}$\square$

Clearly, any feasible solution of MSTCG with disjoint conflicting
pairs of edges corresponds to a common base of the graphic matroid
and the conflict-free matroid. Thus, an optimal solution of MSTCG
is a common base of $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ with
minimum weight. As a consequence, Edmonds' weighted matroid intersection
algorithm gives the answer on the question of the computational complexity
of MSTCG with disjoint conflicting pairs of edges.

\begin{theorem}(Edmonds~\cite{edmonds}, cf.~\cite{schr03})\\
 Let $S$ be a set and let $c:S\to\mathbb{R}$. Given two matroids
$M_{1}=(S,I_{1})$ and $M_{2}=(S,I_{2})$, a common base of $M_{1}$
and $M_{2}$ with minimum weight can be found in strongly polynomial
time.\end{theorem}

Since any optimal solution of MSTCG corresponds to a minimum-weight
common base of the graphic matroid and the conflict-free matroid the
above theorem yields the following result.

\begin{theorem}MSTCG with disjoint conflicting pairs of edges can be
solved in strongly polynomial time. \end{theorem}

%\section{Conclusion}
%For the minimum spanning tree problem in an undirected graph $G$ 
%numerous efficient algorithms are known~\cite{Ahuja}. Imposing incompatibilities 
%on pairs of edges, represented by a so-called conflict graph, seems 
%to make the problem significantly harder. To be more precise, the 
%minimum spanning tree problem with conflict graph (MSTCG) turns out 
%to be strongly $\mathcal{NP}$-hard, even if the connected components of the 
%conflict graph are paths of length two. 
%However, if we restrict the problem to conflict graphs in which each 
%connected component consists of exactly one edge (i.e.\ the conflict 
%graph represents pairwise disjoint forbidden pairs of edges of $G$), 
%then MSTCG is solvable in polynomial time. 
%In contrast to this result, 
%the shortest path problem with pairwise disjoint forbidden pairs of edges 
%is known to be strongly $\mathcal{NP}$-hard~\cite{gj79}. 
%The key feature 
%that indicates the respective computational complexity of these two 
%problems seems to be that the former problem can be formulated as 
%a weighted matroid intersection problem of two matroids, whereas such 
%a representation does not exist for the latter (unless $\mathcal{P}=\mathcal{NP}$).

%%%%%%%5
\newpage

\bibliographystyle{plain} 
\bibliography{MSTCONF}

\end{document}