Search

In the Cluster Editing problem, sometimes known as (unweighted) Correlation Clustering, we must insert and delete a minimum number of edges to achieve a graph in which every connected component is a clique. Owing to its applications in computational biology, social network analysis, machine learning, and others, this problem has been widely studied for decades and is still undergoing active research. There exist several parameterized algorithms for general graphs, but little is known about the complexity of the problem on specific classes of graphs. Among the few important results in this direction, if only deletions are allowed, the problem can be solved in polynomial time on cographs, which are the $P_4$-free graphs. However, the complexity of the broader editing problem on cographs is still open. We show that even on a very restricted subclass of cographs, the problem is NP-hard, W[1]-hard when parameterized by the number $p$ of desired clusters, and that time $n^{o(p/\log p)}$ is forbidden under the ETH. This shows that the editing variant is substantially harder than the deletion-only case, and that hardness holds for the many superclasses of cographs (including graphs of clique-width at most $2$, perfect graphs, circle graphs, permutation graphs). On the other hand, we provide an almost tight upper bound of time $n^{O(p)}$, which is a consequence of a more general $n^{O(cw \cdot p)}$ time algorithm, where $cw$ is the clique-width. Given that forbidding $P_4$s maintains NP-hardness, we look at $\{P_4, C_4\}$-free graphs, also known as trivially perfect graphs, and provide a cubic-time algorithm for this class., Comment: 28 pages, 3 figures

Given a bipartite graph $G$, the \textsc{Bicluster Editing} problem asks for the minimum number of edges to insert or delete in $G$ so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter $k$, which is the number of allowed modified edges. We first show that one can obtain a kernel with $4.5k$ vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time $O^*(2.581^k)$. Our algorithm has the advantage of being conceptually simple and should be easy to implement., Comment: The author acknowledges the contributions of Beno\^it Charbonneau and Pierre-Luc Parent for their help in finding the $4.5k$ lower bound on the kernel size

In the last few years, economic agent-based models have made the transition from qualitative models calibrated to match stylised facts to quantitative models for time series forecasting, and in some cases, their predictions have performed as well or better than those of standard models (see, e.g. Poledna et al. (2023a); Hommes et al. (2022); Pichler et al. (2022)). Here, we build on the model of Poledna et al., adding several new features such as housing markets, realistic synthetic populations of individuals with income, wealth and consumption heterogeneity, enhanced behavioural rules and market mechanisms, and an enhanced credit market. We calibrate our model for all 38 OECD member countries using state-of-the-art approximate Bayesian inference methods and test it by making out-of-sample forecasts. It outperforms both the Poledna and AR(1) time series models by a highly statistically significant margin. Our model is built within a platform we have developed, making it easy to build, run, and evaluate alternative models, which we hope will encourage future work in this area.

Predicting horizontal gene transfers often requires comparative sequence data, but recent work has shown that character-based approaches could also be useful for this task. Notably, perfect transfer networks (PTN) explain the character diversity of a set of taxa for traits that are gained once, rarely lost, but that can be transferred laterally. Characterizing the structure of such characters is an important step towards understanding more complex characters. Although efficient algorithms can infer such networks from character data, they can sometimes predict overly complicated transfer histories. With the goal of recovering the simplest possible scenarios in this model, we introduce galled perfect transfer networks, which are PTNs that are galled trees. Such networks are useful for characters that are incompatible in terms of tree-like evolution, but that do fit in an almost-tree scenario. We provide polynomial-time algorithms for two problems: deciding whether one can add transfer edges to a tree to transform it into a galled PTN, and deciding whether a set of characters are galled-compatible, that is, they can be explained by some galled PTN. We also analyze a real dataset comprising of a bacterial species trees and KEGG functions as characters, and derive several conclusions on the difficulty of explaining characters in a galled tree, which provide several directions for future research., Comment: extended article based on previously accepted manuscript at RECOMB-CG 2024 conference

The CHIPS R&D project focuses on development of low-cost water Cherenkov neutrino detectors through novel design strategies and resourceful engineering. This work presents an end-to-end DAQ solution intended for a recent 5 kt CHIPS prototype, which is largely based on affordable mass-produced components. Much like the detector itself, the presented instrumentation is composed of modular arrays that can be scaled up and easily serviced. A single such array can carry up to 30 photomultiplier tubes (PMTs) accompanied by electronics that generate high voltage in-situ and deliver time resolution of up to 0.69 ns. In addition, the technology is compatible with the White Rabbit timing system, which can synchronize its elements to within 100 ps. While deployment issues did not permit the presented DAQ system to operate beyond initial evaluation, the presented hardware and software successfully passed numerous commissioning tests that demonstrated their viability for use in a large-scale neutrino detector, instrumented with thousands of PMTs., Comment: 30 pages, 28 figures, submitted to MDPI Applied Sciences, Special Issue: Advanced Neutrino Detector Development and Application

In phylogenetics, evolution is traditionally represented in a tree-like manner. However, phylogenetic networks can be more appropriate for representing evolutionary events such as hybridization, horizontal gene transfer, and others. In particular, the class of forest-based networks was recently introduced to represent introgression, in which genes are swapped between between species. A network is forest-based if it can be obtained by adding arcs to a collection of trees, so that the endpoints of the new arcs are in different trees. This contrasts with so-called tree-based networks, which are formed by adding arcs within a single tree. We are interested in the computational complexity of recognizing forest-based networks, which was recently left as an open problem by Huber et al. Forest-based networks coincide with directed acyclic graphs that can be partitioned into induced paths, each ending at a leaf of the original graph. Several types of path partitions have been studied in the graph theory literature, but to our knowledge this type of leaf induced path partition has not been considered before. The study of forest-based networks in terms of these partitions allows us to establish closer relationships between phylogenetics and algorithmic graph theory, and to provide answers to problems in both fields. We show that deciding whether a network is forest-based is NP-complete, even on input networks that are tree-based, binary, and have only three leaves. This shows that partitioning a directed acyclic graph into three induced paths is NP-complete, answering a recent question of Fernau et al. We then show that the problem is polynomial-time solvable on binary networks with two leaves and on the class of orchards. Finally, for undirected graphs, we introduce unrooted forest-based networks and provide hardness results for this class as well.

In this study, we investigate the problem of comparing gene trees reconciled with the same species tree using a novel semi-metric, called the Path-Label Reconciliation (PLR) dissimilarity measure. This approach not only quantifies differences in the topology of reconciled gene trees, but also considers discrepancies in predicted ancestral gene-species maps and speciation/duplication events, offering a refinement of existing metrics such as Robinson-Foulds (RF) and their labeled extensions LRF and ELRF. A tunable parameter {\alpha} also allows users to adjust the balance between its species map and event labeling components. We show that PLR can be computed in linear time and that it is a semi-metric. We also discuss the diameters of reconciled gene tree measures, which are important in practice for normalization, and provide initial bounds on PLR, LRF, and ELRF. To validate PLR, we simulate reconciliations and perform comparisons with LRF and ELRF. The results show that PLR provides a more evenly distributed range of distances, making it less susceptible to overestimating differences in the presence of small topological changes, while at the same time being computationally efficient. Our findings suggest that the theoretical diameter is rarely reached in practice. The PLR measure advances phylogenetic reconciliation by combining theoretical rigor with practical applicability. Future research will refine its mathematical properties, explore its performance on different tree types, and integrate it with existing bioinformatics tools for large-scale evolutionary analyses. The open source code is available at: https://pypi.org/project/parle/., Comment: Full version of WABI 2024 conference paper

A graph $G=(V,E)$ is a $k$-leaf power if there is a tree $T$ whose leaves are the vertices of $G$ with the property that a pair of leaves $u$ and $v$ induce an edge in $G$ if and only if they are distance at most $k$ apart in $T$. For $k\le 4$, it is known that there exists a finite set $F_k$ of graphs such that the class $L(k)$ of $k$-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in $F_k$ as an induced subgraph. We prove no such characterization holds for $k\ge 5$. That is, for any $k\ge 5$, there is no finite set $F_k$ of graphs such that $L(k)$ is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in $F_k$.

In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. This allows to define an operational distance on this space, as the minimum number of contractions and expansions required to transform one network into another. We highlight the difference between this distance and the computation of the maximum common contraction between two networks. Given its ability to outline a common structure between them, which can provide valuable biological insights, we study the algorithmic aspects of the latter. We first prove that computing a maximum common contraction between two networks is NP-hard, even when the maximum degree, the size of the common contraction, or the number of leaves is bounded. We also provide lower bounds to the problem based on the Exponential-Time Hypothesis. Nonetheless, we do provide a polynomial-time algorithm for weakly-galled networks, a generalization of galled trees., Comment: full version (with complete set of proofs) of WABI 2024 submission

Motivation: Non-coding RNAs (ncRNAs) express their functions by adopting molecular structures. Specifically, RNA secondary structures serve as a relatively stable intermediate step before tertiary structures, offering a reliable signature of molecular function. Consequently, within an RNA functional family, secondary structures are generally more evolutionarily conserved than sequences. Conversely, homologous RNA families grouped within an RNA clan share ancestors but typically exhibit structural differences. Inferring the evolution of RNA structures within RNA families and clans is crucial for gaining insights into functional adaptations over time and providing clues about the Ancient RNA World Hypothesis. Results: We introduce the median problem and the small parsimony problem for ncRNA families, where secondary structures are represented as leaf-labelled trees. We utilize the Robinson-Foulds (RF) tree distance, which corresponds to a specific edit distance between RNA trees, and a new metric called the Internal-Leafset (IL) distance. While the RF tree distance compares sets of leaves descending from internal nodes of two RNA trees, the IL distance compares the collection of leaf-children of internal nodes. The latter is better at capturing differences in structural elements of RNAs than the RF distance, which is more focused on base pairs. We also consider a more general tree edit distance that allows the mapping of base pairs that are not perfectly aligned. We study the theoretical complexity of the median problem and the small parsimony problem under the three distance metrics and various biologically-relevant constraints, and we present polynomial-time maximum parsimony algorithms for solving some versions of the problems. Our algorithms are applied to ncRNA families from the RFAM database, illustrating their practical utility

CHIPS (CHerenkov detectors In mine PitS) was a prototype large-scale water Cherenkov detector located in northern Minnesota. The main aim of the R&D project was to demonstrate that construction costs of neutrino oscillation detectors could be reduced by at least an order of magnitude compared to other equivalent experiments. This article presents design features of the CHIPS detector along with details of the implementation and deployment of the prototype. While issues during and after the deployment of the detector prevented data taking, a number of key concepts and designs were successfully demonstrated.

Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while phylogenetic methods use sequences to reconstruct the gene and species trees. However, it is well-known that sequences have difficulty identifying ancient transfers since mutations have enough time to erase all evidence of such events. In this work, we ask whether character-based methods can predict gene transfers. Their advantage over sequences is that homologous genes can have low DNA similarity, but still have retained enough important common motifs that allow them to have common character traits, for instance the same functional or expression profile. A phylogeny that has two separate clades that acquired the same character independently might indicate the presence of a transfer even in the absence of sequence similarity. We introduce perfect transfer networks, which are phylogenetic networks that can explain the character diversity of a set of taxa under the assumption that characters have unique births, and that once a character is gained it is rarely lost. Examples of such traits include transposable elements, biochemical markers and emergence of organelles, just to name a few. We study the differences between our model and two similar models: perfect phylogenetic networks and ancestral recombination networks. Our goals are to initiate a study on the structural and algorithmic properties of perfect transfer networks. We then show that in polynomial time, one can decide whether a given network is a valid explanation for a set of taxa, and show how, for a given tree, one can add transfer edges to it so that it explains a set of taxa. We finally provide lower and upper bounds on the number of transfers required to explain a set of taxa, in the worst case.

Network reconstruction is a well-developed sub-field of network science, but it has only recently been applied to production networks, where nodes are firms and edges represent customer-supplier relationships. We review the literature that has flourished to infer the topology of these networks by partial, aggregate, or indirect observation of the data. We discuss why this is an important endeavour, what needs to be reconstructed, what makes it different from other network reconstruction problems, and how different researchers have approached the problem. We conclude with a research agenda.

For a graph class $\mathcal{G}$, we define the $\mathcal{G}$-modular cardinality of a graph $G$ as the minimum size of a vertex partition of $G$ into modules that each induces a graph in $\mathcal{G}$. This generalizes other module-based graph parameters such as neighborhood diversity and iterated type partition. Moreover, if $\mathcal{G}$ has bounded modular-width, the W[1]-hardness of a problem in $\mathcal{G}$-modular cardinality implies hardness on modular-width, clique-width, and other related parameters. On the other hand, fixed-parameter tractable (FPT) algorithms in $\mathcal{G}$-modular cardinality may provide new ideas for algorithms using such parameters. Several FPT algorithms based on modular partitions compute a solution table in each module, then combine each table into a global solution. This works well when each table has a succinct representation, but as we argue, when no such representation exists, the problem is typically W[1]-hard. We illustrate these ideas on the generic $(\alpha, \beta)$-domination problem, which asks for a set of vertices that contains at least a fraction $\alpha$ of the adjacent vertices of each unchosen vertex, plus some (possibly negative) amount $\beta$. This generalizes known domination problems such as Bounded Degree Deletion, $k$-Domination, and $\alpha$-Domination. We show that for graph classes $\mathcal{G}$ that require arbitrarily large solution tables, these problems are W[1]-hard in the $\mathcal{G}$-modular cardinality, whereas they are fixed-parameter tractable when they admit succinct solution tables. This leads to several new positive and negative results for many domination problems parameterized by known and novel structural graph parameters such as clique-width, modular-width, and $cluster$-modular cardinality., Comment: 70 pages, 6 figures, 5 tables

Several classical combinatorial problems have been considered and analysed on temporal graphs. Recently, a variant of Vertex Cover on temporal graphs, called MinTimelineCover, has been introduced to summarize timeline activities in social networks. The problem asks to cover every temporal edge while minimizing the total span of the vertices (where the span of a vertex is the length of the timestamp interval it must remain active in, minus one). While the problem has been shown to be NP-hard even in very restricted cases, its parameterized complexity has not been fully understood. The problem is known to be in FPT under the span parameter only for graphs with two timestamps, but the parameterized complexity for the general case is open. We settle this open problem by giving an FPT algorithm that is based on a combination of iterative compression and a reduction to the Digraph Pair Cut problem, a powerful problem that has received significant attention recently.

Structural graph parameters play an important role in parameterized complexity, including in kernelization. Notably, vertex cover, neighborhood diversity, twin-cover, and modular-width have been studied extensively in the last few years. However, there are many fundamental problems whose preprocessing complexity is not fully understood under these parameters. Indeed, the existence of polynomial kernels or polynomial Turing kernels for famous problems such as Clique, Chromatic Number, and Steiner Tree has only been established for a subset of structural parameters. In this work, we use several techniques to obtain a complete preprocessing complexity landscape for over a dozen of fundamental algorithmic problems., Comment: 24 pages, 1 table, 1 figure

Several NP-hard problems are solved exactly using exponential-time branching strategies, whether it be branch-and-bound algorithms, or bounded search trees in fixed-parameter algorithms. The number of tractable instances that can be handled by sequential algorithms is usually small, whereas massive parallelization has been shown to significantly increase the space of instances that can be solved exactly. However, previous centralized approaches require too much communication to be efficient, whereas decentralized approaches are more efficient but have difficulty keeping track of the global state of the exploration. In this work, we propose to revisit the centralized paradigm while avoiding previous bottlenecks. In our strategy, the center has lightweight responsibilities, requires only a few bits for every communication, but is still able to keep track of the progress of every worker. In particular, the center never holds any task but is able to guarantee that a process with no work always receives the highest priority task globally. Our strategy was implemented in a generic C++ library called GemPBA, which allows a programmer to convert a sequential branching algorithm into a parallel version by changing only a few lines of code. An experimental case study on the vertex cover problem demonstrates that some of the toughest instances from the DIMACS challenge graphs that would take months to solve sequentially can be handled within two hours with our approach.

Phylogenetic networks are increasingly being considered as better suited to represent the complexity of the evolutionary relationships between species. One class of phylogenetic networks that has received a lot of attention recently is the class of orchard networks, which is composed of networks that can be reduced to a single leaf using cherry reductions. Cherry reductions, also called cherry-picking operations, remove either a leaf of a simple cherry (sibling leaves sharing a parent) or a reticulate edge of a reticulate cherry (two leaves whose parents are connected by a reticulate edge). In this paper, we present a fixed-parameter tractable algorithm to solve the problem of finding a maximum agreement cherry-reduced subnetwork (MACRS) between two rooted binary level-1 networks. This is first exact algorithm proposed to solve the MACRS problem. As proven in earlier work, there is a direct relationship between finding an MACRS and calculating a distance based on cherry operations. As a result, the proposed algorithm also provides a distance that can be used for the comparison of level-1 networks., Comment: presented at RECOMG-CG 2023 conference

Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-repeated subsequence (LSRS) is proposed. Given a sequence $S$ of length $n$, a letter-repeated subsequence is a subsequence of $S$ in the form of $x_1^{d_1}x_2^{d_2}\cdots x_k^{d_k}$ with $x_i$ a subsequence of $S$, $x_j\neq x_{j+1}$ and $d_i\geq 2$ for all $i$ in $[k]$ and $j$ in $[k-1]$. We first present an $O(n^6)$ time algorithm to compute the longest cubic subsequences of all the $O(n^2)$ substrings of $S$, improving the trivial $O(n^7)$ bound. Then, an $O(n^6)$ time algorithm for computing the longest subsequence-repeated subsequence (LSRS) of $S$ is obtained. Finally we focus on two variants of this problem. We first consider the constrained version when $\Sigma$ is unbounded, each letter appears in $S$ at most $d$ times and all the letters in $\Sigma$ must appear in the solution. We show that the problem is NP-hard for $d=4$, via a reduction from a special version of SAT (which is obtained from 3-COLORING). We then show that when each letter appears in $S$ at most $d=3$ times, then the problem is solvable in $O(n^5)$ time., Comment: 15 pages, 1 figure

In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set $P$ of $2n$ points in the plane, and two sites $c_1$ and $c_2$, compute two $n$-stars $S_1$ and $S_2$ centered at $c_1$ and $c_2$ respectively such that the maximum weight of $S_1$ and $S_2$ is minimized. This problem is strongly NP-hard by a reduction from Equal-size Set-Partition with Rationals. Then we consider two variations of the Two-Squirrel problem, namely the Two-MST and Two-TSP problem, which are both NP-hard. The NP-hardness for the latter is obvious while the former needs a non-trivial reduction from Equal-size Set-Partition with Rationals. In terms of approximation algorithms, for Two-MST and Two-TSP we give factor 3.6402 and $4+\varepsilon$ approximations respectively. Finally, we also show some interesting polynomial-time solvable cases for Two-MST., Comment: 17 pages, 7 figures

The potential tradeoff between health outcomes and economic impact has been a major challenge in the policy making process during the COVID-19 pandemic. Epidemic-economic models designed to address this issue are either too aggregate to consider heterogeneous outcomes across socio-economic groups, or, when sufficiently fine-grained, not well grounded by empirical data. To fill this gap, we introduce a data-driven, granular, agent-based model that simulates epidemic and economic outcomes across industries, occupations, and income levels with geographic realism. The key mechanism coupling the epidemic and economic modules is the reduction in consumption demand due to fear of infection. We calibrate the model to the first wave of COVID-19 in the New York metropolitan area, showing that it reproduces key epidemic and economic statistics, and then examine counterfactual scenarios. We find that: (a) both high fear of infection and strict restrictions similarly harm the economy but reduce infections; (b) low-income workers bear the brunt of both the economic and epidemic harm; (c) closing non-customer-facing industries such as manufacturing and construction only marginally reduces the death toll while considerably increasing unemployment; and (d) delaying the start of protective measures does little to help the economy and worsens epidemic outcomes in all scenarios. We anticipate that our model will help designing effective and equitable non-pharmaceutical interventions that minimize disruptions in the face of a novel pandemic.

Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree $T$ to vertices and edges of a species tree $S$. The relative timing of the last common ancestors of two extant genes (leaves of $T$) and the last common ancestors of the two species (leaves of $S$) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.

The near channel performance of Low Density Parity Check Codes (LDPC) has motivated its wide applications. Iterative decoding of LDPC codes provides significant implementation challenges as the complexity grows with the code size. Recent trends in integrating Multiprocessor System on Chip (MPSoC) with Network on Chip (NoC) gives a modular platform for parallel implementation. This paper presents an implementation platform for decoding LDPC codes based on HeMPS, an open source MPSoC framework based on NoC communication fabric. Reduced minimum sum algorithm is used for decoding LDPC codes and simulations are performed using HeMPS tool. The data rate and speedup factor measured for decoding a rate 1/2 LDPC code characterised by 252x504 parity matrix is presented, Comment: 2013 International Conference on High Performance Computing & Simulation (HPCS)

The problem of gender bias is highly prevalent and well known. In this paper, we have analysed the portrayal of gender roles in English movies, a medium that effectively influences society in shaping people's beliefs and opinions. First, we gathered scripts of films from different genres and derived sentiments and emotions using natural language processing techniques. Afterwards, we converted the scripts into embeddings, i.e. a way of representing text in the form of vectors. With a thorough investigation, we found specific patterns in male and female characters' personality traits in movies that align with societal stereotypes. Furthermore, we used mathematical and machine learning techniques and found some biases wherein men are shown to be more dominant and envious than women, whereas women have more joyful roles in movies. In our work, we introduce, to the best of our knowledge, a novel technique to convert dialogues into an array of emotions by combining it with Plutchik's wheel of emotions. Our study aims to encourage reflections on gender equality in the domain of film and facilitate other researchers in analysing movies automatically instead of using manual approaches.