Search

Given a graph $G$ and an integer $k$, the $H$-free Edge Deletion problem asks whether there exists a set of at most $k$ edges of $G$ whose deletion makes $G$ free of induced copies of $H$. Significant attention has been given to the kernelizability aspects of this problem -- i.e., for which graphs $H$ does the problem admit an "efficient preprocessing" procedure, known as a polynomial kernelization, where an instance $I$ of the problem with parameter $k$ is reduced to an equivalent instance $I'$ whose size and parameter value are bounded polynomially in $k$? Although such routines are known for many graphs $H$ where the class of $H$-free graphs has significant restricted structure, it is also clear that for most graphs $H$ the problem is incompressible, i.e., admits no polynomial kernelization parameterized by $k$ unless the polynomial hierarchy collapses. These results led Marx and Sandeep to the conjecture that $H$-free Edge Deletion is incompressible for any graph $H$ with at least five vertices, unless $H$ is complete or has at most one edge (JCSS 2022). This conjecture was reduced to the incompressibility of $H$-free Edge Deletion for a finite list of graphs $H$. We consider one of these graphs, which we dub the prison, and show that Prison-Free Edge Deletion has a polynomial kernel, refuting the conjecture. On the other hand, the same problem for the complement of the prison is incompressible.

Deep-learning based traffic prediction models require vast amounts of data to learn embedded spatial and temporal dependencies. The inherent privacy and commercial sensitivity of such data has encouraged a shift towards decentralised data-driven methods, such as Federated Learning (FL). Under a traditional Machine Learning paradigm, traffic flow prediction models can capture spatial and temporal relationships within centralised data. In reality, traffic data is likely distributed across separate data silos owned by multiple stakeholders. In this work, a cross-silo FL setting is motivated to facilitate stakeholder collaboration for optimal traffic flow prediction applications. This work introduces an FL framework, referred to as FedTPS, to generate synthetic data to augment each client's local dataset by training a diffusion-based trajectory generation model through FL. The proposed framework is evaluated on a large-scale real world ride-sharing dataset using various FL methods and Traffic Flow Prediction models, including a novel prediction model we introduce, which leverages Temporal and Graph Attention mechanisms to learn the Spatio-Temporal dependencies embedded within regional traffic flow data. Experimental results show that FedTPS outperforms multiple other FL baselines with respect to global model performance., Comment: 11 pages, 7 figures, 6 tables, ACM format

We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constant even when r=|R|=2, so we focus on parameterized approximability with solution size as the parameter. For a large class of infinite rings R called Euclidean domains, Dabrowski et al. [SODA-2023] obtained an FPT-algorithm for MIN-2-LIN(R) using an LP-based approach based on work by Wahlstr\"om [SODA-2017]. Here, we consider MIN-r-LIN(R) for finite commutative rings R, initiating a line of research with the ultimate goal of proving dichotomy theorems that separate problems that are FPT-approximable within a constant from those that are not. A major motivation is that our project is a promising step for more ambitious classification projects concerning finite-domain MinCSP and VCSP. Dabrowski et al.'s algorithm is limited to rings without zero divisors, which are only fields among finite commutative rings. Handling zero divisors seems to be an insurmountable obstacle for the LP-based approach. In response, we develop a constant-factor FPT-approximation algorithm for a large class of finite commutative rings, called Bergen rings, and thus prove approximability for chain rings, principal ideal rings, and Z_m for all m>1. We complement the algorithmic result with powerful lower bounds. For r>2, we show that the problem is not FPT-approximable within any constant (unless FPT=W[1]). We identify the class of non-Helly rings for which MIN-2-LIN(R) is not FPT-approximable. Under ETH, we also rule out (2-e)-approximation for every e>0 for non-lineal rings, which includes e.g. rings Z_{pq} where p and q are distinct primes. Towards closing the gaps between upper and lower bounds, we lay the foundation of a geometric approach for analysing rings.

This study introduces novel superior scoring rules called Penalized Brier Score (PBS) and Penalized Logarithmic Loss (PLL) to improve model evaluation for probabilistic classification. Traditional scoring rules like Brier Score and Logarithmic Loss sometimes assign better scores to misclassifications in comparison with correct classifications. This discrepancy from the actual preference for rewarding correct classifications can lead to suboptimal model selection. By integrating penalties for misclassifications, PBS and PLL modify traditional proper scoring rules to consistently assign better scores to correct predictions. Formal proofs demonstrate that PBS and PLL satisfy strictly proper scoring rule properties while also preferentially rewarding accurate classifications. Experiments showcase the benefits of using PBS and PLL for model selection, model checkpointing, and early stopping. PBS exhibits a higher negative correlation with the F1 score compared to the Brier Score during training. Thus, PBS more effectively identifies optimal checkpoints and early stopping points, leading to improved F1 scores. Comparative analysis verifies models selected by PBS and PLL achieve superior F1 scores. Therefore, PBS and PLL address the gap between uncertainty quantification and accuracy maximization by encapsulating both proper scoring principles and explicit preference for true classifications. The proposed metrics can enhance model evaluation and selection for reliable probabilistic classification., Comment: 21 Pages, 3 Figures, 3 Tables

We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist representation" up to $O(n^\omega)$-time transformations, but is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to the problem of finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions over linear delta-matroids. We show that the union and delta-sum of linear delta-matroids define linear delta-matroids, and a representation for the resulting delta-matroid can be constructed in randomized time $O(n^\omega)$. Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single $O(n^{\omega})$-time matrix rank computation. Using the methods of Harvey, previously used by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the $O(n^4)$-time augmenting path algorithm of Geelen, Iwata and Murota. Finally, we consider the maximum-cardinality delta-matroid intersection problem. Using Storjohann's algorithms for symbolic determinants, we show that such a solution can be found in $O(n^{\omega+1})$ time. This is the first polynomial-time algorithm for the problem, solving an open question of Kakimura and Takamatsu.

The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form $x < y$, $x = y$, $x \leq y$ and $x \neq y$, and a budget $k$. The goal is to check whether it is possible to assign rational values to the variables while breaking constraints of total cost at most $k$. This problem generalizes several prominent graph separation and transversal problems: MinCSP$(<)$ is equivalent to Directed Feedback Arc Set, MinCSP$(<,\leq)$ is equivalent to Directed Subset Feedback Arc Set, MinCSP$(=,\neq)$ is equivalent to Edge Multicut, and MinCSP$(\leq,\neq)$ is equivalent to Directed Symmetric Multicut. Apart from trivial cases, MinCSP$(\Gamma)$ for $\Gamma \subseteq \{<,=,\leq,\neq\}$ is NP-hard even to approximate within any constant factor under the Unique Games Conjecture. Hence, we study parameterized complexity of this problem under a natural parameterization by the solution cost $k$. We obtain a complete classification: if $\Gamma \subseteq \{<,=,\leq,\neq\}$ contains both $\leq$ and $\neq$, then MinCSP$(\Gamma)$ is W[1]-hard, otherwise it is fixed-parameter tractable. For the positive cases, we solve MinCSP$(<,=,\neq)$, generalizing the FPT results for Directed Feedback Arc Set and Edge Multicut as well as their weighted versions. Our algorithm works by reducing the problem into a Boolean MinCSP, which is in turn solved by flow augmentation. For the lower bounds, we prove that Directed Symmetric Multicut is W[1]-hard, solving an open problem.

Generative adversarial networks constitute a powerful approach to generative modeling. While generated samples often are indistinguishable from real data, there is no guarantee that they will follow the true data distribution. For scientific applications in particular, it is essential that the true distribution is well captured by the generated distribution. In this work, we propose a method to ensure that the distributions of certain generated data statistics coincide with the respective distributions of the real data. In order to achieve this, we add a new loss term to the generator loss function, which quantifies the difference between these distributions via suitable f-divergences. Kernel density estimation is employed to obtain representations of the true distributions, and to estimate the corresponding generated distributions from minibatch values at each iteration. When compared to other methods, our approach has the advantage that the complete shapes of the distributions are taken into account. We evaluate the method on a synthetic dataset and a real-world dataset and demonstrate improved performance of our approach.

We present representative sets-style statements for linear delta-matroids, which are set systems that generalize matroids, with important connections to matching theory and graph embeddings. Furthermore, our proof uses a new approach of sieving polynomial families, which generalizes the linear algebra approach of the representative sets lemma to a setting of bounded-degree polynomials. The representative sets statements for linear delta-matroids then follow by analyzing the Pfaffian of the skew-symmetric matrix representing the delta-matroid. Applying the same framework to the determinant instead of the Pfaffian recovers the representative sets lemma for linear matroids. Altogether, this significantly extends the toolbox available for kernelization. As an application, we show an exact sparsification result for Mader networks: Let $G=(V,E)$ be a graph and $\mathcal{T}$ a partition of a set of terminals $T \subseteq V(G)$, $|T|=k$. A $\mathcal{T}$-path in $G$ is a path with endpoints in distinct parts of $\mathcal{T}$ and internal vertices disjoint from $T$. In polynomial time, we can derive a graph $G'=(V',E')$ with $T \subseteq V(G')$, such that for every subset $S \subseteq T$ there is a packing of $\mathcal{T}$-paths with endpoints $S$ in $G$ if and only if there is one in $G'$, and $|V(G')|=O(k^3)$. This generalizes the (undirected version of the) cut-covering lemma, which corresponds to the case that $\mathcal{T}$ contains only two blocks. To prove the Mader network sparsification result, we furthermore define the class of Mader delta-matroids, and show that they have linear representations. This should be of independent interest.

We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as $\mathbb{N}$, where the relations are defined via first-order formulas whose only predicate is $=$. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP$(\Gamma)$ for every finite equality language $\Gamma$, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the ``cut requests'' come as disjunctions over $d = O(1)$ individual cut requests $s_i \neq t_i$. We also consider singleton expansions of equality languages, i.e., enriching an equality language with the capability for assignment constraints $(x=i)$ for either finitely or infinitely many constants $i \in \mathbb{N}$, and fully characterize the complexity of the resulting MinCSP.

We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial $P(X)$ on a set of variables $X=\{x_1,\ldots,x_n\}$ and a linear matroid $M=(X,\mathcal{I})$ of rank $k$, both over a field $\mathbb{F}$ of characteristic 2, in $2^k$ evaluations we can sieve for those terms in the monomial expansion of $P$ which are multilinear and whose support is a basis for $M$. Alternatively, using $2^k$ evaluations of $P$ we can sieve for those monomials whose odd support spans $M$. Applying this framework, we improve on a range of algebraic FPT algorithms, such as: 1. Solving $q$-Matroid Intersection in time $O^*(2^{(q-2)k})$ and $q$-Matroid Parity in time $O^*(2^{qk})$, improving on $O^*(4^{qk})$ over general fields (Brand and Pratt, ICALP 2021) 2. $T$-Cycle, Colourful $(s,t)$-Path, Colourful $(S,T)$-Linkage in undirected graphs, and the more general Rank $k$ $(S,T)$-Linkage problem, all in $O^*(2^k)$ time, improving on $O^*(2^{k+|S|})$ and $O^*(2^{|S|+O(k^2 \log(k+|\mathbb{F}|))})$ respectively (Fomin et al., SODA 2023) 3. Many instances of the Diverse X paradigm, finding a collection of $r$ solutions to a problem with a minimum mutual distance of $d$ in time $O^*(2^{r(r-1)d/2})$, improving solutions for $k$-Distinct Branchings from time $2^{O(k \log k)}$ to $O^*(2^k)$ (Bang-Jensen et al., ESA 2021), and for Diverse Perfect Matchings from $O^*(2^{2^{O(rd)}})$ to $O^*(2^{r^2d/2})$ (Fomin et al., STACS 2021) Here, all matroids are assumed to be represented over fields of characteristic 2. Over general fields, we achieve similar results at the cost of using exponential space by working over the exterior algebra. For a class of arithmetic circuits we call strongly monotone, this is even achieved without any loss of running time. However, the odd support sieving result appears to be specific to working over characteristic 2.

Kernel principal component analysis (kPCA) is a widely studied method to construct a low-dimensional data representation after a nonlinear transformation. The prevailing method to reconstruct the original input signal from kPCA -- an important task for denoising -- requires us to solve a supervised learning problem. In this paper, we present an alternative method where the reconstruction follows naturally from the compression step. We first approximate the kernel with random Fourier features. Then, we exploit the fact that the nonlinear transformation is invertible in a certain subdomain. Hence, the name \emph{invertible kernel PCA (ikPCA)}. We experiment with different data modalities and show that ikPCA performs similarly to kPCA with supervised reconstruction on denoising tasks, making it a strong alternative., Comment: This work has been submitted to the IEEE for possible publication

Physics-informed neural networks (PINNs) constitute a flexible approach to both finding solutions and identifying parameters of partial differential equations. Most works on the topic assume noiseless data, or data contaminated with weak Gaussian noise. We show that the standard PINN framework breaks down in case of non-Gaussian noise. We give a way of resolving this fundamental issue and we propose to jointly train an energy-based model (EBM) to learn the correct noise distribution. We illustrate the improved performance of our approach using multiple examples.

One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterized complexity. In this note we explore applicability of flow-augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following. -- In weighted undirected graphs \textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an oracle access to group operations. -- The weighted version of \textsc{Directed Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed Symmetric Multicut} as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting., Comment: 17 pages, 1 figure

We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a set $X \subseteq V(D)$ of size at most $k$ such that for every $1 \leq i \leq \ell$, $X$ intersects either all $(s_i,t_i)$-paths or all $(t_i,s_i)$-paths. Equivalently, every strongly connected component of $D-X$ contains at most one vertex out of $s_i$ and $t_i$ for every $i$. This problem is previously known from research in approximation algorithms, where it is known to have an $O(\log k \log \log k)$-approximation. We note that the problem, parameterized by $k$, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by $k$, but we give three partial results: An FPT algorithm parameterized by $k+\ell$; an FPT-time 2-approximation parameterized by $k$; and an FPT algorithm parameterized by $k$ for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by $k$ remains an intriguing open possibility., Comment: A shortened version of this article has been accepted for presentation and publication at The 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains - a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers, and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.

We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\Gamma$, with or without weights. More precisely, for each finite Boolean constraint language $\Gamma$, we consider the following two problems. In Min SAT$(\Gamma)$, the input is a formula $F$ over $\Gamma$ and an integer $k$, and the task is to find an assignment $\alpha \colon V(F) \to \{0,1\}$ that satisfies all but at most $k$ constraints of $F$, or determine that no such assignment exists. In Weighted Min SAT$(\Gamma$), the input additionally contains a weight function $w \colon F \to \mathbb{Z}_+$ and an integer $W$, and the task is to find an assignment $\alpha$ such that (1) $\alpha$ satisfies all but at most $k$ constraints of $F$, and (2) the total weight of the violated constraints is at most $W$. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language $\Gamma$, either Weighted Min SAT$(\Gamma)$ is FPT; or Weighted Min SAT$(\Gamma)$ is W[1]-hard but Min SAT$(\Gamma)$ is FPT; or Min SAT$(\Gamma)$ is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages $\Gamma$ that cannot express implications $(u \to v)$ (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted $\ell$-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation (Kim et al., STOC 2022)., Comment: v2. Major update to all three flow-augmentation papers

Machine learning models can be improved by adapting them to respect existing background knowledge. In this paper we consider multitask Gaussian processes, with background knowledge in the form of constraints that require a specific sum of the outputs to be constant. This is achieved by conditioning the prior distribution on the constraint fulfillment. The approach allows for both linear and nonlinear constraints. We demonstrate that the constraints are fulfilled with high precision and that the construction can improve the overall prediction accuracy as compared to the standard Gaussian process.

An instance $I$ of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in $I$ is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of $I$. Boehmer et al. (2021) designed a polynomial-time algorithm to find the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most $k$ swaps are enough to turn $I$ into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by $k$ is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph $G$, two vertices $s,t \in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal $st$-cut $Z$ in $G$ of size at most $k$, with probability $2^{-\mathrm{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted $st$-Cut} or Weighted Directed Feedback Vertex Set. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph $H$, if the List $H$-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable., Comment: v2. Major update of three flow-augmentation papers. Includes a deterministic version. Weighted Almost 2-SAT algorithm has been removed, as it is superseded by a more general algorithm of Flow-Augmentation III (arXiv:2207.07422)

We propose a model for hierarchical structured data as an extension to the stochastic temporal convolutional network. The proposed model combines an autoregressive model with a hierarchical variational autoencoder and downsampling to achieve superior computational complexity. We evaluate the proposed model on two different types of sequential data: speech and handwritten text. The results are promising with the proposed model achieving state-of-the-art performance.

Magnonic crystals are magnetic metamaterials, that provide a promising way to manipulate magnetodynamic properties by controlling the geometry of the patterned structures. Here, we study the magnetodynamic properties of 1D magnonic crystals consisting of parallel NiFe strips with different strip widths and separations. The strips couple via dipole-dipole interactions. As an alternative to experiments and/or micromagnetic simulations, we investigate the accuracy of a simple macrospin model. For the case of simple strips, a model with a single free parameter to account for an overestimation of the out-of-plane demagnetization of the magnonic lattice is described. By adjusting this parameter a good fit with experimental as well as micromagnetic results is obtained. Moreover, the Gilbert damping is found independent of the lattice constant however the inhomogeneous linewidth broadening found to increase with decreasing stripe separation.

Let $G$ be a graph and $S, T \subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S \cup T \subseteq V(H)$ and such that for every $A \subseteq S$ and $B \subseteq T$ the size of a minimum $(A,B)$-vertex cut is the same in $G$ as in $H$. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlstr\"om (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier $H$ with $O(k^3)$ vertices can be computed in randomized polynomial time, even for arbitrary digraphs $G$. However, since then, no improvements on the size $O(k^3)$ have been shown. In this paper, we draw inspiration from the renowned Bollob\'as's Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlstr\"om's methods. This new perspective allows us to construct a sparsifier $H$ of $\Theta(k^2)$ vertices for the case that $G$ is a DAG. We also show how to compute $H$ in time near-linear in the size of $G$, improving on the previous $O(n^{\omega+1})$. Furthermore, $H$ recovers the closest min-cut in $G$ for every partition $(A,B)$, which was not previously known. Finally, we show that a sparsifier of size $\Omega(k^2)$ is required, both for DAGs and for undirected edge cuts.

Fifteen years have passed since the publication of Foxlin's seminal paper "Pedestrian tracking with shoe-mounted inertial sensors". In addition to popularizing the zero-velocity update, Foxlin also hinted that the optimal parameter tuning of the zero-velocity detector is dependent on, for example, the user's gait speed. As demonstrated by the recent influx of related studies, the question of how to properly design a robust zero-velocity detector is still an open research question. In this review, we first recount the history of foot-mounted inertial navigation and characterize the main sources of error, thereby motivating the need for a robust solution. Following this, we systematically analyze current approaches to robust zero-velocity detection, while categorizing public code and data. The article concludes with a discussion on commercialization along with guidance for future research.

We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph $G$ with distinguished vertices $s,t \in V(G)$ and an integer $k$, one can in randomized $k^{O(1)} \cdot (|V(G)| + |E(G)|)$ time sample a set $A \subseteq \binom{V(G)}{2}$ such that the following holds: for every inclusion-wise minimal $st$-cut $Z$ in $G$ of cardinality at most $k$, $Z$ becomes a minimum-cardinality cut between $s$ and $t$ in $G+A$ (i.e., in the multigraph $G$ with all edges of $A$ added) with probability $2^{-O(k \log k)}$. Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability ($2^{-O(k \log k)}$ instead of $2^{-O(k^4 \log k)}$), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective $st$-Cut problem can be solved in randomized FPT time $2^{O(k \log k)} (|V(G)|+|E(G)|)$ on undirected graphs., Comment: v2. Major update of all three flow-augmentation papers. The partial dichotomy part has been removed from this work, as it is superseded by the full dichotomy of Flow-Augmentation III (arXiv:2207.07422)

We study the Many Visits TSP problem, where given a number $k(v)$ for each of $n$ cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city $v$ exactly $k(v)$ times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space $\mathcal{O}^*(5^n)$. They also show a polynomial space algorithm running in time $\mathcal{O}^*(16^{n+o(n)})$. In this work, we show three main results: (i) A randomized polynomial space algorithm in time $\mathcal{O}^*(2^nD)$, where $D$ is the maximum distance between two cities. By using standard methods, this results in $(1+\epsilon)$-approximation in time $\mathcal{O}^*(2^n\epsilon^{-1})$. Improving the constant $2$ in these results would be a major breakthrough, as it would result in improving the $\mathcal{O}^*(2^n)$-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. (ii) A tight analysis of Berger et al.'s exponential space algorithm, resulting in $\mathcal{O}^*(4^n)$ running time bound. (iii) A new polynomial space algorithm, running in time $\mathcal{O}(7.88^n)$.

Deep state space models (SSMs) are an actively researched model class for temporal models developed in the deep learning community which have a close connection to classic SSMs. The use of deep SSMs as a black-box identification model can describe a wide range of dynamics due to the flexibility of deep neural networks. Additionally, the probabilistic nature of the model class allows the uncertainty of the system to be modelled. In this work a deep SSM class and its parameter learning algorithm are explained in an effort to extend the toolbox of nonlinear identification methods with a deep learning based method. Six recent deep SSMs are evaluated in a first unified implementation on nonlinear system identification benchmarks.

We show the existence of an exact mimicking network of $k^{O(\log k)}$ edges for minimum multicuts over a set of terminals in an undirected graph, where $k$ is the total capacity of the terminals, as well as a method for computing a mimicking network of quasipolynomial size in polynomial time. As a consequence of the latter, several problems are shown to have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution and the number of cut requests. The result combines the matroid-based irrelevant edge approach used in the kernel for $s$-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for $s$-Multiway Cut for constant value of $s$ (Kratsch and Wahlstr\"om, FOCS 2012)., Comment: Updated version with simplified proof and new constructive result

Magneto-inductive navigation is an inexpensive and easily deployable solution to many of today's navigation problems. By utilizing very low frequency magnetic fields, magneto-inductive technology circumvents the problems with attenuation and multipath that often plague competing modalities. Using triaxial transmitter and receiver coils, it is possible to compute position and orientation estimates in three dimensions. However, in many situations, additional information is available that constrains the set of possible solutions. For example, the receiver may be known to be coplanar with the transmitter, or orientation information may be available from inertial sensors. We employ a maximum a posteriori estimator to fuse magneto-inductive signals with such complementary information. Further, we derive the Cramer-Rao bound for the position estimates and investigate the problem of detecting distortions caused by ferrous material. The performance of the estimator is compared to the Cramer-Rao bound and a state-of-the-art estimator using both simulations and real-world data. By fusing magneto-inductive signals with accelerometer measurements, the median position error is reduced almost by a factor of two.

Visual odometry shows excellent performance in a wide range of environments. However, in visually-denied scenarios (e.g. heavy smoke or darkness), pose estimates degrade or even fail. Thermal cameras are commonly used for perception and inspection when the environment has low visibility. However, their use in odometry estimation is hampered by the lack of robust visual features. In part, this is as a result of the sensor measuring the ambient temperature profile rather than scene appearance and geometry. To overcome this issue, we propose a Deep Neural Network model for thermal-inertial odometry (DeepTIO) by incorporating a visual hallucination network to provide the thermal network with complementary information. The hallucination network is taught to predict fake visual features from thermal images by using Huber loss. We also employ selective fusion to attentively fuse the features from three different modalities, i.e thermal, hallucination, and inertial features. Extensive experiments are performed in hand-held and mobile robot data in benign and smoke-filled environments, showing the efficacy of the proposed model., Comment: Accepted to IEEE Robotics and Automation Letters (RAL)

Recent developments within deep learning are relevant for nonlinear system identification problems. In this paper, we establish connections between the deep learning and the system identification communities. It has recently been shown that convolutional architectures are at least as capable as recurrent architectures when it comes to sequence modeling tasks. Inspired by these results we explore the explicit relationships between the recently proposed temporal convolutional network (TCN) and two classic system identification model structures; Volterra series and block-oriented models. We end the paper with an experimental study where we provide results on two real-world problems, the well-known Silverbox dataset and a newer dataset originating from ground vibration experiments on an F-16 fighter aircraft., Comment: Accepted to Conference on Decision and Control, The first two authors contributed equally