Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs.

In this thesis I present some results, which mainly concern finding algorithms for graphs problems, to which I worked on during my Ph.D with the supervision of my supervisors. In particular, as a first theme, it is presented a new temporal interpretation of the well studied \ClusterEditing which we called \EditTempClique (\ETC). In this regard, %at first it is shown that the corresponding versions in the temporal setting of any \NP-Hard version of \ClusterEditing is still \NP-Hard. Then, in this work, it is proved that \ETC is \NP-Complete even if we restrict the possible inputs to the class of temporal graphs with a path as their underlying graph. Furthermore, it is presented a result that shows that \ETC is instead tractable in polynomial time if the underlying graph is a path and the maximum number of appearances allowed for each of the edges of that path is fixed. Taking in mind the known key observation that a static graph is a cluster graph if and only if it does not contain any induced $P_3$, it is presented a local characterisation for cluster temporal graphs. This characterisation establishes that a temporal graph is a cluster temporal graph if and only if every subset of at most five vertices induces a cluster temporal graph. Using this characterisation, we obtain an \FPT~algorithm for \ETC parameterised simultaneously by the number of modifications and the lifetime (number of timesteps) of the input temporal graph. Furthermore, it is shown via a counterexample, that a cluster temporal graph can not be properly characterised by sets of at most four vertices. In the last Chapter of this thesis, at first it is proven a result on the realisation of distance matrices by $n-$cycles and then it is developed an algorithm that allows to establish if a given distance matrix $D$ can or cannot be realised by a weighted unicyclic graph or at least by a weighted tree. In case of affirmative answer, a second part of the algorithm reconstructs that graph. The algorithm takes $\mathcal O(n^4)$. Furthermore, it is shown that if the algorithm returns a unicyclic graph as a realisation of $D$, then this realisation is optimal.