We consider the Shortest Odd Path problem, where given an undirected graph G , a weight function on its edges, and two vertices s and t in G , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first FPT algorithm is parameterized by | E − | , the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

Budapest University of Technology and Economics, Magyar tudósok krt 2., Budapest, 1117, Hungary The MTA-ELTE Egerváry Research Group on Combinatorial Optimization, Eötvös Loránd Research Network (ELKH), Pázmány Péter sétány 1/C, Budapest, 1117, Hungary Department of Operations Research, ELTE Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary Department of Mathematics and Statistics, Lancaster University, Lancaster, LA1 4YF, United Kingdom Export Date: 10 June 2022 Correspondence Address: Schulze, B.; Department of Mathematics and Statistics, United Kingdom; email: [email protected]

We consider the following augmentation problem: Given a rigid graph $G=(V,E)$, find a minimum cardinality edge set $F$ such that the graph $G'=(V,E\cup F)$ is globally rigid. We provide a min-max theorem and a polynomial-time algorithm for this problem for several types of rigidity, such as rigidity in the plane or on the cylinder. Rigidity is often characterized by some sparsity properties of the underlying graph, and global rigidity is characterized by redundant rigidity (where the graph remains rigid after deleting an arbitrary edge) and 2- or 3-vertex-connectivity. Hence, to solve the above-mentioned problem, we define and solve polynomially a combinatorial optimization problem family based on these sparsity and connectivity properties. This family also includes the problem of augmenting a $k$-tree-connected graph to a highly $k$-tree-connected and 2-connected graph. Moreover, as an interesting consequence, we give an optimal solution to the so-called global rigidity pinning problem, where we aim to find a minimum cardinality vertex set $X$ for a rigid graph $G=(V,E)$, such that the graph $G+K_X$ is globally rigid in $\mathbb{R}^2$ where $K_X$ denotes the complete graph on the vertex set $X$.

By generalizing the results of [N. Kamiyama, N. Katoh, and A. Takizawa, Combinatorica, 29 (2009), pp. 197--214], we solve the following problem. Given a digraph $D=(V,A)$ and a matroid on a set ${\sf{S}}=\{{\sf{s}}_1,\dots,{\sf{s}}_k\}$ along with a map $\pi:{\sf{S}}\to V$, find $k$ edge-disjoint arborescences $T_1,\dots, T_k$ with roots $\pi({\sf{s}}_1),\dots,\pi({\sf{s}}_k)$, respectively, such that, for any $v\in V$, the set $\{{\sf{s}}_i:v\in T_i\}$ is independent and its rank reaches the theoretical maximum. We also give a simplified proof for a result of [S. Fujishige, Combinatorica, 30 (2010), pp. 247--252].