Source author record

Annabell Berger

Annabell Berger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO Mathematical Software

Catalog footprint

What is connected

5works

4topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Marathon: An open source software library for the analysis of Markov-Chain Monte Carlo algorithms

In this paper, we consider the Markov-Chain Monte Carlo (MCMC) approach for random sampling of combinatorial objects. The running time of such an algorithm depends on the total mixing time of the underlying Markov chain and is unknown in general. For some Markov chains, upper bounds on this total mixing time exist but are too large to be applicable in practice. We try to answer the question, whether the total mixing time is close to its upper bounds, or if there is a significant gap between them. In doing so, we present the software library marathon which is designed to support the analysis of MCMC based sampling algorithms. The main application of this library is to compute properties of so-called state graphs which represent the structure of Markov chains. We use marathon to investigate the quality of several bounding methods on four well-known Markov chains for sampling perfect matchings and bipartite graph realizations. In a set of experiments, we compute the total mixing time and several of its bounds for a large number of input instances. We find that the upper bound gained by the famous canonical path method is several magnitudes larger than the total mixing time and deteriorates with growing input size. In contrast, the spectral bound is found to be a precise approximation of the total mixing time.

preprint2014arXiv

Broder's Chain Is Not Rapidly Mixing

We prove that Broder's Markov chain for approximate sampling near-perfect and perfect matchings is not rapidly mixing for Hamiltonian, regular, threshold and planar bipartite graphs, filling a gap in the literature. In the second part we experimentally compare Broder's chain with the Markov chain by Jerrum, Sinclair and Vigoda from 2004. For the first time, we provide a systematic experimental investigation of mixing time bounds for these Markov chains. We observe that the exact total mixing time is in many cases significantly lower than known upper bounds using canonical path or multicommodity flow methods, even if the structure of an underlying state graph is known. In contrast we observe comparatively tighter upper bounds using spectral gaps.

preprint2014arXiv

The Connection between the Number of Realizations for Degree Sequences and Majorization

The \emph{graph realization problem} is to find for given nonnegative integers $a_1,\dots,a_n$ a simple graph (no loops or multiple edges) such that each vertex $v_i$ has degree $a_i.$ Given pairs of nonnegative integers $(a_1,b_1),\dots,(a_n,b_n),$ (i) the \emph{bipartite realization problem} ask whether there is a bipartite graph (no loops or multiple edges) such that vectors $(a_1,...,a_n)$ and $(b_1,...,b_n)$ correspond to the lists of degrees in the two partite sets, (ii) the \emph{digraph realization problem} is to find a digraph (no loops or multiple arcs) such that each vertex $v_i$ has indegree $a_i$ and outdegree $b_i.$\\ The classic literature provides characterizations for the existence of such realizations that are strongly related to the concept of majorization. Aigner and Triesch (1994) extended this approach to a more general result for graphs, leading to an efficient realization algorithm and a short and simple proof for the Erdős-Gallai Theorem. We extend this approach to the bipartite realization problem and the digraph realization problem.\\ Our main result is the connection between majorization and the number of realizations for a degree list in all three problems. We show: if degree list $S'$ majorizes $S$ in a certain sense, then $S$ possesses more realizations than $S'.$ We prove that constant lists possess the largest number of realizations for fixed $n$ and a fixed number of arcs $m$ when $n$ divides $m.$ So-called \emph{minconvex lists} for graphs and bipartite graphs or \emph{opposed minconvex lists} for digraphs maximize the number of realizations when $n$ does not divide $m$.

preprint2012arXiv

How to Attack the NP-complete Dag Realization Problem in Practice

We study the following fundamental realization problem of directed acyclic graphs (dags). Given a sequence S:=(a_1,b_1),...,(a_n, b_n) with a_i, b_i in Z_0^+, does there exist a dag (no parallel arcs allowed) with labeled vertex set V:= {v_1,...,v_n} such that for all v_i in V indegree and outdegree of v_i match exactly the given numbers a_i and b_i, respectively? Recently this decision problem has been shown to be NP-complete by Nichterlein (2011). However, we can show that several important classes of sequences are efficiently solvable. In previous work (Berger and Mueller-Hannemann, FCT2011), we have proved that yes-instances always have a special kind of topological order which allows us to reduce the number of possible topological orderings in most cases drastically. This leads to an exact exponential-time algorithm which significantly improves upon a straightforward approach. Moreover, a combination of this exponential-time algorithm with a special strategy gives a linear-time algorithm. Interestingly, in systematic experiments we observed that we could solve a huge majority of all instances by the linear-time heuristic. This motivates us to develop characteristics like dag density and "distance to provably easy sequences" which can give us an indicator how easy or difficult a given sequence can be realized. Furthermore, we propose a randomized algorithm which exploits our structural insight on topological sortings and uses a number of reduction rules. We observe that it clearly outperforms all other variants and behaves surprisingly well for almost all instances. Another striking observation is that our simple linear-time algorithm solves a set of real-world instances from different domains, namely ordered binary decision diagrams (OBDDs), train and flight schedules, as well as instances derived from food-web networks without any exception.

preprint2010arXiv

Uniform sampling of undirected and directed graphs with a fixed degree sequence

Many applications in network analysis require algorithms to sample uniformly at random from the set of all graphs with a prescribed degree sequence. We present a Markov chain based approach which converges to the uniform distribution of all realizations for both the directed and undirected case. It remains an open challenge whether these Markov chains are rapidly mixing. For the case of directed graphs, we also explain in this paper that a popular switching algorithm fails in general to sample uniformly at random because the state graph of the Markov chain decomposes into different isomorphic components. We call degree sequences for which the state graph is strongly connected arc swap sequences. To handle arbitrary degree sequences, we develop two different solutions. The first uses an additional operation (a reorientation of induced directed 3-cycles) which makes the state graph strongly connected, the second selects randomly one of the isomorphic components and samples inside it. Our main contribution is a precise characterization of arc swap sequences, leading to an efficient recognition algorithm. Finally, we point out some interesting consequences for network analysis.