166 research outputs found
Separating sets of strings by finding matching patterns is almost always hard
No full textWe study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others. © 2017 Elsevier B.V
Augmenting Graphs to Minimize the Diameter
No full textWe study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem
Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
No full textClustering, particularly hierarchical clustering, is an important method for understanding and analysing data across a wide variety of knowledge domains with notable utility in systems where the data can be classified in an evolutionary context. This paper introduces a new hierarchical clustering problem defined by a novel objective function we call the arithmetic-harmonic cut. We show that the problem of finding such a cut is NP-hard and APX-hard but is fixed-parameter tractable, which indicates that although the problem is unlikely to have a polynomial time algorithm (even for approximation), exact parameterized and local search based techniques may produce workable algorithms. To this end, we implement a memetic algorithm for the problem and demonstrate the effectiveness of the arithmetic-harmonic cut on a number of datasets including a cancer type dataset and a corona virus dataset. We show favorable performance compared to currently used hierarchical clustering techniques such as k-Means, Graclus and Normalized-Cut. The arithmetic-harmonic cut metric overcoming difficulties other hierarchical methods have in representing both intercluster differences and intracluster similarities
Complete Balancing via Rotation
No full textTrees are a fundamental structure in algorithmics. In this paper, we study the transformation of an arbitrary binary tree S with n vertices into a completely balanced tree T via rotations, a widely studied elementary tree operation. Combining concepts on rotation distance and data structures, we give a basic algorithm that performs the transformation in Θ(n) time and Θ(1) space, making at most 2n - 2 log2n rotations and improving on known previous results. The algorithm is then improved, exploiting particular properties of S. Finally, we show tighter upper bounds and obtain a close lower bound on the rotation distance between a zig-zag tree and a completely balanced tree. We also find the exact rotation distance of a particular almost balanced tree to a completely balanced tree, and thus show that their distance is quite large despite the similarity of the two trees
Fortissat Science Alliance podcast: Layla Mathieson
No full textLayla Mathieson was an EPSRC/MRC OPTIMA CDT PhD student studying optical medical imaging alongside an integrated Masters in healthcare innovation and entrepreneurship at the University of Edinburgh. She took part in the Fortissat Science Alliance podcast recordings in September 2021.What is the Fortissat Science Alliance?The Fortissat Science Alliance was a Wellcome Trust & Children In Need "Curiosity" project. This scheme provided informal STEM learning opportunities for young people who attended the community centre Getting Better Together Shotts (GBT Shotts) between 2019 and 2023. Due to the COVID-19 pandemic, deliveries had to pivot online so the podcast was founded. These recordings were made via Zoom with warm-up STEM activities sent to every young person in advance, along with a profile page for each researcher, so that they were relaxed and able to ask excellent questions.Link to episode on Spotify.Depending on the broadcast date, podcast deliveries were co-sponsored by Glasgow Science Festival, EXPLORATHON 2021, or EXPLORATHON 2022/23.For the duration of the project, it was supported jointly by Children in Need and the Wellcome Trust. In 2021, EXPLORATHON episodes were supported by the European Commission [grant agreement ID 101036101]. In 2022-23, EXPLORATHON episodes were supported by the Engineering & Physical Sciences Research Council [grant number EP/X020894/1]. Layla was supported by the EPSRC/MRC Centre for Doctoral Training in Optical Medical Imaging (OPTIMA).Author contributions to contentLayla Mathieson was the guest featured on this episode. Rebecca Hay was the youth worker coordinating the young people who conducted the interviews as well as co-editing and broadcasting the recordings. Iain Hamilton co-edited the episodes. Kirsty Ross was the STEM consultant for the project and uploaded completed episodes to Figshare.</p
Graph editing problems with extended regularity constraints
No full text© 2017 Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k+r parameterization
The parameterized complexity of editing graphs for bounded degeneracy
No full textAbstractWe examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete, and remains W[P]-complete even if the input graph is already (r+1)-degenerate, or has maximum degree 2r+1 for all r≥2.We also demonstrate fixed-parameter tractability for several Clique based problems when the input graph has bounded degeneracy
The Parameterized Complexity of Degree Constrained Editing Problems
No full textThis thesis examines degree constrained editing problems within the framework of parameterized complexity. A degree constrained editing problem takes as input a graph and a set of constraints and asks whether the graph can be altered in at most k editing steps such that the degrees of the remaining vertices are within the given constraints. Parameterized complexity gives a framework for examining
problems that are traditionally considered intractable and developing efficient exact algorithms for them, or showing that it is unlikely that they have such algorithms, by introducing an additional component to the input, the parameter, which gives additional information about the structure of the problem. If the problem has an algorithm that is exponential in the parameter, but polynomial, with constant degree, in the size of the input, then it is considered to be fixed-parameter tractable.
Parameterized complexity also provides an intractability framework for identifying problems that are likely to not have such an algorithm.
Degree constrained editing problems provide natural parameterizations in terms of the total cost k of vertex deletions, edge deletions and edge additions allowed, and
the upper bound r on the degree of the vertices remaining after editing. We define a class of degree constrained editing problems, WDCE, which generalises several well know problems, such as Degree r Deletion, Cubic Subgraph, r-Regular Subgraph, f-Factor and General Factor. We show that in general if both k and r are part of the parameter, problems in the WDCE class are fixed-parameter tractable, and if parameterized by k or r alone, the problems are intractable in a parameterized sense.
We further show cases of WDCE that have polynomial time kernelizations, and in particular when all the degree constraints are a single number and the editing
operations include vertex deletion and edge deletion we show that there is a kernel with at most O(kr(k + r)) vertices. If we allow vertex deletion and edge addition,
we show that despite remaining fixed-parameter tractable when parameterized by k and r together, the problems are unlikely to have polynomial sized kernelizations, or
polynomial time kernelizations of a certain form, under certain complexity theoretic assumptions.
We also examine a more general case where given an input graph the question is whether with at most k deletions the graph can be made r-degenerate. We show that in this case the problems are intractable, even when r is a constant
Recommended from our members
Genome-wide analysis identifies genetic effects on reproductive success and ongoing natural selection at the FADS locus
No full textThis manuscript represents a large collaboration with many "middle" contributing authors, including the author requesting this waiver (Daniel Chasman). Iain Mathieson, Felix R. Day, Nicola Barban, Felix C. Tropf, and David M. Brazel are the starred (equal contribution) first authors; Melinda C. Mills, and John R.B. Perry are the starred last authors. Corresponding: Iain Mathieson, Melinda C. Mills, and John Perry are the corresponding authors.
Please note that while the uploaded version of the manuscript has been accepted, there may still be changes that would be incorporated in the final publication.Identifying genetic determinants of reproductive success may highlight mechanisms underlying fertility and identify alleles under present-day selection. Using data in 785,604 individuals of European ancestry, we identified 43 genomic loci associated with either number of children ever born (NEB) or childlessness. These loci span diverse aspects of reproductive biology, including puberty timing, age at first birth, sex hormone regulation, endometriosis and age at menopause. Missense variants in ARHGAP27 were associated with higher NEB but shorter reproductive lifespan, suggesting a trade-off at this locus between reproductive ageing and intensity. Other genes implicated by coding variants include PIK3IP1, ZFP82 and LRP4, and our results suggest a new role for the melanocortin 1 receptor (MC1R) in reproductive biology. As NEB is one component of evolutionary fitness, our identified associations indicate loci under present-day natural selection. Integration with data from historical selection scans highlighted an allele in the FADS1/2 gene locus that has been under selection for thousands of years and remains so today. Collectively, our findings demonstrate that a broad range of biological mechanisms contribute to reproductive success.Accepted Manuscrip
- …
