Search

In this paper the necessary and sufficient conditions are given for the solution of a system of parameter varying linear inequalities of the form A(t) x ≥ b (t) for all t ∈ T, where T is an arbitrary set, x is the unknown vector, A(t) is a known triangular Toeplitz matrix and b (t) is a known vector. For every t ∈ T the corresponding inequality defines a polyhedron, in which the solution should exist. The solution of the linear system is the intersection of the corresponding polyhedrons for every t ∈ T . A general modular decomposition method has been developed, which is based on the successive reduction of the initial system of inequalities by reducing iteratively the number of variables and by considering an equivalent system of inequalities. [ABSTRACT FROM AUTHOR]

The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view and introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: Bankruptcy Minimization/Maximization , in which the aim is to produce a payment schedule with at most/at least a given number of bankruptcies; Perfect Scheduling , the special case of the minimization variant where the aim is to produce a schedule with no bankruptcies (that is, a perfect schedule); and Bailout Minimization , in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. We show that each of these problems is NP-complete, in many cases even on very restricted input instances. On the positive side, we provide for Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees although in contrast we prove NP-completeness on directed acyclic graphs, as well as on instances with a constant number of nodes (and hence also constant treewidth). When we allow non-integer payments, we show by a linear programming argument that the problem Bailout Minimization can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we 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. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms used in practice for computing the hyperbolicity number of an n-vertex graph have running time O (n 4) . Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2 O (k) + O (n + m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential Time Hypothesis (SETH) fails, there is no 2 o (k) · n 2 - ε -time algorithm for every ε > 0 . [ABSTRACT FROM AUTHOR]