A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. This definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however, are often temporal rather than static---the connections change over a period of time. And hence temporal graphs, rather than static graphs, are often better suited to model social networks. Motivated by this, we introduce a definition of temporal c-closed graphs, in which if two vertices u and v have at least c common neighbors during a short interval of time, then u and v are adjacent to each other around that time. Our pilot experiments show that several real-world temporal networks are c-closed for rather small values of c. We also study the computational problems of enumerating maximal cliques and other dense subgraphs in temporal c-closed graphs. A clique in a temporal graph is a subgraph that lasts for a certain period of time, during which every possible edge in the subgraph becomes active often enough; other dense subgraphs are defined similarly. We bound the number of such maximal dense subgraphs in a temporal c-closed graph that evolves slowly, and thus show that the corresponding enumeration problems admit efficient algorithms; by slow evolution, we mean that between consecutive time-steps, the local change in adjacencies remains small. Our work also adds to a growing body of literature on defining suitable structural parameters for temporal graphs that can be leveraged to design efficient algorithms.

Many works within robust combinatorial optimisation consider interval-valued costs or constraints. While most of these works focus on finding a unique solution following a robust criteria such as minimax, a few consider the problem of characterising a set of possibly optimal solutions. This paper is situated within this line of work, and considers the problem of exactly enumerating the set of possibly optimal matroids under interval-valued costs. We show in particular that each solution in this set can be obtained through a polynomial procedure, and provide an efficient algorithm to achieve the enumeration.

Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions (”contigs”) are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and $$\mathcal {NP}$$ -hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score.