% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\newenvironment{proof}{\textbf{Proof}$\;$}{\hfill\qed}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{On finding a minimum weight cycle basis with cycles of bounded length}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[1]{Edoardo Amaldi},
\author[2]{Bernard Fortz},
\author[1]{Claudio Iuliano}

\address[1]{Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy\\ {\tt \{amaldi,iuliano\}@elet.polimi.it}}
\address[2]{D\'epartement d'Informatique, Facult\'e des Sciences, Universit\'e Libre de Bruxelles, Bruxelles, Belgium\\ {\tt bernard.fortz@ulb.ac.be}}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
undirected graphs \sep cycle basis \sep cycle \sep bounded length
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}\label{sec:introduction}

Consider a connected undirected graph $G = (V,E)$ without loops
and multiple edges. Let $n=|V|$ and $m=|E|$ be respectively the
number of vertices and edges. A generalized cycle is a subset of
edges $C \subseteq E$ such that every vertex of $V$ is incident to
an even number of edges in $C$. All the cycles of $G$ form a
vector space, the so-called \emph{cycle space}. Given an
undirected graph $G$ with a nonnegative weight $w_e$ assigned to
each edge $e \in E$, the \emph{Minimum Cycle Basis} problem
consists in finding a \emph{cycle basis} $\mathcal{C}$ of minimum
total weight $w(\mathcal{C})=\sum_{C \in \mathcal{C}} w(C)$, where
the weight of a cycle is defined as $w(C)=\sum_{e \in C} w_e$.
This problem has been extensively studied, both from the
algorithmic and the structural point of views. See the most recent
works~\cite{ESA09,IPCO10}, the survey~\cite{SurveyCycleBases} and
the references therein.

In this work, we investigate an interesting and natural variant, that
we refer to as the \emph{Minimum cycle basis with cycles of bounded
  length} problem. Given an undirected graph $G$ with a nonnegative
weight $w_e$ and a nonnegative length $l_e$ assigned to each edge $e
\in E$ and a positive integer $L$, we wish to find a minimum (weight)
cycle basis where each cycle $C$ has a length $l(C)=\sum_{e \in
  C}{l_e}$ at most $L$.  Without loss of generality we assume
nonnegative integer weights and lengths on all the edges. The special
case in which each cycle must contain at most $k$ edges ($l_e=1$ for
each $e \in E$) is referred to as \emph{Minimum $k$-edge-cycle
  basis}. Cycles with a bounded number of edges naturally arise in a
number of contexts, see for instance~\cite{FL04}, where $k$-edge-cycle
bases play an important role.

\section{Minimum cycle bases with cycles of bounded length}\label{sec:bounded length}

The existence of a cycle basis with cycles of length at most $L$
clearly depends on the value of $L$ and, as also noticed in \cite{HO01}, 
it can be checked in
polynomial time by looking for a cycle basis with a shortest (in
terms of length) longest cycle, see \cite{CGH95} for the
algorithm.
Even if the longest cycle has a length smaller than $L$ it is hard
to find one with minimum total weight.

\begin{prop}
The problem of finding a minimum cycle basis with cycles of bounded length is NP-hard.
\end{prop}

\begin{proof}
We proceed by polynomial-time reduction from the \emph{Partition}
problem, known to be NP-complete~\cite{GJ79}, to the decision
version of the above problem.
In the Partition problem, given a set of $N$ items, each with an
integer size $a_j$, we have to decide whether there exists a
subset $A$ of items such that $\sum_{j \in A} a_j = \frac{1}{2}
\sum_{j=1}^{N} a_j$. For each instance of the Partition problem it
is easy to construct a special instance of the Minimum cycle basis
with cycles of bounded length problem such that the answer to the
former is yes if and only if the answer to the latter is yes. Consider a
graph with $2 N + 1$ vertices $v_1 \ldots v_{2N+1}$ and assume
that they are ordered along a line. For every odd $i$, with $1 \leq
i \leq 2N$, $v_i$ is connected to $v_{i+1}$ by an edge with weight
$a_{(i+1)/2}$ and length $0$ and to $v_{i+2}$ by an edge with
length $a_{(i+1)/2}$ and weight $0$. For every even $i$, with $1
\leq i \leq 2N$, $v_i$ is connected to $v_{i+1}$ by an edge with
both weight and length $0$. The vertices $v_1$ and $v_{2N+1}$ are
also connected by an edge with both weight and length $0$. Hence,
the total number of edges is equal to $3N+1$. Let $W = L =
\frac{1}{2} \sum_{j=1}^{N} a_{j}$. A minimum cycle basis consists
of $N + 1$ cycles: the $N$ smaller cycles with both weight and
length $a_j$ (for a partial total weight $2W$) and the larger
cycle given by the edge joining $v_1$ and $v_{2N+1}$ plus a path
through the other vertices. Finding a cycle basis with total
weight $\leq 3W$ and with cycles whose length is bounded by $L$
corresponds to finding a path with total weight $\leq W$ and
length $\leq L$ from $v_1$ to $v_{2N+1}$ in the above graph
without the edge joining them. This path yields a partition into
nonzero-weight edges and nonzero-length edges that solves the
Partition problem.
\end{proof}

We now show that the Minimum $k$-edge-cycle basis problem, namely
the special case where $l_e = 1$ for each $e \in E$, can be solved
in polynomial time. We adapt Horton's approach~\cite{Hor87} to the
bounded problem. In Horton's algorithm, a polynomial subset of
candidate cycles is generated. For every vertex $x \in V$ and
every edge $e=\{y,z\} \in E$ we consider the cycle $C$ formed by
the union of the two minimum weight paths $p_{xy}$ and $p_{xz}$
from $x$ to the endpoints of $e$, $y$ and $z$, plus the edge $e$
itself, i.e., $C = p_{xy} + p_{xz} + \{y,z\}$. We say that $C$ has 
a representation $(x,\{y,z\})$. The candidate cycles are then
sorted by nondecreasing weight and a minimum cycle basis is given
by the $m-n+1$ lightest independent cycles.

Unfortunately, a minimum $k$-edge-cycle basis is not guaranteed to
be contained in the set of Horton candidate cycles. As an example,
consider the sunflower graph in~\cite[Fig. 7]{SurveyCycleBases}
and assume that the three edges of the internal triangle have
weight equal to $3$ whereas the other edges have weight equal to
$1$. The unique $3$-edge-cycle basis is given by the four
triangles, but the internal one is not a Horton candidate cycle.

The proposition in~\cite{Hor87} stating that given a cycle $C$ in
a minimum cycle basis, for any pair of vertices $u, v \in C$ the
minimum weight path $p_{uv}$ must be contained in $C$, is no
longer valid. 
Denoting by $p_{uv}^l$ the minimum weight path between vertices 
$u$ and $v$ with a most $l$ edges, we have the following result.

\begin{prop}\label{prop:k-Horton}
For any two vertices $u$ and $v$ of a cycle $C$ in a minimum $k$-edge-cycle basis, let $P_1(u,v)$ and $P_2(u,v)$
be the two paths joining vertices $u$ and $v$ in $C$. Given two integers $l_1$ and $l_2$ greater than the number
of edges in $P_1(u,v)$ and $P_2(u,v)$, respectively, and such that $l_1 + l_2 = k$, at least one between
$p_{uv}^{l_1}$ and $p_{uv}^{l_2}$ must be contained in $C$.
\end{prop}
\begin{proof}
Suppose it is not true. Then $C$ can be obtained as the
composition of three cycles $P_1(u,v)+p_{uv}^{l_2}$,
$P_2(u,v)+p_{uv}^{l_1}$, and $p_{uv}^{l_1}+p_{uv}^{l_2}$, all of
lighter weight than $C$ and with a number of edges bounded by $k$.
Thus $C$ cannot be contained in a minimum $k$-edge-cycle basis.
\end{proof}

All the candidate $k$-edge-cycles can be generated by considering
$C = p_{xy}^{l_1} + p_{xz}^{l_2} + \{y,z\}$ for any vertex $x \in
V$, edge $e=\{y,z\} \in E$ and all the $k-2$ possible choices of
positive integers $l_1$ and $l_2$ such that $l_1+l_2 = k-1$, as in \cite{HO01}. This
naive approach can, however, be improved on by exploiting the
notion of \emph{isometric cycle}~\cite{ESA09} for the
unconstrained case. A cycle $C$ is isometric if and only if it
has a representation $(x,\{y,z\})$ for each vertex $x \in C$.

\begin{prop}\label{prop:balanced}
Every isometric cycle $C$ has a representation $(x,\{y,z\})$ for a
certain pair of vertex $x \in V$ and edge $\{y,z\} \in E$ that is
balanced, i.e., such that the difference between the number of
edges in $p_{xy}$ and $p_{xz}$ is $1$ if $C$ has an even number of
edges and $0$ if odd.
\end{prop}

For the lack of space, we cannot report the proof that is based on
the efficient $O(nm)$ procedure for detecting isometric cycles
proposed in~\cite{ESA09}. The above result is also valid for
cycles with at most $k$ edges. Indeed, we only need to generate the candidate
$k$-edge-cycles $C = p_{xy}^{l_1} + p_{xz}^{l_2} + \{y,z\}$ for
every vertex $x \in V$ and edge $e=\{y,z\}$, for a choice of $l_1$
and $l_2$ leading to a balanced representation, if it exists.
In this set of
$O(nm)$ candidate $k$-edge-cycles, each cycle has a length of at
most $k$. Since $k$ is a constant, the total number of edges in
all these cycles is $O(nm)$. Thus, by using the improved
independence test recently proposed in~\cite{IPCO10}, we obtain an
$O(m^2 n / \log n)$ deterministic algorithm like for the
unconstrained case. The independence test is inspired by de Pina's
method~\cite{dePina95}, that maintains at each step a basis of the
linear space that is orthogonal to the subspace spanned by the
cycles selected so far. It takes advantage of the divide and
conquer scheme presented in~\cite{KMMP08} and uses a bit packing
technique that exploits the sparseness property, namely the fact
that the number of edges in all the candidate cycles is $O(nm)$.

Finally, it is worth pointing out that, although de Pina's algorithm~\cite{dePina95}
(improved in~\cite{KMMP08}) can be easily adapted to solve Minimum
$k$-edge-cycle basis problem by just considering minimum weight paths with
at most $k$ edges, it leads to a worse $O(m^2 n + m n^2
\log n)$ complexity.


% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\bibliographystyle{abbrv}

\begin{thebibliography}{10}

\bibitem{ESA09}
E.~Amaldi, C.~Iuliano, T.~Jurkiewicz, K.~Mehlhorn, and R.~Rizzi.
\newblock Breaking the \mbox{$O(m^2 n)$} barrier for minimum cycle bases.
\newblock In A.~Fiat and P.~Sanders, editors, {\em ESA}, volume 5757 of {\em
  LNCS}, pages 301--312. Springer, 2009.

\bibitem{IPCO10}
E.~Amaldi, C.~Iuliano, and R.~Rizzi.
\newblock Efficient deterministic algorithms for finding a minimum cycle basis
  in undirected graphs.
\newblock In F.~Eisenbrand and B.~Shepherd, editors, {\em Integer Programming and Combinatorial Optimization (IPCO)}, volume 6080 of {\em
  LNCS}, pages 397--410. Springer, 2010.

\bibitem{CGH95}
D.~M. Chickering, D.~Geiger, and D.~Heckerman.
\newblock On finding a cycle basis with a shortest maximal cycle.
\newblock {\em Inf. Process. Lett.}, 54(1):55--58, 1995.

\bibitem{dePina95}
J.~C. De~Pina.
\newblock {\em Applications of shortest path methods}.
\newblock PhD thesis, University of Amsterdam, The Netherlands, 1995.

\bibitem{FL04}
B.~Fortz and M.~Labb\'e.
\newblock Two-connected networks with rings of bounded cardinality.
\newblock {\em Computational Optimization and Applications}, 27(2):123--148,
  2004.


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

\bibitem{HO01}
D.~S. Hochbaum and E.~V. Olinick.
\newblock The bounded cycle-cover problem.
\newblock {\em INFORMS J. on Computing}, 13(2):104--119, 2001.

\bibitem{Hor87}
J.~D. Horton.
\newblock A polynomial-time algorithm to find the shortest cycle basis of a
  graph.
\newblock {\em SIAM J. Computing}, 16(2):358--366, 1987.

\bibitem{SurveyCycleBases}
T.~Kavitha, C.~Liebchen, K.~Mehlhorn, D.~Michail, R.~Rizzi, T.~Ueckerdt, and
  K.~A. Zweig.
\newblock Cycle bases in graphs characterization, algorithms, complexity, and
  applications.
\newblock {\em Computer Science Review}, 3(4):199--243, 2009.

\bibitem{KMMP08}
T.~Kavitha, K.~Mehlhorn, D.~Michail, and K.~E. Paluch.
\newblock An \mbox{$\tilde{O}(m^2 n)$} algorithm for minimum cycle basis of
  graphs.
\newblock {\em Algorithmica}, 52(3):333--349, 2008.

\end{thebibliography}

\end{document}
