Search

A procedure for quantifying the U $5f$ electrons' covalence and degree of localization in U intermetallic compounds is presented. To this end, bulk sensitive hard and soft x-ray photoelectron spectroscopy were utilized in combination with density-functional theory (DFT) plus dynamical mean-field theory (DMFT) calculations. The energy dependence of the photoionization cross-sections allows the disentanglement of the U\,$5f$ contribution to the valence band from the various other atomic subshells so that the computational parameters in the DFT\,+\,DMFT can be reliably determined. Applying this method to UGa$_2$ and UB$_2$ as model compounds from opposite ends of the (de)localization range, we have achieved excellent simulations of the valence band and core-level spectra. The width in the distribution of atomic U\,$5f$ configurations contributing to the ground state, as obtained from the calculations, quantifies the correlated nature and degree of localization of the U\,5$f$. The findings permit answering the longstanding question why different spectroscopic techniques give seemingly different numbers for the U 5$f$ valence in intermetallic U compounds., Comment: 14 pages, 9 figures

We investigate the topological superconductor candidate UTe$_2$ using high-resolution valence-band resonant inelastic x-ray scattering at the U $M_{4,5}$-edges. We observe atomic-like low-energy excitations that support the correlated nature of this unconventional superconductor. These excitations originate from the U $5f^2$ configuration, which is unexpected since the short Te2-Te2 distances exclude Te2 being 2-. By utilizing the photoionization cross-section dependence of the photoemission spectra in combination with band structure calculations, we infer that the stabilization of the U $5f^2$ configuration is due to the U $6d$ bonding states in the U-dimers acting as a charge reservoir. Our results emphasize that the description of the physical properties should commence with a $5f^2$ $ansatz$., Comment: 9 pages, 5 figures, article

In this work we extend the concept of out/in-branchings spanning the vertices of a digraph (also called directed spanning trees) to temporal graphs, which are digraphs where arcs are available only at prescribed times. While the literature has focused on minimum weight/earliest arrival time Temporal Out-Branchings (TOB), we solve the problem for other optimization criteria. In particular, we define five different types of TOBs based on the optimization of the travel duration (FT-TOB), of the departure time (LD-TOB), of the number of transfers (MT-TOB), of the total waiting time (MW-TOB), and of the travelling time (ST-TOB). For D$\in \{$LD,MT,ST$\}$, we provide necessary and sufficient conditions for the existence of a spanning D-TOB; when it does not exist, we characterize the maximum vertex set that a D-TOB can span. Moreover, we provide a log linear algorithm for computing such branchings. For D$\in \{$FT,MW$\}$, we prove that deciding the existence of a spanning D-TOB is NP-complete; we also show that the same results hold for optimal temporal in-branchings. Finally, we investigate the related problem of computing a spanning temporal subgraph with the minimum number of arcs and optimizing a chosen criterion D. This problem turns out to be NP-hard for any D. The hardness results are quite surprising, as computing optimal paths between nodes can always be done in polynomial time., Comment: 26 pages, figures 9, Conference version published at FCT 2023

The application of pressure as well as the successive substitution of Ru with Fe in the hidden order (HO) compound URu$_2$Si$_2$ leads to the formation of the large moment antiferromagnetic phase (LMAFM). Here we have investigated the substitution series URu$_{2-x}$Fe$_x$Si$_2$ from $x$\,=\,0.0 to 2.0 by U\,4$f$ core-level photoelectron spectroscopy and have observed non-monotonic changes in the spectra. The initial increase and subsequent decrease of the spectral weight of the 4$f$ core level satellite with increasing $x$ stands for a non-monotonic 5$f$ filling across the substitution series. The competition of chemical pressure and increase of the density of states at the Fermi energy, both due to substitution of Ru with Fe, can explain such a behavior. An extended Doniach phase diagram including the $x$ dependence of the density of states is proposed. Also in URu$_{2-x}$Fe$_x$Si$_2$ the ground state is a singlet or quasi-doublet state consisting of two singlets. Hence, the formation of magnetic order in the URu$_{2-x}$Fe$_x$Si$_2$ substitution series must be explained within a singlet magnetism model., Comment: 10 pages, 7 figures

CeRh$_2$As$_2$ is a new multiphase superconductor with strong suggestions for an additional itinerant multipolar ordered phase. The modeling of the low temperature properties of this heavy fermion compound requires a quartet Ce$^{3+}$ crystal-field ground state. Here we provide the evidence for the formation of such a quartet state using x-ray spectroscopy. Core-level photoelectron and x-ray absorption spectroscopy confirm the presence of Kondo hybridization in CeRh$_2$As$_2$. The temperature dependence of the linear dichroism unambiguously reveils the impact of Kondo physics for coupling the Kramer's doublets into an effective quasi-quartet. Non-resonant inelastic x-ray scattering data find that the $|\Gamma_7^- \rangle$ state with its lobes along the 110 direction of the tetragonal structure ($xy$ orientation) contributes most to the multi-orbital ground state of CeRh$_2$As$_2$., Comment: 8 pages, 7 figures

Using high resolution tender-x-ray resonant inelastic scattering and hard-x-ray non-resonant inelastic scattering beyond the dipole limit we were able to detect electronic excitations in intermetallic UGa$_2$ that are highly atomic in nature. Analysis of the spectral lineshape reveals that the local $5f^2$ configuration characterizes the correlated nature of this ferromagnet. The orientation and directional dependence of the spectra indicate that the ground state is made of the $\Gamma_1$ singlet and/or $\Gamma_6$ doublet symmetry. With the ordered moment in the $ab$ plane, we infer that the magnetism originates from the higher lying $\Gamma_6$ doublet being mixed with the $\Gamma_1$ singlet due to inter-site exchange, qualifying UGa$_2$ to be a true quantum magnet. The ability to observe atomic excitations is crucial to resolve the on-going debate about the degree of localization versus itineracy in U intermetallics., Comment: 9 pages, 7 figures

A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, $\tau$. Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasingly (i.e., non-decreasing) depending on the scenario. Then, the classical concept of connected components and also of unilateral connected components in static graphs and digraphs naturally extends to the temporal setting. In this paper, we answer to the following fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size $k$, parameterized by $\tau$, by $k$, and by $k+\tau$? We show that this question has a different answer depending on the considered definition of component and whether the temporal graph is directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable? A quadratic algorithm is known but, contrary to the static case, we show that a better running time is unlikely unless SETH fails. (iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the definition of temporal component this test is NP-complete.

We investigated the electronic structure of the enigmatic CeRh$_3$B$_2$ using resonant inelastic scattering and x-ray absorption spectroscopy in combination with $ab$ $initio$ density functional calculations. We find that the Rh 4$d$ states are irrelevant for the high-temperature ferromagnetism and the Kondo effect. We also find that the Ce 4$f$ crystal-field strength is too small to explain the strong reduction of the Ce magnetic moment. The data reveal instead the presence of two different active Ce 4$f$ orbitals, with each coupling selectively to different bands in CeRh$_3$B$_2$. The inter-site hybridization of the |J=5/2,Jz=+/-1/2> crystal-field state and Ce 5$d$ band combined with the intra-site Ce 4$f$-5$d$ exchange creates the strong ferromagnetism, while hybridization between the |J=5/2,Jz=+/-5/2> and the B $sp$ in the $ab$-plane contributes to the Kondo interaction which causes the moment reduction. This orbital selective coupling explains the unique and seemingly contradictory properties of CeRh$_3$B$_2$., Comment: 15 pages, 14 figures

A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its lifetime $\tau$. Temporal walks are sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. Paths are temporal walks where no vertex repetition is allowed. A temporal vertex is a pair $(u,i)$ where $u$ is a vertex and $i\in[\tau]$ a timestep. In this paper we focus on the questions: (i) are there at least $k$ paths from a single source $s$ to a single target $t$, no two of which internally intersect on a temporal vertex? (ii) are there at most $h$ temporal vertices whose removal disconnects $s$ from $t$? Let $k^*$ be the maximum value $k$ for which the answer to (i) is YES, and let $h^*$ be the minimum value $h$ for which the answer to (ii) is YES. In static graphs, $k^*$ and $h^*$ are equal by Menger's Theorem and this is a crucial property to solve efficiently both (i) and (ii). In temporal graphs such equality has been investigated only focusing on disjoint walks rather than disjoint paths. In this context, we prove that $k^*$ is equal to $h^*$ if and only if $k^*$ is 1. We show that this implies a dichotomy for (i), which turns out to be polynomial-time solvable when $k \le 2$, and NP-complete for $k \ge 3$. Finally, we give hardness results and an XP algorithm for (ii).

CeRhSn with the Ce atoms forming a quasikagome lattice in the hexagonal plane has recently been discussed in the context of quantum criticality driven by magnetic frustration. Furthermore, it has been reported that the successive substitution of Rh by Pd leads to magnetic order. Here we have investigated the change of the 4$f$ occupation in the substitution series CeRh$_{1-x}$Pd$_x$Sn for for $x$ = 0, 0.1, 0.3, 0.5, 0.75 by means of photoelectron spectroscopy with hard x-rays (HAXPES). The quantitative analysis of the core level spectra with a combined full multiplet and configuration interaction analysis shows a smooth decrease of the 4$f^0$ contribution with rising $x$ due to an increase of the effective 4$f$ binding energy $\varepsilon_{4f}$ and the reduction of the effective hybridization $V_\text{eff}$. We further compare valence band data with the calculated partial density of states and find that the Pd 4$d$ states are about 1eV further away from the Ce 4$f$ states at the Fermi energy than the Rh 4$d$ states. In fact, the effective binding energy $\varepsilon_{4f}$ of the 4$f$ states in the configuration interaction analysis of the core level spectra decreases by the same amount., Comment: 10 pages, 9 figures

An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph $G$ at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of K\"{o}nigsberg problem in 1736. What if Euler had to take a bus? In a temporal graph $(G,\lambda)$, with $\lambda: E(G)\to 2^{[\tau]}$, an edge $e\in E(G)$ is available only at the times specified by $\lambda(e)\subseteq [\tau]$, in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this scenario, even though several translations of Eulerian trails and walks are possible in temporal terms, only a very particular variation has been exploited in the literature, specifically for infinite dynamic networks (Orlin, 1984). In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether $(G,\lambda)$ has a temporal walk or trail is polynomial, while deciding whether it has a local trail is NP-complete even if it has lifetime~2. In contrast, in the general case, solving any of these problems is NP-complete, even under very strict hypothesis.

The crystal-field ground state wave function of CeCu$_2$Si$_2$ has been investigated with linear polarized $M$-edge x-ray absorption spectroscopy from 250mK to 250K, thus covering the superconducting ($T_{\text{c}}$=0.6K), the Kondo ($T_{\text{K}}$$\approx$20K) as well as the Curie-Weiss regime. The comparison with full-multiplet calculations shows that the temperature dependence of the experimental linear dichroism is well explained with a $\Gamma_7^{(1)}$ crystal-field ground-state and the thermal population of excited states at around 30meV. The crystal-field scheme does not change throughout the entire temperature range thus making the scenario of orbital switching unlikely. Spectroscopic evidence for the presence of the Ce 4$f^0$ configuration in the ground state is consistent with the possibility for a multi-orbital character of the ground state. We estimate from the Kondo temperature and crystal-field splitting energies that several percents of the higher lying $\Gamma_6$ state and $\Gamma_7^{(2)}$ crystal-field states are mixed into the primarily $\Gamma_7^{(1)}$ ground state. This estimate is also supported by re-normalized band-structure calculations that uses the experimentally determined crystal-field scheme., Comment: 8 pages, 5 figures

A $k$-truss is an edge-induced subgraph $H$ such that each of its edges belongs to at least $k-2$ triangles of $H$. This notion has been introduced around ten years ago in social network analysis and security, as a form of cohesive subgraph that is rich of triangles and less stringent than the clique. The \emph{trussness} of a graph is the maximum $k$ such that a $k$-truss exists. The problem of computing $k$-trusses has been largely investigated from the practical and engineering point of view. On the other hand, the theoretical side of the problem has received much less attention, despite presenting interesting challenges. The existing methods share a common design, based on iteratively removing the edge with smallest support, where the support of an edge is the number of triangles containing it. The aim of this paper is studying algorithmic aspects of graph trussness. While it is possible to show that the time complexity of computing exactly the graph trussness and that of counting/listing all triangles is inherently the same, we provide efficient algorithms for estimating its value, under suitable conditions, with significantly lower complexity than the exact approach. In particular, we provide a $(1 \pm \epsilon)$-approximation algorithm that is asymptotically faster than the exact approach, on graphs which contain $\omega(m \, polylog(n))$ triangles, and has the same running time on graphs that do not. For the latter case, we also show that it is impossible to obtain an approximation algorithm with faster running time than the one of the exact approach when the number of triangles is $O(m)$, unless well known conjectures on triangle-freeness and Boolean matrix multiplication are false.

Using inelastic x-ray scattering beyond the dipole limit and hard x-ray photoelectron spectroscopy we establish the dual nature of the U $5f$ electrons in UM$_2$Si$_2$ (M = Pd, Ni, Ru, Fe), regardless of their degree of delocalization. We have observed that the compounds have in common a local atomic-like state that is well described by the U $5f^2$ configuration with the $\Gamma_1^{(1)}$ and $\Gamma_2$ quasi-doublet symmetry. The amount of the U 5$f^3$ configuration, however, varies considerably across the UM$_2$Si$_2$ series, indicating an increase of U5$f$ itineracy in going from M=Pd to Ni to Ru, and to the Fe compound. The identified electronic states explain the formation of the very large ordered magnetic moments in UPd$_2$Si$_2$ and UNi$_2$Si$_2$, the availability of orbital degrees of freedom needed for the hidden order in URu$_2$Si$_2$ to occur, as well as the appearance of Pauli paramagnetism in UFe$_2$Si$_2$. A unified and systematic picture of the U$M_2$Si$_2$ compounds may now be drawn, thereby providing suggestions for new experiments to induce hidden order and/or superconductivity in U compounds with the tetragonal body-centered ThCr$_2$Si$_2$ structure.

A temporal digraph ${\cal G}$ is a triple $(G, \gamma, \lambda)$ where $G$ is a digraph, $\gamma$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $\lambda$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted at given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching ${\cal B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${\cal B}_1$ and ${\cal B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions., Comment: 16 pages, 4 figures

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of Maximal Bipartite Subgraphs, Maximal k-Degenerate Subgraphs (for bounded k), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or "supergraph", and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential: we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met., Comment: A preliminary version of this work appeared in STOC 2019: https://dl.acm.org/doi/10.1145/3313276.3316402

Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) uses a ground set U (e.g., the network nodes) and an indicator F, subset of 2^U, of which subsets of U have the required property. For the problem of listing all sets in F maximal under inclusion, the ambitious goal is to cover a large class of set systems, preserving at the same time the efficiency of the enumeration. Among the existing algorithms, the best-known ones list the maximal subsets in time proportional to their number but may require exponential space. In this paper we improve the state of the art in two directions by introducing an algorithmic framework that, under standard suitable conditions, simultaneously (i) extends the class of problems that can be solved efficiently to strongly accessible set systems, and (ii) reduces the additional space usage from exponential in |U| to stateless, thus accounting for just O(q) space, where q <= |U| is the largest size of a maximal set in F

Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$ is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the $k$ most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the paper, we prove that it is not solvable in time $\O(|E|^{2-\epsilon})$ on directed graphs, for any constant $\epsilon>0$, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the $k$ most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top $k$ nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the $10$ most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page $p$ to a page $q$ if $p$ contains a link to $q$.

Although web crawlers have been around for twenty years by now, there is virtually no freely available, opensource crawling software that guarantees high throughput, overcomes the limits of single-machine systems and at the same time scales linearly with the amount of resources available. This paper aims at filling this gap, through the description of BUbiNG, our next-generation web crawler built upon the authors' experience with UbiCrawler [Boldi et al. 2004] and on the last ten years of research on the topic. BUbiNG is an opensource Java fully distributed crawler; a single BUbiNG agent, using sizeable hardware, can crawl several thousands pages per second respecting strict politeness constraints, both host- and IP-based. Unlike existing open-source distributed crawlers that rely on batch techniques (like MapReduce), BUbiNG job distribution is based on modern high-speed protocols so to achieve very high throughput.

Closeness is an important centrality measure widely used in the analysis of real-world complex networks. In particular, the problem of selecting the k most central nodes with respect to this measure has been deeply analyzed in the last decade. However, even for not very large networks, this problem is computationally intractable in practice: indeed, Abboud et al have recently shown that its complexity is strictly related to the complexity of the All-Pairs Shortest Path (in short, APSP) problem, for which no subcubic "combinatorial" algorithm is known. In this paper, we propose a new algorithm for selecting the k most closeness central nodes in a graph. In practice, this algorithm significantly improves over the APSP approach, even though its worst-case time complexity is the same. For example, the algorithm is able to compute the top k nodes in few dozens of seconds even when applied to real-world networks with millions of nodes and edges. We will also experimentally prove that our algorithm drastically outperforms the most recently designed algorithm, proposed by Olsen et al. Finally, we apply the new algorithm to the computation of the most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie.

Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the \emph{cyclic} orientations of an undirected connected graph with $n$ vertices and $m$ edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations.We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with $\tilde{O}(m)$ delay time. Space usage is $O(m)$ with an additional setup cost of $O(n^2)$ time before the enumeration begins, or $O(mn)$ with a setup cost of $\tilde{O}(m)$ time.

Let $R$ be a commutative ring, $f \in R[X_1,\ldots,X_k]$ a multivariate polynomial, and $G$ a finite subgroup of the group of units of $R$ satisfying a certain constraint, which always holds if $R$ is a field. Then, we evaluate $\sum f(x_1,\ldots,x_k)$, where the summation is taken over all pairwise distinct $x_1,\ldots,x_k \in G$. In particular, let $p^s$ be a power of an odd prime, $n$ a positive integer coprime with $p-1$, and $a_1,\ldots,a_k$ integers such that $\varphi(p^s)$ divides $a_1+\cdots+a_k$ and $p-1$ does not divide $\sum_{i \in I}a_i$ for all non-empty proper subsets $I\subseteq \{1,\ldots,k\}$; then $$ \sum x_1^{a_1}\cdots x_k^{a_k} \equiv \frac{\varphi(p^s)}{\mathrm{gcd}(n,\varphi(p^s))}(-1)^{k-1}(k-1)! \,\,\bmod{p^s}, $$ where the summation is taken over all pairwise distinct $n$-th residues $x_1,\ldots,x_k$ modulo $p^s$ coprime with $p$., Comment: 10 pages, no figures. The article has been substantially rewritten and results have been improved. Old main result appears now as Corollary 4. Moreover, Theorem 2 has a proof which relies on a different argument

Entity-linking is a natural-language-processing task that consists in identifying the entities mentioned in a piece of text, linking each to an appropriate item in some knowledge base; when the knowledge base is Wikipedia, the problem comes to be known as wikification (in this case, items are wikipedia articles). One instance of entity-linking can be formalized as an optimization problem on the underlying concept graph, where the quantity to be optimized is the average distance between chosen items. Inspired by this application, we define a new graph problem which is a natural variant of the Maximum Capacity Representative Set. We prove that our problem is NP-hard for general graphs; nonetheless, under some restrictive assumptions, it turns out to be solvable in linear time. For the general case, we propose two heuristics: one tries to enforce the above assumptions and another one is based on the notion of hitting distance; we show experimentally how these approaches perform with respect to some baselines on a real-world dataset., Comment: In Proceedings GRAPHITE 2014, arXiv:1407.7671. The second and third authors were supported by the EU-FET grant NADINE (GA 288956)

Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, are unlike context-free grammars in that they do not have a binary normal form. In general, parsing with SCFGs takes space and time polynomial in the length of the input strings, but with the degree of the polynomial depending on the permutations of the SCFG rules. We consider linear parsing strategies, which add one nonterminal at a time. We show that for a given input permutation, the problems of finding the linear parsing strategy with the minimum space and time complexity are both NP-hard.

We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time taken to read the input graph plus the time to list the output, namely, the edges in each of the cycles. The algorithm uses a reduction to the problem of listing all the paths from a vertex s to a vertex t which we also solve optimally., Comment: 12 Pages, 7 Page Appendix