Romeo Rizzi

I&C Journal 2025 Journal Article

Linear-time safe-alternating DFS and SCCs

• Carlo Comin
• Romeo Rizzi

An alternating graph is a directed graph whose vertex set is partitioned into two colour classes, existential and universal. This forms the basic arena for well-known models in formal verification, discrete optimal control, and infinite duration two-player games where Player □ and Player ○ alternate in a turn-based sliding of a pebble along the arcs they control. We study alternating strongly-connectedness on alternating graphs as a generalization of strongly-connectedness in directed graphs, aiming at providing a linear-time decomposition and a sound structural graph characterization. For this a novel notion of alternating reachability is introduced: Player □ attempts to reach vertices without leaving a prescribed subset of the vertices while Player ○ works against. This is named safe-alternating reachability. It is shown that every alternating graph uniquely decomposes into safe-alternating strongly-connected components, where Player □ can visit each vertex within a given component infinitely often without having to ever leave out the component itself. Our main result is a linear-time algorithm for computing this alternating graph decomposition. Both the underlying graph structures and the algorithm generalize the classical decomposition of a directed graph into strongly-connected components, building on the algorithms devised by Tarjan in 1972. Our theory has direct applications e. g. solving well-known infinite duration pebble games faster. Dinneen and Khoussainov showed in 1999 that deciding a given Update Game costs O ( m n ) time, where n is the number of vertices and m is that of arcs. We solve that task in Θ ( m + n ) linear time. In turn the complexity of Explicit McNaughton-Müller Games improves from cubic to quadratic.

MFCS Conference 2024 Conference Paper

Generalizing Roberts' Characterization of Unit Interval Graphs

• Virginia Ardévol Martínez
• Romeo Rizzi
• Abdallah Saffidine
• Florian Sikora
• Stéphane Vialette

For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1, 2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2.

I&C Journal 2024 Journal Article

Predictive mining of multi-temporal relations

• Beatrice Amico
• Carlo Combi
• Romeo Rizzi
• Pietro Sala

In this paper, we propose a methodology for deriving a new kind of approximate temporal functional dependencies, called Approximate Predictive Functional Dependencies (APFDs), based on a three-window framework and on a multi-temporal relational model. Different features are proposed for the Observation Window (OW), where we observe predictive data, for the Waiting Window (WW), and for the Prediction Window (PW), where the predicted event occurs. We then consider the concept of approximation for such APFDs, introduce new error measures, and discuss different strategies for deriving APFDs. We discuss the quality, i. e. , the informative content, of the derived AFDs by considering their entropy and information gain. Moreover, we outline the results in deriving APFDs focusing on the Acute Kidney Injury (AKI). We use real clinical data contained in the MIMIC III dataset related to patients from Intensive Care Units to show the applicability of our approach to real-world data.

TIME Conference 2023 Conference Paper

Discovering Predictive Dependencies on Multi-Temporal Relations

• Beatrice Amico
• Carlo Combi
• Romeo Rizzi
• Pietro Sala

In this paper, we propose a methodology for deriving a new kind of approximate temporal functional dependencies, called Approximate Predictive Functional Dependencies (APFDs), based on a three-window framework and on a multi-temporal relational model. Different features are proposed for the Observation Window (OW), where we observe predictive data, for the Waiting Window (WW), and for the Prediction Window (PW), where the predicted event occurs. We then discuss the concept of approximation for such APFDs, introduce two new error measures. We prove that the problem of deriving APFDs is intractable. Moreover, we discuss some preliminary results in deriving APFDs from real clinical data using MIMIC III dataset, related to patients from Intensive Care Units.

TCS Journal 2023 Journal Article

On recognising words that are squares for the shuffle product

• Romeo Rizzi
• Stéphane Vialette

The shuffle of two words u and v of A ⁎ is the language u ⧢ v consisting of all words u 1 v 1 u 2 v 2 … u k v k, where k ≥ 0 and the u i and v i are words of A ⁎ such that u = u 1 u 2 … u k and v = v 1 v 2 … v k. In other words, u ⧢ v is the finite set of all words obtainable from merging the words u and v from left to right, but choosing the next symbol arbitrarily from u or v. A word u ∈ A ⁎ is a square for the shuffle product if it is the shuffle of two identical words (i. e. , u ∈ v ⧢ v for some v ∈ A ⁎ ). Whereas it can be decided in polynomial-time whether or not u ∈ v 1 ⧢ v 2 for given words u, v 1 and v 2 (J. -C. Spehner, 1986 [19]), we show in this paper that it is NP-complete to determine whether or not a word u is a square for the shuffle product. The novelty in our approach lies in representing words as linear graphs, in which deciding whether or not a given word is a square for the shuffle product reduces to computing some inclusion-free perfect matching. Finally, we prove that it is NP-complete to determine whether or not an input word is in the shuffle of a word with its reverse.

SODA Conference 2022 Conference Paper

Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time

• Manuel Cáceres
• Massimo Cairo
• Brendan Mumey
• Romeo Rizzi
• Alexandru I. Tomescu

A minimum path cover (MPC) of a directed acyclic graph (DAG) G = ( V, E ) is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size k of an MPC (also known as the width ) can be small in practical applications, research has also studied algorithms whose running time is parameterized on k. We obtain two new MPC parameterized algorithms for DAGs running in time O(k 2 | V | log |V| + |E| ) and O ( k 3 |V| + |E| ). We also obtain a parallel algorithm running in O ( k 2 |V| + |E| ) parallel steps and using O (log |V| ) processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we show that we can transform (in O ( k 2 |V| ) time) a given MPC into another MPC that uses less than 2 |V| distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.

I&C Journal 2021 Journal Article

Consistency checking of STNs with decisions: Managing temporal and access-control constraints in a seamless way

• Matteo Zavatteri
• Carlo Combi
• Romeo Rizzi
• Luca Viganò

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN to model temporal plans with decisions. STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i. e. , complete truth value assignments to the propositions) they are relevant. In this paper, we deal with the use of STNDs for modeling and synthesizing execution strategies. We propose an incremental hybrid SAT-based consistency checking algorithm for STNDs that is faster than the one previously proposed and allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). We carry out an experimental evaluation with Kappa, a tool that we developed for STNDs. We also show that any STND can be easily translated into a disjunctive temporal network and vice versa.

AAAI Conference 2021 Conference Paper

Faster and Better Simple Temporal Problems

• Dario Ostuni
• Alice Raffaele
• Romeo Rizzi
• Matteo Zavatteri

In this paper we give a structural characterization and extend the tractability frontier of the Simple Temporal Problem (STP) by defining the class of the Extended Simple Temporal Problem (ESTP), which augments STP with strict inequalities and monotone Boolean formulae on inequations (i. e. , formulae involving the operations of conjunction, disjunction and parenthesization). A polynomial-time algorithm is provided to solve ESTP, faster than previous state-of-the-art algorithms for other extensions of STP that had been considered in the literature, all encompassed by ESTP. We show the practical competitiveness of our approach through a proof-ofconcept implementation and an experimental evaluation involving also state-of-the-art SMT solvers.

TCS Journal 2021 Journal Article

When a dollar makes a BWT

• Sara Giuliani
• Zsuzsanna Lipták
• Francesco Masillo
• Romeo Rizzi

The Burrows-Wheeler-Transform (BWT) is a reversible string transformation which plays a central role in text compression and is fundamental in many modern bioinformatics applications. The BWT is a permutation of the characters, which is in general better compressible and allows to answer several different query types more efficiently than the original string. It is easy to see that not every string is a BWT image, and exact characterizations of BWT images are known. We investigate a related combinatorial question. In many applications, a sentinel character $ is added to mark the end of the string, and thus the BWT of a string ending with $ contains exactly one $-character. Given a string w, we ask in which positions, if any, the $-character can be inserted to turn w into the BWT image of a word ending with $. We show that this depends only on the standard permutation of w and present a O ( n log ⁡ n ) -time algorithm for identifying all such positions, improving on the naive quadratic time algorithm. We also give a combinatorial characterization of such positions and develop bounds on their number and value. This is an extended version of [Giuliani et al. ICTCS 2019].

ICAPS Conference 2020 Conference Paper

Dynamic Controllability and (J, K)-Resiliency in Generalized Constraint Networks with Uncertainty

• Matteo Zavatteri
• Romeo Rizzi
• Tiziano Villa

A number of formal models have been proposed to address temporal and resource allocation problems under uncertainty. Such models are typically shipped with an embedded notion of dynamic controllability, enclosing the ability to always make the right decisions, during execution, according to the observed uncontrollable events that always happen. In the business process management community, resource allocation was recently studied to deal with uncontrollable choices, whereas in the security community it was studied to face the uncontrollable availability of resources. The latter is a kind of dynamic controllability known as resiliency where uncontrollable events might also not happen. To the best of our knowledge, approaches handling resiliency on top of dynamic controllability still remain unexplored. To bridge this gap, we propose Generalized Constraint Networks with Uncertainty (GCNUs), a model that we devised to address resource controllability more widely, boosting expressiveness while considering several sources of uncertainty simultaneously. We define dynamic controllability and (J, K)-resiliency of GCNUs. We reason on the structure of these problems, carry out a complexity analysis and provide algorithms to solve them.

OVERLAY Workshop 2019 Workshop Paper

Complexity of Weak, Strong and Dynamic Controllability of CNCUs

• Matteo Zavatteri
• Romeo Rizzi
• Tiziano Villa

TCS Journal 2019 Journal Article

Dynamic controllability of simple temporal networks with uncertainty: Simple rules and fast real-time execution

• Massimo Cairo
• Romeo Rizzi

Simple Temporal Networks (STNs) are a well-studied model for representing temporal constraints. They comprise a set of time-points (real-valued variables representing execution times) and binary difference constraints among them. Simple Temporal Networks with Uncertainty (STNUs) extend STNs in that some time-points (called contingent) are treated as exogenous variables, whose execution times, bound to fall within a given interval from the corresponding activation time-points (as specified by a “contingent link”), get revealed only during real-time execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the execution times of contingent time-points revealed during execution. In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying any of our rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the previous efficient algorithms for DC-checking. Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of the notion of DC among several variants of the semantics of STNUs, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O ( K N ) total time in a network with K ≥ 1 contingent links and N ≥ K time points, considerably improving the previous O ( N 3 ) -time bound.

I&C Journal 2019 Journal Article

Faster FPTASes for counting and random generation of Knapsack solutions

• Romeo Rizzi
• Alexandru I. Tomescu

In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w 1, …, w n and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from Gopalan et al. (2011) [9], Štefankovič et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5]. Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

TIME Conference 2019 Conference Paper

Hybrid SAT-Based Consistency Checking Algorithms for Simple Temporal Networks with Decisions

• Matteo Zavatteri
• Carlo Combi
• Romeo Rizzi
• Luca Viganò 0001

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN by adding decision time points to model temporal plans with decisions. A decision time point is a special kind of time point that once executed allows for deciding a truth value for an associated Boolean proposition. Furthermore, STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i. e. , complete truth value assignments to the propositions) they are relevant. Thus, an STND models a family of STNs each obtained as a projection of the initial STND onto a scenario. An STND is consistent if there exists a consistent scenario (i. e. , a scenario such that the corresponding STN projection is consistent). Recently, a hybrid SAT-based consistency checking algorithm (HSCC) was proposed to check the consistency of an STND. Unfortunately, that approach lacks experimental evaluation and does not allow for the synthesis of all consistent scenarios. In this paper, we propose an incremental HSCC algorithm for STNDs that (i) is faster than the previous one and (ii) allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). Then, we carry out an experimental evaluation with KAPPA, a tool that we developed for STNDs. Finally, we prove that STNDs and disjunctive temporal networks (DTNs) are equivalent.

OVERLAY Workshop 2019 Workshop Paper

Strong Controllability of Temporal Networks with Decisions

• Matteo Zavatteri
• Romeo Rizzi
• Tiziano Villa

I&C Journal 2018 Journal Article

Checking dynamic consistency of conditional hyper temporal networks via mean payoff games

• Carlo Comin
• Romeo Rizzi

Conditional Simple Temporal Network (CSTN ) is a constraint-based graph formalism for conditional temporal planning, which may be viewed as an extension of Simple Temporal Networks. Recently, STN s have been generalized into Hyper Temporal Networks (HyTN s), by considering weighted directed hypergraphs where each hyperarc models a disjunctive temporal constraint. We introduce the Conditional Hyper Temporal Network (CHyTN) model, a natural extension and generalization of both CSTN s and HyTN s, obtained by blending them together. We show that deciding whether a given CSTN is dynamically-consistent is coNP-hard, and that deciding whether a given CHyTN is dynamically-consistent is PSPACE-hard. Next, we offer the first deterministic (pseudo) singly-exponential time algorithm for checking DC in CHyTNs and CSTN s. To analyze the computational complexity of the proposed algorithm, we introduce a refined notion of DC, named ϵ-DC, presenting a sharp lower bounding analysis on the critical value of the reaction time where a conditional temporal network transits from being, to not being, dynamically-consistent.

TIME Conference 2018 Conference Paper

Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty

• Massimo Cairo
• Luke Hunsberger
• Romeo Rizzi

Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, together with a set of binary constraints, each of the form Y <= X+w. The problem of finding a feasible schedule (i. e. , an assignment of real numbers to time-points such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph. Simple Temporal Networks with Uncertainty (STNUs) augment STNs to include contingent links that can be used, for example, to represent actions with uncertain durations. The duration of a contingent link is not controlled by the planner, but is instead controlled by a (possibly adversarial) environment. Each contingent link has the form, <A, l, u, C>, where 0 < l <= u < infty. Once the planner executes the activation time-point A, the environment must execute the contingent time-point C at some time A+Delta, where Delta in [l, u]. Crucially, the planner does not know the value of Delta in advance, but only discovers it when C executes. An STNU is dynamically controllable (DC) if there is a strategy that the planner can use to execute all of the non-contingent time-points, such that all of the constraints are guaranteed to be satisfied no matter which durations the environment chooses for the contingent links. The strategy can be dynamic in that it can react in real time to the contingent durations it observes. Recently, an upper bound of O(N^3) was given for the DC-checking problem for STNUs, where N is the number of time-points. This paper introduces a new algorithm, called the RUL^- algorithm, for solving the DC-checking problem for STNUs that improves on the O(N^3) bound. The worst-case complexity of the RUL^- algorithm is O(MN+K^2N+KN log N), where N is the number of time-points, M is the number of constraints, and K is the number of contingent time-points. If M is O(N^2), then the complexity reduces to O(N^3); however, in sparse graphs the complexity can be much less. For example, if M is O(N log N), and K is O(sqrt{N}), then the complexity of the RUL^- algorithm reduces to O(N^2 log N). The RUL^- algorithm begins by using the Bellman-Ford algorithm to compute a potential function. It then performs at most 2K rounds of computations, interleaving novel applications of Dijkstra's algorithm to (1) generate new edges and (2) update the potential function in response to those new edges. The constraint-propagation/edge-generation rules used by the RUL^- algorithm are distinguished from related work in two ways. First, they only generate unlabeled edges. Second, their applicability conditions are more restrictive. As a result, the RUL^- algorithm requires only O(K) rounds of Dijkstra's algorithm, instead of the O(N) rounds required by other approaches. The paper proves that the RUL^- algorithm is sound and complete for the DC-checking problem for STNUs.

MFCS Conference 2018 Conference Paper

Listing Subgraphs by Cartesian Decomposition

• Alessio Conte
• Roberto Grossi
• Andrea Marino 0001
• Romeo Rizzi
• Luca Versari

We investigate a decomposition technique for listing problems in graphs and set systems. It is based on the Cartesian product of some iterators, which list the solutions of simpler problems. Our ideas applies to several problems, and we illustrate one of them in depth, namely, listing all minimum spanning trees of a weighted graph G. Here iterators over the spanning trees for unweighted graphs can be obtained by a suitable modification of the listing algorithm by [Shioura et al. , SICOMP 1997], and the decomposition of G is obtained by suitably partitioning its edges according to their weights. By combining these iterators in a Cartesian product scheme that employs Gray coding, we give the first algorithm which lists all minimum spanning trees of G in constant delay, where the delay is the time elapsed between any two consecutive outputs. Our solution requires polynomial preprocessing time and uses polynomial space.

TIME Conference 2018 Conference Paper

On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier

• Carlo Comin
• Romeo Rizzi

In 2005 T. K. S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of temporal variables, and a finite set of temporal constraints each of which can be either one of the following three types: (t_1) two-variable linear-difference simple constraint; (t_2) single-variable disjunction of many interval constraints; (t_3) two-variable disjunction of two interval constraints only. Kumar showed that RDTPs are solvable in deterministic strongly polynomial time by reducing them to the Connected Row-Convex (CRC) constraints satisfaction problem, also devising a faster randomized algorithm. Instead, the most general form of DTPs allows for multi-variable disjunctions of many interval constraints and it is NP-complete. This work offers a deeper comprehension on the tractability of RDTPs, leading to an elementary deterministic strongly polynomial time algorithm for them, significantly improving the asymptotic running times of all the previous deterministic and randomized solutions. The result is obtained by reducing RDTPs to the Single-Source Shortest Paths (SSSP) and the 2-SAT problem (jointly), instead of reducing to CRCs. In passing, we obtain a faster (quadratic time) algorithm for RDTPs having only {t_1, t_2}-constraints and no t_3-constraint. As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a disjunctive strict generalization of Simple Temporal Networks (STNs) based on hypergraphs: we prove that solving temporal problems having only t_2-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in NP cap co-NP and admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only t_3-constraints and either only multi-tail or only multi-head hyperarc-constraints turns out strongly NP-complete.

TIME Conference 2017 Conference Paper

A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results

• Massimo Cairo
• Luke Hunsberger
• Roberto Posenato
• Romeo Rizzi

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network to include a new kind of time-points, called observation time-points. The execution of an observation time-point generates information in real time, specifically, the truth value of a propositional letter. In addition, time-points and temporal constraints may be labeled by conjunctions of (positive or negative) propositional letters. A CSTN is called dynamically consistent (DC) if there exists a dynamic strategy for executing its time-points such that no matter how the observations turn out during execution, the time-points whose labels are consistent with those observations have all been executed, and the constraints whose labels are consistent with those observations have all been satisfied. The strategy is dynamic in that its execution decisions may react to observations. The original formulation of CSTNs included propositional labels only on time-points, but the DC-checking algorithm was impractical because it was based on a conversion of the semantic constraints into an exponentially-sized Disjunctive Temporal Network. Later work added propositional labels to temporal constraints, and yielded a sound-and-complete propagation-based DC-checking algorithm, empirically demonstrated to be practical across a variety of CSTNs. This paper introduces a streamlined version of a CSTN in which propositional labels may appear on constraints, but not on time-points. This change simplifies the definition of the DC property, as well as the propagation rules for the DC-checking algorithm. It also simplifies the proofs of the soundness and completeness of those rules. This paper provides two translations from traditional CSTNs to streamlined CSTNs. Each translation preserves the DC property and, for any DC network, ensures that any dynamic execution strategy for that network can be extended to a strategy for its streamlined counterpart. Finally, this paper presents an empirical comparison of two versions of the DC-checking algorithm: the original version and a simplified version for streamlined CSTNs. The comparison is based on CSTN benchmarks from earlier work. For small-sized CSTNs, the original version shows the best performance, but the performance difference between the two versions decreases as the number of time-points in the CSTN increases. We conclude that the simplified algorithm is a practical alternative for checking the dynamic consistency of CSTNs.

TIME Conference 2017 Conference Paper

Dynamic Controllability Made Simple

• Massimo Cairo
• Romeo Rizzi

Simple Temporal Networks with Uncertainty (STNUs) are a well-studied model for representing temporal constraints, where some intervals (contingent links) have an unknown but bounded duration, discovered only during execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the actual duration of contingent links revealed during execution. In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying our sound rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the polynomial-time algorithms for DC-checking. Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of several variants of the notion of DC, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O(KN) total time in a network with K contingent links and N time points, considerably improving the previous O(N^3)-time bound.

TIME Conference 2017 Conference Paper

Incorporating Decision Nodes into Conditional Simple Temporal Networks

• Massimo Cairo
• Carlo Combi
• Carlo Comin
• Luke Hunsberger
• Roberto Posenato
• Romeo Rizzi
• Matteo Zavatteri

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters. Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network. This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs: (1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.

SODA Conference 2017 Conference Paper

The Complexity of Simulation and Matrix Multiplication

• Massimo Cairo
• Romeo Rizzi

AAAI Conference 2016 Conference Paper

Decoding Hidden Markov Models Faster Than Viterbi Via Online Matrix-Vector (max, +)-Multiplication

• Massimo Cairo
• Gabriele Farina
• Romeo Rizzi

In this paper, we present a novel algorithm for the maximum a posteriori decoding (MAPD) of timehomogeneous Hidden Markov Models (HMM), improving the worst-case running time of the classical Viterbi algorithm by a logarithmic factor. In our approach, we interpret the Viterbi algorithm as a repeated computation of matrix-vector (max, +)multiplications. On time-homogeneous HMMs, this computation is online: a matrix, known in advance, has to be multiplied with several vectors revealed one at a time. Our main contribution is an algorithm solving this version of matrix-vector (max, +)-multiplication in subquadratic time, by performing a polynomial preprocessing of the matrix. Employing this fast multiplication algorithm, we solve the MAPD problem in O(mn2 / log n) time for any time-homogeneous HMM of size n and observation sequence of length m, with an extra polynomial preprocessing cost negligible for m > n. To the best of our knowledge, this is the first algorithm for the MAPD problem requiring subquadratic time per observation, under the assumption – usually verified in practice – that the transition probability matrix does not change with time.

TIME Conference 2016 Conference Paper

Dynamic Controllability of Conditional Simple Temporal Networks Is PSPACE-complete

• Massimo Cairo
• Romeo Rizzi

Even after the proposal of various solution algorithms, the precise computational complexity of checking whether a Conditional Temporal Network is Dynamically Controllable had still remained widely open. This issue gets settled in this paper which provides constructions, algorithms, and bridging lemmas and arguments to formally prove that: (1) the problem is PSPACE-hard, and (2) the problem lies in PSPACE.

TIME Conference 2016 Conference Paper

Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks

• Massimo Cairo
• Carlo Comin
• Romeo Rizzi

Conditional Simple Temporal Network CSTN is a constraint-based graph-formalism for conditional temporal planning. Three notions of consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic-Consistency (DC) is the most interesting notion, but it is also the most challenging. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced ε-DC (a refined, more realistic, notion of DC), and provided an algorithmic solution to it. Next, given that DC implies ε-DC for some sufficiently small ε > 0, and that for every ε > 0 it holds that ε-DC implies DC, we offered a sharp lower bounding analysis on the critical value of the reaction-time ε under which the two notions coincide. This delivered the first (pseudo) singly-exponential time algorithm for the DC-Checking of CSTNs. However, the ε-DC notion is interesting per se, and the ε-DC-Checking algorithm in [Comin and Rizzi, TIME 2015] rests on the assumption that the reaction-time satisfies ε > 0, leaving unsolved the question of what happens when ε = 0. In this work, we introduce and study π-DC, a sound notion of DC with an instantaneous reaction-time (i. e. one in which the planner can react to any observation at the same instant of time in which the observation is made). Firstly, we demonstrate by a counter-example that π-DC is not equivalent to 0-DC, and that 0-DC is actually inadequate for modeling DC with an instantaneous reaction-time. This shows that the main results obtained in our previous work do not apply directly, as they were formulated, to the case of ε = 0. Motivated by this observation, as a second contribution, our previous tools are extended in order to handle π-DC, and the notion of ps-tree is introduced, also pointing out a relationship between π-DC and HyTN-Consistency. Thirdly, a simple reduction from π-DC-Checking to DC-Checking is identified. This allows us to design and to analyze the first sound-and-complete π-DC-Checking procedure. Remarkably, the time complexity of the proposed algorithm remains (pseudo) singly-exponential in the number of propositional letters.

SODA Conference 2016 Conference Paper

New Bounds for Approximating Extremal Distances in Undirected Graphs

• Massimo Cairo
• Roberto Grossi
• Romeo Rizzi

We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2 – ∊ )-approximation of the diameter or a (5/3 – ∊ )-approximation of all the eccentricities in O ( m 2– δ ) time for any ∊, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 – 1/2 k )-approximation of the diameter and the radius and a (3 – 4/(2 k + 1))-approximation of all eccentricities in expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h -dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.

TIME Conference 2015 Conference Paper

Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: A Singly-Exponential Time DC-checking

• Carlo Comin
• Romeo Rizzi

Conditional Simple Temporal Network (CSTN) is a constraint-based graph-formalism for conditional temporal planning. It offers a more flexible formalism than the equivalent CSTP model of Tsamardinos, Vidal and Pollack, from which it was derived mainly as a sound formalization. Three notions of consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic consistency is the most interesting notion, but it is also the most challenging and it was conjectured to be hard to assess. Tsamardinos, Vidal and Pollack gave a doubly-exponential time algorithm for deciding whether a CSTN is dynamically-consistent and to produce, in the positive case, a dynamic execution strategy of exponential size. In the present work we offer a proof that deciding whether a CSTN is dynamically-consistent is coNP-hard and provide the first singly-exponential time algorithm for this problem, also producing a dynamic execution strategy whenever the input CSTN is dynamically-consistent. The algorithm is based on a novel connection with Mean Payoff Games, a family of two-player infinite games played on finite graphs, well known for having applications in model-checking and formal verification. The presentation of such connection is mediated by the Hyper Temporal Network model, a tractable generalization of Simple Temporal Networks whose consistency checking is equivalent to determining Mean Payoff Games. In order to analyse the algorithm we introduce a refined notion of dynamic-consistency, named ε-dynamic-consistency, and present a sharp lower bounding analysis on the critical value of the reaction time where the CSTN transits from being, to not being, dynamically-consistent. The proof technique introduced in this analysis of the reaction time is applicable more generally when dealing with linear difference constraints which include strict inequalities.

TCS Journal 2015 Journal Article

On the complexity of the vector connectivity problem

• Ferdinando Cicalese
• Martin Milanič
• Romeo Rizzi

We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph G with a requirement r ( v ) for each vertex v, VecCon asks for a minimum cardinality set S of vertices such that every vertex v ∈ V ∖ S is connected to S via r ( v ) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n-vertex graphs to within a factor of log ⁡ n + 2, leaving open the question of whether the problem is NP-hard on general graphs. We show that VecCon is APX-hard in general graphs, and NP-hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs.

TIME Conference 2015 Conference Paper

The Price of Evolution in Temporal Databases

• Carlo Combi
• Romeo Rizzi
• Pietro Sala

Temporal Functional Dependencies (TFDs for short) are functional dependencies that predicate on temporal databases characterized by a special temporal dimension called valid time (VT). In [1] Combi et al. proposed a uniform framework that subsumes many of the TFDs proposed in literature and, by the combination of them, allow us to express finer constraints. Some interesting constraints are the Temporally Mixed Functional Dependencies (TMFD for short) that allow one to write constraints on the evolution of the data in the database. The problem of checking a TMFD against an instance of a temporal schema is polynomial. We will show that when approximation comes into play (i. e. , we look for TMFD holding for almost all database tuples) the problem turns out to be NP-Complete. Moreover we introduce a type of association rules build over TMFD called Temporally Mixed Association Rule (TMAR). We prove that verifying TMAR under approximation is still NP-Complete, by reducing it to a novel problem on directed acyclic graphs.

TIME Conference 2014 Conference Paper

A Tractable Generalization of Simple Temporal Networks and Its Relation to Mean Payoff Games

• Carlo Comin
• Roberto Posenato
• Romeo Rizzi

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. We introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints. In a Hyper Temporal Network a single temporal constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. As in STNs, a HyTN is consistent when a real value can be assigned to each temporal variable satisfying all the constraints. We show the computational complexity for this generalization and propose effective reduction algorithms for checking consistency of HyTNs unveiling the link with the field of Mean Payoff Games. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, as we show, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs allow to express natural constraints that cannot be expressed by HySTNs like "trigger off an event exactly d min after the occurrence of the last event in a set".

TCS Journal 2014 Journal Article

Complexity insights of the Minimum Duplication problem

• Guillaume Blin
• Paola Bonizzoni
• Riccardo Dondi
• Romeo Rizzi
• Florian Sikora

The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. Recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced, where the goal is to find all pre-duplications, that is duplications that in the evolution precede the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite. First of all, we prove that the Minimum Duplication problem is APX -hard, even when the input consists of five uniquely leaf-labeled gene trees (improving upon known results on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently with a randomized algorithm when the input gene trees have bounded depth. An extended abstract of this paper appeared in SOFSEM 2012 [1].

TCS Journal 2014 Journal Article

Set graphs. II. Complexity of set graph recognition and similar problems

• Martin Milanič
• Romeo Rizzi
• Alexandru I. Tomescu

A graph G is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional. Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size.

TIME Conference 2013 Conference Paper

Optimal Design of Consistent Simple Temporal Networks

• Romeo Rizzi
• Roberto Posenato

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of minimum and maximum distance constraints between pairs of temporal variables. During construction of an STN, it is possible that the network presents some constraint violations that need to be resolved. One way to solve such violations is to remove a minimal number of constraints, already shown to be an APX-hard problem. Another way is relaxing some constraints in different ways till violations are solved and choosing the best configuration according to one or more criteria. In this paper, assuming that it is possible to increase any constraint bound of an STN paying a constraint-specific cost, we exhibit a polynomial-time algorithm that repairs an STN eliminating all constraint violations at minimum global cost.

SODA Conference 2013 Conference Paper

Optimal Listing of Cycles and st-Paths in Undirected Graphs

• Etienne Birmelé
• Rui A. Ferreira
• Roberto Grossi
• Andrea Marino 0001
• Nadia Pisanti
• Romeo Rizzi
• Gustavo Sacomoto

The classical problem of efficiently listing all the simple cycles in a graph has been studied since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most efficient solution was presented by Johnson [SIAM J. Computing, 1975] and takes O ((η + 1)( m + n )) time. This solution is not optimal for undirected graphs: nevertheless, no theoretical improvements have been proposed in the past decades. We present the first optimal solution to list all the simple cycles in an undirected graph G. Specifically, let ( G ) denote the set of all these cycles (| ( G )| = η). For a cycle c ∊ ( G ), let | c | denote the number of edges in c. Our algorithm requires time and is asymptotically optimal: Ω( m ) time is necessarily required to read G as input, and time is required to list the output. We also present the first optimal solution to list all the simple paths from s to t (shortly, st -paths) in an undirected graph G. Let st ( G ) denote the set of st -paths in G and, for an st -path π ∊ st ( G ), let |π| be the number of edges in π. Our algorithm lists all the st -paths in G optimally in time.

TCS Journal 2010 Journal Article

Complexity issues in color-preserving graph embeddings

• Gaëlle Brevier
• Romeo Rizzi
• Stéphane Vialette

In the context of comparative analysis of protein–protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein–protein interaction graph (target graph) of another species with respect to (w. r. t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively.

TCS Journal 2010 Journal Article

Finding common structured patterns in linear graphs

• Guillaume Fertin
• Danny Hermelin
• Romeo Rizzi
• Stéphane Vialette

A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting ( ⊏ ) or crossing ( ≬ ). Given a family of linear graphs, and a non-empty subset R ⊆ { <, ⊏, ≬ }, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for { <, ≬ } -structured patterns and { ⊏, ≬ } -structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2 ℋ ( k ) for { <, ≬ } -structured patterns, (ii) k 1 / 2 for { ⊏, ≬ } -structured patterns, and (iii) O ( k log k ) for { <, ⊏, ≬ } -structured patterns, where k is the size of the optimal solution and ℋ ( k ) = ∑ i = 1 k 1 / i is the k th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right.

I&C Journal 2008 Journal Article

The Minimum Substring Cover problem

• Danny Hermelin
• Dror Rawitz
• Romeo Rizzi
• Stéphane Vialette

In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding.

MFCS Conference 2005 Conference Paper

Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs

• Guillaume Fertin
• Romeo Rizzi
• Stéphane Vialette

Abstract In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the protein-protein interaction graph H of another species with respect to (w. r. t.) orthologous proteins. Two problems are considered: the Exact -( μ G, μ H )- Matching problem and the Max -( μ G, μ H ) problem, where μ G (resp. μ H ) denotes in both problems the maximum number of orthologous proteins in H (resp. G ) of a protein in G (resp. H ). Following [FLV04], the Exact -( μ G, μ H )- Matching problem asks for an injective homomorphism of G to H w. r. t. orthologous proteins. The optimization version is called the Max -( μ G, μ H )- Matching problem and is concerned with finding an injective mapping of a graph G to a graph H w. r. t. orthologous proteins that matches as many edges of G as possible. For both problems, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters μ G and μ H.

TCS Journal 2005 Journal Article

Polynomial and APX-hard cases of the individual haplotyping problem

• Vineet Bafna
• Sorin Istrail
• Giuseppe Lancia
• Romeo Rizzi

SNP haplotyping problems have been the subject of extensive research in the last few years, and are one of the hottest areas of Computational Biology today. In this paper we report on our work of the last two years, whose preliminary results were presented at the European Symposium on Algorithms (Proceedings of the Annual European Symposium on Algorithms (ESA), Vol. 2161. Lecture Notes in Computer Science, Springer, 2001, pp. 182–193.) and Workshop on Algorithms in Bioinformatics (Proceedings of the Annual Workshop on Algorithms in Bioinformatics (WABI), Vol. 2452. Lecture Notes in Computer Science, Springer, 2002, pp. 29–43.). We address the problem of reconstructing two haplotypes for an individual from fragment assembly data. This problem will be called the Single Individual Haplotyping Problem. On the positive side, we prove that the problem can be solved effectively for gapless data, and give practical, dynamic programming algorithms for its solution. On the negative side, we show that it is unlikely that polynomial algorithms exist, even to approximate the solution arbitrarily well, when the data contain gaps. We remark that both the gapless and gapped data arise in different real-life applications.