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.

TIME2015

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 O(mn). In 2004, Makino and Uno sharpened the time delay to O(n^{\omega}) 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 n^2 nodes in one shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from O(n^{2.3728639}) to O(n^{2.093362}).

Download: Manuscript.

maximal_clique_listing

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 \epsilon-dynamic-consistency, and present a sharp lower bounding analysis on the critical value of the reaction time \hat{\varepsilon} where the CSTN transits from being, to not being, dynamically-consistent. The proof technique introduced in this analysis of \hat{\varepsilon} 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.

We prove the existence of a pseudo-polynomial O(|V|^2 |E|\, W) time algorithm for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor log(|V|\, W) the best previously known pseudo-polynomial upper bound due to Brim et al. (2011). The improvement hinges on a suitable characterization of values and optimal strategies in terms of reweightings.
Download link: manuscript.

The end of TIME…

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

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”.