Sorting with Forbidden Intermediates

Our Paper “Sorting with Forbidden Intermediates (On (s,t)-Paths with Forbidden Vertices in Hypercube Graphs)”

has been accepted to the “3rd International Conference on Algorithms for Computational Biology (AlCoB2016), Trujillo, Spain, June 21-22, 2016.”

AlCoB2016 was held at Extremadura Centre for Advanced Technologies (CETA-CIEMAT), located at Trujillo, Spain, street Sola no. 1 (Conventual de San Francisco), June 21-22, 2016.

This is a joint work with Anthony Labarre, Romeo Rizzi, Stéphane Vialette.

Pre-print link: manuscript, presentation.

AlCoB2016

Advertisements

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.