skip to main content


Title: Eulerian Walks in Temporal Graphs
Abstract

An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graphGat least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph$$\varvec{(G,\lambda )}$$(G,λ), with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$λ:E(G)2[τ], an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$eE(G)is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$λ(e)[τ], 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 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$$\varvec{(G,\lambda )}$$(G,λ)has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$NP-complete even if$$\varvec{\tau = 2}$$τ=2. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$NP-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$XPalgorithms parametrized by$$\varvec{\tau }$$τfor walks, and by$$\varvec{\tau +tw(G)}$$τ+tw(G)for trails and local trails, where$$\varvec{tw(G)}$$tw(G)refers to the treewidth of$$\varvec{G}$$G.

 
more » « less
NSF-PAR ID:
10370097
Author(s) / Creator(s):
;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Algorithmica
Volume:
85
Issue:
3
ISSN:
0178-4617
Page Range / eLocation ID:
p. 805-830
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We explain recent LHCb measurements of the lepton universality ratios,$$R_{D^{(*)}}^{\tau /\ell }\equiv \frac{\mathcal {B}(\bar{B} \rightarrow D^{(*)+} \tau ^- \bar{\nu }_\tau )}{\mathcal {B}(\bar{B} \rightarrow D^{(*)+}\ell ^- \bar{\nu }_\ell )}$$RD()τ/B(B¯D()+τ-ν¯τ)B(B¯D()+-ν¯)and$${R(\Lambda _c^+)}^{\tau /\ell } \equiv \frac{\mathcal {B}(\Lambda _b \rightarrow \Lambda _c^+ \tau ^- \bar{\nu }_{\tau })}{\mathcal {B}(\Lambda _b \rightarrow \Lambda _c^+ \ell ^- \bar{\nu }_{\ell })}$$R(Λc+)τ/B(ΛbΛc+τ-ν¯τ)B(ΛbΛc+-ν¯)with$$\ell =\mu $$=μ, via new physics that affects$$R_D^{\tau /\ell }$$RDτ/and$$R(\Lambda _c^+)^{\tau /\ell }$$R(Λc+)τ/but not$$R_{D^*}^{\tau /\ell }$$RDτ/. The scalar operator in the effective theory for new physics is indicated. We find that the forward-backward asymmetry and$$\tau $$τpolarization in$$\bar{B} \rightarrow D^+ \tau ^{-} \bar{\nu }_{\tau }$$B¯D+τ-ν¯τand$$\Lambda _b \rightarrow \Lambda _c^+ \tau ^- \bar{\nu }_{\tau }$$ΛbΛc+τ-ν¯τdecays are significantly affected by the scalar interaction. We construct a simple two Higgs doublet model as a realization of our scenario and consider lepton universality in semileptonic charm and top decays, radiativeBdecay,B-mixing, and$$Z \rightarrow b \bar{b}$$Zbb¯.

     
    more » « less
  2. Abstract

    The radiation of steady surface gravity waves by a uniform stream$$U_{0}$$U0over locally confined (width$$L$$L) smooth topography is analyzed based on potential flow theory. The linear solution to this classical problem is readily found by Fourier transforms, and the nonlinear response has been studied extensively by numerical methods. Here, an asymptotic analysis is made for subcritical flow$$D/\lambda > 1$$D/λ>1in the low-Froude-number ($$F^{2} \equiv \lambda /L \ll 1$$F2λ/L1) limit, where$$\lambda = U_{0}^{2} /g$$λ=U02/gis the lengthscale of radiating gravity waves and$$D$$Dis the uniform water depth. In this regime, the downstream wave amplitude, although formally exponentially small with respect to$$F$$F, is determined by a fully nonlinear mechanism even for small topography amplitude. It is argued that this mechanism controls the wave response for a broad range of flow conditions, in contrast to linear theory which has very limited validity.

     
    more » « less
  3. Abstract

    Recent progress in microspherical superlens nanoscopy raises a fundamental question about the transition from super-resolution properties of mesoscale microspheres, which can provide a subwavelength resolution$$\sim \lambda /7$$λ/7, to macroscale ball lenses, for which the imaging quality degrades because of aberrations. To address this question, this work develops a theory describing the imaging by contact ball lenses with diameters$$3030<D/λ<4000covering this transition range and for a broad range of refractive indices$$1.31.3<n<2.1. Starting from geometrical optics we subsequently proceed to an exact numerical solution of the Maxwell equations explaining virtual and real image formation as well as magnificationMand resolution near the critical index$$n\approx 2$$n2which is of interest for applications demanding the highestMsuch as cellphone microscopy. The wave effects manifest themselves in a strong dependence of the image plane position and magnification on$$D/\lambda $$D/λ, for which a simple analytical formula is derived. It is demonstrated that a subwavelength resolution is achievable at$$D/\lambda \lesssim 1400$$D/λ1400. The theory explains the results of experimental contact-ball imaging. The understanding of the physical mechanisms of image formation revealed in this study creates a basis for developing applications of contact ball lenses in cellphone-based microscopy.

     
    more » « less
  4. Abstract

    We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$0-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$0-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$Ax=b, where$$A\in \mathbb {Z}^{m\times n}$$AZm×n,$${\varvec{b}}\in \mathbb {Z}^m$$bZmand$$\varvec{x}$$xis either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$0-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$R, to other subdomains such as$$\mathbb {Z}$$Z. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.

     
    more » « less
  5. Abstract

    For polyhedral constrained optimization problems and a feasible point$$\textbf{x}$$x, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\nabla _\varOmega f(\textbf{x})$$Ωf(x), has an orthogonal decomposition of the form$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$β(x)+φ(x). At a stationary point,$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$Ωf(x)=0so$$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$Ωf(x)reflects the distance to a stationary point. Away from a stationary point,$$\Vert \varvec{\beta }(\textbf{x})\Vert $$β(x)and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$φ(x)measure different aspects of optimality since$$\varvec{\beta }(\textbf{x})$$β(x)only vanishes when the KKT multipliers at$$\textbf{x}$$xhave the correct sign, while$$\varvec{\varphi }(\textbf{x})$$φ(x)only vanishes when$$\textbf{x}$$xis a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\Vert \varvec{\beta }(\textbf{x})\Vert $$β(x)and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$φ(x).

     
    more » « less