Search

We show that the number of conjugacy classes of intersections $A\cap B^g$, for fixed finitely generated subgroups $A, B

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph $G$ and a set of terminal pairs $P$ and asks whether $G$ contains a set of pairwise edge-disjoint paths connecting every terminal pair in $P$. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in $P$ in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size $3$. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.

In this thesis we introduce a Monge–Amp`ere iteration to be a sequence of convex functions {ϕi}i∈N which solve the sequence of Monge–Amp`ere equations det(∇2ϕi+1) = h ◦ ϕi with second boundary values ∇ϕi+1(Rn) = A where h is a function of one variable and A is a bounded, convex set. Our main analytic theorem gives sufficient conditions on the function h and the set A so that a Monge– Amp`ere iteration {ϕi}, once correctly normalized, converges smoothly on compact sets to a convex solution of the Monge–Amp`ere equation det(∇2ϕ) = h ◦ ϕ with second boundary value ∇ϕ(Rn) = A. Monge–Amp`ere iterations {ϕi}i∈N arise as a sequence of solutions to optimal transport problems, so our convergence result can be interpreted as breaking apart the Monge–Amp`ere equation det(∇2ϕ) = h◦ϕ, ∇ϕ(Rn) = A into a sequence of optimal transport problems. We then turn to two geometric applications of our main theorem. The first application, when h(t) = e−t, is to Ricci iteration, which was introduced by Rubinstein. We prove a sequence {ωi}i∈N of toric Ka¨hler metrics with fixed edge singularities solving the K¨ahler–Ricci iteration on a toric Fano manifold converges, after being twisted by automorphisms, to a Ka¨hler–Einstein metric with the same singularities. This extends the smooth K¨ahler–Ricci iteration convergence theorem of Darvas–Rubinstein [12] to edge metrics on toric Fano manifolds. The second geometric application, when h(t) = t−(n+2), is to affine differential geometry. We introduce the affine iteration to be a sequence of graph immersions fi : Rn ,→ Rn+1 such that the affine normal at fi+1(x) is a constant multiple of the position vector fi(x). Thus, the affine iteration is a sequence of prescribed affine normal problems. We prove for any affine iteration {fi}i∈N there exists a sequence of matrices Mi ∈ Sln+1R such that {Mi ·fi(Rn)} converges smoothly to an affine sphere.

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as an approximation algorithm for computing the parameter.