# A Paper on CSTNs @ TIME2015 (Sept 23-25, 2015, University of Kassel, Germany).

Our Paper “*Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking*” was accepted to the “*22nd International Symposium on Temporal Representation and Reasoning (TIME2015)*“.

TIME2015 will be held at *University of Kassel*, Germany (September 23-25, 2015).

This is a joint work with *R. Rizzi*.

Pre-print link: manuscript, presentation.

# An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et. al. in 1977. As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e. maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama showed it is . In 2004, Makino and Uno sharpened the time delay to by generating all the children of a node in one single shot performed by computing a *square* fast matrix multiplication. In this paper, we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on *rectangular* fast matrix multiplication in order to compute all children of nodes in one shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from to .

Download: Manuscript.

# Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking.

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 combinatorial games on 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 analyze 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 is applicable more in general when dealing with linear difference constraints which include strict inequalities.

Download link: manuscript.

# Sorting With Forbidden Intermediates

A wide range of applications, most notably in comparative

genomics, involve the computation of a shortest sorting sequence of op-

erations for a given permutation, where the set of allowed operations

is fixed beforehand. Such sequences are useful for instance when recon-

structing potential scenarios of evolution between species, or when trying

to assess their similarity. We revisit those problems by adding a new con-

straint on the sequences to be computed: they must avoid a given set of forbidden intermediates, which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution.

Download link: manuscript.

# An Improved Upper Bound on Time Complexity of Value Problem and Optimal Strategy Synthesis in MPGs.

# The end of TIME…

<a href=”https://carlocomin.files.wordpress.com/2014/09/20140908_073425.jpg”

TIME2014 ended on wednesday.

Our paper on Hyper Temporal Networks can be found here:

article presentation handout

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 STNs like “trigger off

an event exactly δ min after the occurrence of the last event in

a set”.