173 research outputs found
Brief Announcement: The Temporal Firefighter Problem
No full textThe Firefighter problem asks how many vertices can be saved from a fire spreading over the vertices of a graph. At timestep 0 a vertex begins burning, then on each subsequent timestep a non-burning vertex is chosen to be defended, and the fire then spreads to all undefended vertices that it neighbours. The problem is NP-Complete on arbitrary graphs, however existing work has found several graph classes for which there are polynomial time solutions. We introduce Temporal Firefighter, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have a polynomial-time solution. This motivates us to explore restrictions on the temporal structure of the graph, and we find that Temporal Firefighter is fixed parameter tractable with respect to the temporal graph parameter vertex-interval-membership-width
Making Life More Confusing for Firefighters
No full textIt is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem is NP-Complete on all but a few classes of graphs. Thankfully, firefighters do not have to work alone, and are often aided by the efforts of good natured civillians who slow the spread of a fire by maintaining firebreaks when they are able. We will show that this help, although well-intentioned, unfortunately makes the optimal deployment of firefighters an even harder problem. To model this scenario we introduce the Temporal Firefighter problem, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have polynomial time solutions. This motivates us to explore making use of the temporal structure of the graph in our search for tractability, and we conclude by presenting an FPT algorithm for Temporal Firefighter with respect to the temporal graph parameter vertex-interval-membership-width
Fifty Shades of Transformation
No full textDanielle Meeks explores the recent trend of publishing fan fiction, brought to the forefront by the popularity of the Fifty Shades trilogy. Creating a work within another author\u27s copyrighted fictional universe for profit is analyzed under the fair use doctrine and by comparing substantial similarities between Fifty Shades and the Twilight series to determine if the trilogy is transformative enough to survive a potential lawsuit
Structural Parameters for Dense Temporal Graphs
No full textTemporal graphs provide a useful model for many real-world networks. Unfortunately, the majority of algorithmic problems we might consider on such graphs are intractable. There has been recent progress in defining structural parameters which describe tractable cases by simultaneously restricting the underlying structure and the times at which edges appear in the graph. These all rely on the temporal graph being sparse in some sense. We introduce temporal analogues of three increasingly restrictive static graph parameters - cliquewidth, modular-width and neighbourhood diversity - which take small values for highly structured temporal graphs, even if a large number of edges are active at each timestep. The computational problems solvable efficiently when the temporal cliquewidth of the input graph is bounded form a subset of those solvable efficiently when the temporal modular-width is bounded, which is in turn a subset of problems efficiently solvable when the temporal neighbourhood diversity is bounded. By considering specific temporal graph problems, we demonstrate that (up to standard complexity theoretic assumptions) these inclusions are strict
Counting Temporal Paths
No full textThe betweenness centrality of a vertex v is an important centrality measure
that quantifies how many optimal paths between pairs of other vertices visit v.
Computing betweenness centrality in a temporal graph, in which the edge set may
change over discrete timesteps, requires us to count temporal paths that are
optimal with respect to some criterion. For several natural notions of
optimality, including foremost or fastest temporal paths, this counting problem
reduces to #Temporal Path, the problem of counting all temporal paths between a
fixed pair of vertices; like the problems of counting foremost and fastest
temporal paths, #Temporal Path is #P-hard in general. Motivated by the many
applications of this intractable problem, we initiate a systematic study of the
prameterised and approximation complexity of #Temporal Path. We show that the
problem presumably does not admit an FPT-algorithm for the feedback vertex
number of the static underlying graph, and that it is hard to approximate in
general. On the positive side, we proved several exact and approximate
FPT-algorithms for special cases
Critical interventions in Caribbean politics and theory
No full text"These essays by Brian Meeks, a noted public intellectual in the Caribbean, reflect on Caribbean politics, particularly radical politics and ideologies in the postcolonial era. But his essays also explain the peculiarities of the contemporary neo-liberal period while searching for pathways beyond the current plight. In the first chapters, titled 'Theoretical Forays,' Meeks makes a conscious attempt to engage with contemporary Caribbean political thought at a moment of flux and search for a relevant theoretical language and style to both explicate the Caribbean's recent past and confront the difficult conditions of the early twenty-first century. The next part, 'Caribbean Questions,' both retrospective and biographical, retraces the author's own engagement with the University of the West Indies (UWI), the short-lived but influential Caribbean Black Power movement, the work of seminal Trinidadian thinker and activist Lloyd Best, Cuba's relationship with Jamaica, and the crisis and collapse of the Grenadian Revolution. As evident in its title, 'Jamaican Journeys,' the concluding section excerpts and extracts from a longer, more sustained engagement with Jamaican politics and society. Much of Meeks' argument builds around the notion that Jamaica faces a crucial moment, as the author seeks to chart and explain its convoluted political path and dismal economic performance over the past three decades. Meeks remains surprisingly optimistic as he suggests that despite the emptying of sovereignty in the increasingly globalized world, windows to enhanced human development might open through policies of greater democracy and popular inclusion"-
Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks
No full textSpreading processes on graphs are a natural model for a wide variety of real-world phenomena,
including information or behaviour spread over social networks, biological diseases spreading over
contact or trade networks, and the potential flow of goods over logistical infrastructure. Often,
the networks over which these processes spread are dynamic in nature, and can be modeled with
graphs whose structure is subject to discrete changes over time, i.e. with temporal graphs. Here, we
consider temporal graphs in which edges are available at specified timesteps, and study the problem
of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally)
reachable from a given starting point. This could be used to control the spread of a disease, rumour,
etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process
starting at any single vertex can be transferred to only a limited number of other vertices using
a temporally-feasible path (i.e. a path, along which the times of the edge availabilities increase).
We introduce a natural deletion problem for temporal graphs and we provide positive and negative
results on its computational complexity, both in the traditional and the parameterised sense (subject
to various natural parameters), as well as addressing the approximability of this problem
Review Of The Origins Of Christian Morality: The First Two Centuries W. A. Meeks
No full textAn absorbing and groundbreaking study of early Christian moral discourse. Meeks (Yale, and author of The First Urban Christians, CH, Jun\u2793) not only places the ancient texts in their specific cultural and religious settings but also calls on contemporary philosophical discussion to illuminate features of the emerging Christian moral vision. Since early Christians did not produce a systematic discussion of their ethical perspective, its contours must be discerned in its legacies--letters, testaments, moral stories, rituals--and in its charitable institutions and its attitudes toward celibacy, sex, and female roles. Meeks frames his discussion with two additional considerations. Conversion to Christianity meant radically separating from one\u27s past life and taking seriously the prospect of the end of the world. These viewpoints heightened Christians\u27 sense of being members of an alien nation. In addition, Meeks assesses the contributions from Jewish and Greco-Roman sources, as well as their similarities and contrasts to Christian ideas. This fine, comprehensive study should be a standard for many years. Upper-level undergraduate and above
Deleting edges to restrict the size of an epidemic: a new application for treewidth
No full textMotivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small treewidth) so that the resulting graph avoids a set FF of forbidden subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when h=3h=3 ), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time 2O(|F|wr)n2O(|F|wr)n on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices. For the special case in which we wish only to ensure that no component has more than h vertices, we improve on this to give an algorithm running in time O((wh)2wn)O((wh)2wn) , which we have implemented and tested on real datasets based on cattle movements
- …
