We consider the problem of computing $$k \in {\mathbb {N}}$$ internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, $$O(\min \{k,\sqrt{n}\}m)$$ for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every $$1 \le k \le \delta $$ (where $$\delta $$ is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last $$\delta -k+2$$ vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time $$O(n+m)$$ , which improves the previously best time $$O(\min \{k,\sqrt{n}\}m)$$ . Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.

Tutte paths are one of the most successful tools for attacking Hamiltonicity problems in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.

Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely min{d(v),d(w)}, where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree delta contains Omega(delta^2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree delta >= 5 or with edge-connectivity lambda >= 4 or with vertex-connectivity kappa >= 3 contains in fact Omega(delta |V|) pendant pairs. We prove that this bound is tight from several perspectives, and that Omega(delta |V|) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter, and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte’s theorem that every 4-connected planar graph is Hamiltonian, as well as Barnette’s theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte’s and Thomassen’s decompositions. We solve this problem by extending the decomposition of Gao, Richter, and Yu in such a way that all pieces into which the graph is decomposed are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk just mentioned. Its running time is O ( n 3 ).

Canonical orderings have been used as a key tool in graph drawing, graph encoding, and visibility representations for the last decades [H. de Fraysseix, J. Pach, and R. Pollack, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC '88), ACM, New York, 1988, pp. 426--433; G. Kant, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), IEEE Press, Piscataway, NJ, 1992, pp. 101--110]. We study a far-reaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a Ph.D. thesis as early as 1971. Mondshein proposed to order the vertices of a graph in a sequence such that for any $i$, the vertices from 1 to $i$ essentially induce a 2-connected graph, while the remaining vertices from $i+1$ to $n$ induce a connected graph. Mondshein's sequence generalizes canonical orderings and later became independently known as nonseparating ear decomposition. Surprisingly, this fundamental link between canonical orderings and nonseparating ear decomposition had not been previously established. Currently, the fastest known algorithm for computing a Mondshein sequence achieves a running time of $O(nm)$; the main open problem in Mondshein's and follow-up work is to improve this running time to subquadratic time. After putting Mondshein's work into context, we present an algorithm that computes a Mondshein sequence in optimal time and space $O(m)$. This improves the previous best running time by a factor of $n$. We illustrate the impact of this result by deducing linear-time algorithms for five other problems---in four of these, the previous best running time was quadratic. In particular, we show how to compute three independent spanning trees in a 3-connected graph in time $O(m)$, improving a result of Cheriyan and Maheshwari [J. Algorithms, 9 (1988), pp. 507--537]; improve the preprocessing time from $O(n^2)$ to $O(m)$ for the output-sensitive data structure of Di Battista, Tamassia, and Vismara [Algorithmica, 23 (1999), pp. 302--340] that reports three internally disjoint paths between any given vertex pair; derive a very simple $O(n)$-time planarity test once a Mondshein sequence is computed; compute a nested family of contractible subgraphs of 3-connected graphs in time $O(m)$; and compute a 3-partition in time $O(m)$ (the previous best running time is $O(n^2)$ due to Suzuki et al. [Information Processing Society of Japan (IPSJ), 31 (1990), pp. 584--592 (in Japanese)]).

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

One of the most noted construction methods of $3$-vertex-connected graphs is due to Tutte and is based on the following fact: Any $3$-vertex-connected graph $G=(V,E)$ on more than $4$ vertices contains a contractible edge, i.e., an edge whose contraction generates a $3$-connected graph. This implies the existence of a sequence of edge contractions from $G$ to the complete graph $K_4$, such that every intermediate graph is $3$-vertex-connected. A theorem of Barnette and Grünbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of $O(|V|^2)$ to $O(|E|)$. This result has a number of consequences; an important one is a new linear-time test of $3$-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time $3$-connectivity tests and uses a certificate that is easy to verify in time $O(|E|)$. We show how to extend the results to an optimal certifying test of $3$-edge-connectivity.

Let P be a set of n ≥ 4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm; the algorithm is constructive and runs in time O(n3). We also show which graph structure can be expected when there is a cubic plane graph on P; e.g., if P admits a 2-connected cubic plane graph, we show that P admits also a 2-connected cubic plane graph that contains the boundary cycle of P. The algorithm extends to checking P on admitting a 2-connected cubic plane graph.

Given two $3$-connected graphs $G$ and $H$, a \emph{construction sequence} constructs $G$ from $H$ (e.\,g. from the $K_4$) with three basic operations, called the \emph{Barnette-Gr\"unbaum operations}. These operations are known to be able to construct all $3$-connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in $G$ and showing under some minor assumptions that there is still a construction sequence to $G$ when we start from an \emph{arbitrary prescribed} $H$-subdivision. This leads to the first algorithm that computes a construction sequence in time $O(|V(G)|^2)$. As an application, we develop a certificate for the $3$-connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on $3$-connectedness is designed.%Finding certifying algorithms is a major goal for problems where the efficient solutions known are complicated. Tutte proved that every $3$-connected graph on more than $4$ nodes has a \emph{contractible edge}. Barnette and Gr\"unbaum proved the existence of a \emph{removable edge} in the same setting. We show that the sequence of contractions and the sequence of removals from $G$ to the $K_4$ can be computed in $O(|V|^2)$ time by extending Barnette and Gr\"unbaum's theorem. As an application, we derive a certificate for the $3$-connectedness of graphs that can be easily computed and verified.

This paper presents results from extensive simulation studies on the iterated prisoner’s dilemma. Two models were implemented: a nongroup model in order to study fundamental principles of cooperation and a model to imitate ethnocentrism. Some extensions of Axelrod’s elementary model implemented individual reputation. We furthermore introduced group reputation to provide a more realistic scenario. In an environment with group reputation the behavior of one agent will affect the reputation of the whole group and vice-versa. While kind agents (e.g. those with a cooperative behavior) lose reputation when being in a group, in which defective strategies are more common, agents with defective behavior on the other hand benefit from a group with more cooperative strategies. We demonstrate that group reputation decreases cooperation with the in-group and increases cooperation with the out-group.

The Prisoner's Dilemma and the Public Goods Game are models to study mechanisms leading to the evolution of cooperation. From a simplified rational and egoistic perspective there should be no altruistic cooperation in these games at all. Previous studies observed circumstances under which cooperation can emerge. This paper demonstrates that high-order punishment opportunities can maintain a higher cooperation level in an agent based simulation of the evolution of cooperation.