Search

A matching cut is a matching that is also an edge cut. In the problem Minimum Matching Cut, we ask for a matching cut with the minimum number of edges in the matching. We give polynomial-time algorithms for $P_7$-free, $S_{1,1,2}$-free and $(P_6 + P_4)$-free graphs, which also solve several open cases for the well-studied problem Matching Cut. In addition, we show NP-hardness for $3P_3$-free graphs, implying that Minimum Matching Cut and Matching Cut differ in complexity on certain graph classes. We also give complexity dichotomies for both general and bipartite graphs of bounded radius and diameter.

Wood species identification plays a crucial role in various industries, from ensuring the legality of timber products to advancing ecological conservation efforts. This paper introduces WoodYOLO, a novel object detection algorithm specifically designed for microscopic wood fiber analysis. Our approach adapts the YOLO architecture to address the challenges posed by large, high-resolution microscopy images and the need for high recall in localization of the cell type of interest (vessel elements). Our results show that WoodYOLO significantly outperforms state-of-the-art models, achieving performance gains of 12.9% and 6.5% in F2 score over YOLOv10 and YOLOv7, respectively. This improvement in automated wood cell type localization capabilities contributes to enhancing regulatory compliance, supporting sustainable forestry practices, and promoting biodiversity conservation efforts globally.

Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al.,2022]. In that light, we wonder about other types of queries, which are of particular interest to bioinformatics: the search for the longest repeating factor, unique substrings, absent words, anti-powers, and longest previous factors. While we obtain a polynomial time algorithm for the first problem on ED strings, we show that all others are NP-hard to compute, some of them even under the restriction that the input can be modelled as an indeterminate or GD string.

In order to truly understand how social media might shape online discourses or contribute to societal polarization, we need refined models of platform choice, that is: models that help us understand why users prefer one social media platform over another. This study develops a dynamic model of platform selection, extending Social Feedback Theory by incorporating multi-agent reinforcement learning to capture how user decisions are shaped by past rewards across different platforms. A key parameter ($\mu$) in the model governs users' tendencies to either seek approval from like-minded peers or engage with opposing views. Our findings reveal that online environments can evolve into suboptimal states characterized by polarized, strongly opinionated echo chambers, even when users prefer diverse perspectives. Interestingly, this polarizing state coexists with another equilibrium, where users gravitate toward a single dominant platform, marginalizing other platforms into extremity. Using agent-based simulations and dynamical systems analysis, our model underscores the complex interplay of user preferences and platform dynamics, offering insights into how digital spaces might be better managed to foster diverse discourse.

Cuneiform is the earliest known system of writing, first developed for the Sumerian language of southern Mesopotamia in the second half of the 4th millennium BC. Cuneiform signs are obtained by impressing a stylus on fresh clay tablets. For certain purposes, e.g. authentication by seal imprint, some cuneiform tablets were enclosed in clay envelopes, which cannot be opened without destroying them. The aim of our interdisciplinary project is the non-invasive study of clay tablets. A portable X-ray micro-CT scanner is developed to acquire density data of such artifacts on a high-resolution, regular 3D grid at collection sites. The resulting volume data is processed through feature-preserving denoising, extraction of high-accuracy surfaces using a manifold dual marching cubes algorithm and extraction of local features by enhanced curvature rendering and ambient occlusion. For the non-invasive study of cuneiform inscriptions, the tablet is virtually separated from its envelope by curvature-based segmentation. The computational- and data-intensive algorithms are optimized or near-real-time offline usage with limited resources at collection sites. To visualize the complexity-reduced and octree-based compressed representation of surfaces, we develop and implement an interactive application. To facilitate the analysis of such clay tablets, we implement shape-based feature extraction algorithms to enhance cuneiform recognition. Our workflow supports innovative 3D display and interaction techniques such as autostereoscopic displays and gesture control., Comment: Preprint of an accepted paper submitted to the 14th IEEE Symposium on Large Data Analysis and Visualization. 11 pages, 19 figures, 2 tables

In this study, we explore the explainability of neural networks in agriculture and forestry, specifically in fertilizer treatment classification and wood identification. The opaque nature of these models, often considered 'black boxes', is addressed through an extensive evaluation of state-of-the-art Attribution Maps (AMs), also known as class activation maps (CAMs) or saliency maps. Our comprehensive qualitative and quantitative analysis of these AMs uncovers critical practical limitations. Findings reveal that AMs frequently fail to consistently highlight crucial features and often misalign with the features considered important by domain experts. These discrepancies raise substantial questions about the utility of AMs in understanding the decision-making process of neural networks. Our study provides critical insights into the trustworthiness and practicality of AMs within the agriculture and forestry sectors, thus facilitating a better understanding of neural networks in these application areas.

We have developed a methodology for the systematic generation of a large image dataset of macerated wood references, which we used to generate image data for nine hardwood genera. This is the basis for a substantial approach to automate, for the first time, the identification of hardwood species in microscopic images of fibrous materials by deep learning. Our methodology includes a flexible pipeline for easy annotation of vessel elements. We compare the performance of different neural network architectures and hyperparameters. Our proposed method performs similarly well to human experts. In the future, this will improve controls on global wood fiber product flows to protect forests.

Understanding how different networks relate to each other is key for obtaining a greater insight into complex systems. Here, we introduce an intuitive yet powerful framework to characterise the relationship between two networks comprising the same nodes. We showcase our framework by decomposing the shortest paths between nodes as being contributed uniquely by one or the other source network, or redundantly by either, or synergistically by the two together. Our approach takes into account the networks' full topology, and it also provides insights at multiple levels of resolution: from global statistics, to individual paths of different length. We show that this approach is widely applicable, from brains to the London public transport system. In humans and across 123 other mammalian species, we demonstrate that reliance on unique contributions by long-range white matter fibers is a conserved feature of mammalian structural brain networks. Across species, we also find that efficient communication relies on significantly greater synergy between long-range and short-range fibers than expected by chance, and significantly less redundancy. Our framework may find applications to help decide how to trade-off different desiderata when designing network systems, or to evaluate their relative presence in existing systems, whether biological or artificial.

The zero-temperature Ising model is known to reach a fully ordered ground state in sufficiently dense random graphs. In sparse random graphs, the dynamics gets absorbed in disordered local minima at magnetization close to zero. Here, we find that the non-equilibrium transition between the ordered and the disordered regime occurs at an average degree that slowly grows with the graph size. The system shows bistability: The distribution of the absolute magnetization in the reached absorbing state is bimodal, with peaks only at zero and unity. For a fixed system size, the average time to absorption behaves nonmonotonically as a function of average degree. The peak value of the average absorption time grows as a power law of the system size. These findings have relevance for community detection, opinion dynamics, and games on networks., Comment: 5 pages, 5 figures

The suffix array is arguably one of the most important data structures in sequence analysis and consequently there is a multitude of suffix sorting algorithms. However, to this date the GSACA algorithm introduced in 2015 is the only known non-recursive linear-time suffix array construction algorithm (SACA). Despite its interesting theoretical properties, there has been little effort in improving the algorithm's subpar real-world performance. There is a super-linear algorithm DSH which relies on the same sorting principle and is faster than DivSufSort, the fastest SACA for over a decade. This paper is concerned with analysing the sorting principle used in GSACA and DSH and exploiting its properties in order to give an optimised linear-time algorithm. Our resulting algorithm is not only significantly faster than GSACA but also outperforms DivSufSort and DSH.

We show how the Fourier transform for distributional sections of vector bundles over symmetric spaces of non-compact type $G/K$ can be used for questions of solvability of systems of invariant differential equations in analogy to H\"ormander's proof of the Ehrenpreis-Malgrange theorem. We get complete solvability for the hyperbolic plane $\mathbb{H}^2$ and partial results for products $\mathbb{H}^2 \times \cdots \times \mathbb{H}^2$ and the hyperbolic 3-space $\mathbb{H}^3$., Comment: Corrected misprints and improved the presentation. Lemma 1 is new

Information decompositions quantify how the Shannon information about a given random variable is distributed among several other random variables. Various requirements have been proposed that such a decomposition should satisfy, leading to different candidate solutions. Curiously, however, only two of the original requirements that determined the Shannon information have been considered, namely monotonicity and normalization. Two other important properties, continuity and additivity, have not been considered. In this contribution, we focus on the mutual information of two finite variables $Y,Z$ about a third finite variable $S$ and check which of the decompositions satisfy these two properties. While most of them satisfy continuity, only one of them is both continuous and additive., Comment: 17 pages

The description of the Paley-Wiener space for compactly supported smooth functions $C^\infty_c(G)$ on a semi-simple Lie group $G$ involves certain intertwining conditions that are difficult to handle. In the present paper, we make them completely explicit for $G=\mathbf{SL}(2,\mathbb{R})^d$ ($d\in \mathbb{N}$) and $G=\mathbf{SL}(2,\mathbb{C})$. Our results are based on a defining criterion for the Paley-Wiener space, valid for general groups of real rank one, that we derive from Delorme's proof of the Paley-Wiener theorem. In a forthcoming paper, we will show how these results can be used to study solvability of invariant differential operators between sections of homogeneous vector bundles over the corresponding symmetric spaces.

We study the Fourier transform for compactly supported distributional sections of complex homogeneous vector bundles on symmetric spaces of non-compact type $X = G/K$. We prove a characterisation of their range. In fact, from Delorme's Paley-Wiener theorem for compactly supported smooth functions on a real reductive group of Harish-Chandra class, we deduce topological Paley-Wiener and Paley-Wiener-Schwartz theorems for sections.

Force-directed layout algorithms are ubiquitously-used tools for network visualisation across a multitude of scientific disciplines. However, they lack theoretical grounding which allows to interpret their outcomes rigorously and can guide the choice of specific algorithms for certain data sets. We propose an approach building on latent space models, which assume that the probability of nodes forming a tie depends on their distance in an unobserved latent space. From such latent space models, we derive force equations for a force-directed layout algorithm. Since the forces infer positions which maximise the likelihood of the given network under the latent space model, the force-directed layout becomes interpretable. We implement these forces for unweighted and weighted networks and spatialise different real-world networks. Comparison to existing layout algorithms (not grounded in an interpretable model) reveals that node groups are placed in similar configurations, while said algorithms show a stronger intra-cluster separation of nodes, as well as a tendency to separate clusters more strongly in retweet networks. We also explore the possibility of visualising data traditionally not seen as network data, such as survey data.

The paper explores the notion of a reconfiguration of political space in the context of the rise of populism and its effects on the political system. We focus on Germany and the appearance of the new right wing party "Alternative for Germany" (AfD). Many scholars of politics discuss the rise of the new populism in Western Europe and the US with respect to a new political cleavage related to globalization, which is assumed to mainly affect the cultural dimension of the political space. As such, it might replace the older economic cleavage based on class divisions in defining the dominant dimension of political conflict. An explanation along these lines suggests a reconfiguration of the political space in the sense that (1) the main cleavage within the political space changes its direction from the economic axis towards the cultural axis, but (2) also the semantics of the cultural axis itself is changing towards globalization related topics. Using the electoral manifestos from the Manifesto project database, we empirically address this reconfiguration of the political space by comparing political spaces for Germany built using topic modeling with the spaces based on the content analysis of the Manifesto project and the corresponding categories of political goals. We find that both spaces have a similar structure and that the AfD appears on a new dimension. In order to characterize this new dimension we employ a novel technique, inter-issue consistency networks (IICN) that allow to analyze the evolution of the correlations between the political positions on different issues over several elections. We find that the new dimension introduced by the AfD can be related to the split off of a new "cultural right" issue bundle from the previously existing center-right bundle., Comment: The version 2 contains the corrected figures from the corrigendum 10.3389/fdata.2021.833037

We consider compact locally symmetric spaces $\Gamma\backslash G/H$ where $G/H$ is a non-compact semisimple symmetric space and $\Gamma$ is a discrete subgroup of $G$. We discuss some features of the joint spectrum of the (commutative) algebra $D(G/H)$ of invariant differential operators acting, as unbounded operators, on the Hilbert space $L^2(\Gamma\backslash G/H)$ of square integrable complex functions on $\Gamma\backslash G/H$. In the case of the Lorentzian symmetric space $SO_0(2,2n)/SO_0(1,2n)$, the representation theoretic spectrum is described explicitly. The strategy is to consider connected reductive Lie groups $L$ acting transitively and co-compactly on $G/H$, a cocompact lattice $\Gamma\subset L$, and study the spectrum of the algebra $D(L/L\cap H)$ on $L^2(\Gamma\backslash L/L\cap H)$. Though the group $G$ does not act on $L^2(\Gamma\backslash G/H)$, we explain how (not necessarily unitary) $G$-representations enter into the spectral decomposition of $D(G/H)$ on $L^2(\Gamma\backslash G/H)$ and why one should expect a continuous contribution to the spectrum in some cases. As a byproduct, we obtain a result on the $L$-admissibility of $G$-representations. These notes contain the statements of the main results, the proofs and the details will appear elsewhere., Comment: The results were announced in June 2019 at the conference Representation Theory XVI held in Dubrovnik, Croatia. The paper will appear in a Contemporary Mathematics volume dedicated to the conference

Automated vehicles require efficient and safe planning to maneuver in uncertain environments. Largely this uncertainty is caused by other traffic participants, e.g., surrounding vehicles. Future motion of surrounding vehicles is often difficult to predict. Whereas robust control approaches achieve safe, yet conservative motion planning for automated vehicles, Stochastic Model Predictive Control (SMPC) provides efficient planning in the presence of uncertainty. Probabilistic constraints are applied to ensure that the maximal risk remains below a predefined level. However, safety cannot be ensured as probabilistic constraints may be violated, which is not acceptable for automated vehicles. Here, we propose an efficient trajectory planning framework with safety guarantees for automated vehicles. SMPC is applied to obtain efficient vehicle trajectories for a finite horizon. Based on the first optimized SMPC input, a guaranteed safe backup trajectory is planned using reachable sets. This backup is used to overwrite the SMPC input if necessary for safety. Recursive feasibility of the safe SMPC algorithm is proved. Highway simulations show the effectiveness of the proposed method regarding performance and safety., Comment: This is the extended version of the IEEE Transactions on Intelligent Vehicles paper available at https://doi.org/10.1109/TIV.2021.3074645

This article analyses public debate on Twitter via network representations of retweets and replies. We argue that tweets observable on Twitter have both a direct and mediated effect on the perception of public opinion. Through the interplay of the two networks, it is possible to identify potentially misleading representations of public opinion on the platform. The method is employed to observe public debate about two events: The Saxon state elections and violent riots in the city of Leipzig in 2019. We show that in both cases, (i) different opinion groups exhibit different propensities to get involved in debate, and therefore have unequal impact on public opinion. Users retweeting far-right parties and politicians are significantly more active, hence their positions are disproportionately visible. (ii) Said users act significantly more confrontational in the sense that they reply mostly to users from different groups, while the contrary is not the case., Comment: 5 figures, 4 tables

What are the mechanisms by which groups with certain opinions gain public voice and force others holding a different view into silence? And how does social media play into this? Drawing on recent neuro-scientific insights into the processing of social feedback, we develop a theoretical model that allows to address these questions. The model captures phenomena described by spiral of silence theory of public opinion, provides a mechanism-based foundation for it, and allows in this way more general insight into how different group structures relate to different regimes of collective opinion expression. Even strong majorities can be forced into silence if a minority acts as a cohesive whole. The proposed framework of social feedback theory (SFT) highlights the need for sociological theorising to understand the societal-level implications of findings in social and cognitive neuroscience., Comment: Odycceus Research (www.odycceus.eu)

We present an open-source interface for scientists to explore Twitter data through interactive network visualizations. Combining data collection, transformation and visualization in one easily accessible framework, the twitter explorer connects distant and close reading of Twitter data through the interactive exploration of interaction networks and semantic networks. By lowering the technological barriers of data-driven research, it aims to attract researchers from various disciplinary backgrounds and facilitates new perspectives in the thriving field of computational social science., Comment: 13 pages, 5 figures