In this paper, we study two graph convexity parameters: iteration time and general position number. The iteration time was defined in 1981 in the geodesic convexity, but its computational complexity was so far open. The general position number was defined in the geodesic convexity and proved $\NP$-hard in 2018. We extend these parameters to any graph convexity and prove that the iteration number is $\NP$-hard in the $P_3$ convexity. We use this result to prove that the iteration time is also $\NP$-hard in the geodesic convexity even in graphs with diameter two, a long standing open question. These results are also important since they are the last two missing $\NP$-hardness results regarding the ten most studied graph convexity parameters in the geodesic and $P_3$ convexities. We also prove that the general position number of the monophonic convexity is $W[1]$-hard (parameterized by the size of the solution) and $n^{1-\varepsilon}$-inapproximable in polynomial time for any $\varepsilon>0$ unless $\P=\NP$, even in graphs with diameter two. Finally, we also obtain FPT results on the general position number in the $P_3$ convexity and we prove that it is $W[1]$-hard (parameterized by the size of the solution).
相關內容
We consider the approximation of weakly T-coercive operators. The main property to ensure the convergence thereof is the regularity of the approximation (in the vocabulary of discrete approximation schemes). In a previous work the existence of discrete operators $T_n$ which converge to $T$ in a discrete norm was shown to be sufficient to obtain regularity. Although this framework proved usefull for many applications for some instances the former assumption is too strong. Thus in the present article we report a weaker criterium for which the discrete operators $T_n$ only have to converge point-wise, but in addition a weak T-coercivity condition has to be satisfied on the discrete level. We apply the new framework to prove the convergence of certain $H^1$-conforming finite element discretizations of the damped time-harmonic Galbrun's equation, which is used to model the oscillations of stars. A main ingredient in the latter analysis is the uniformly stable invertibility of the divergence operator on certain spaces, which is related to the topic of divergence free elements for the Stokes equation.
A simple graph on $n$ vertices may contain a lot of maximum cliques. But how many can it potentially contain? We will define prime and composite graphs, and we will show that if $n \ge 15$, then the grpahs with the maximum number of maximum cliques have to be composite. Moreover, we will show an edge bound from which we will prove that if any factor of a composite graph has $\omega(G_i) \ge 5$, then it cannot have the maximum number of maximum cliques. Using this we will show that the graph that contains $3^{\lfloor n/3 \rfloor}c$ maximum cliques has the most number of maximum cliques on $n$ vertices, where $c\in\{1,\frac{4}{3},2\}$, depending on $n \text{ mod } 3$.
In this paper, we study the method to reconstruct dynamical systems from data without time labels. Data without time labels appear in many applications, such as molecular dynamics, single-cell RNA sequencing etc. Reconstruction of dynamical system from time sequence data has been studied extensively. However, these methods do not apply if time labels are unknown. Without time labels, sequence data becomes distribution data. Based on this observation, we propose to treat the data as samples from a probability distribution and try to reconstruct the underlying dynamical system by minimizing the distribution loss, sliced Wasserstein distance more specifically. Extensive experiment results demonstrate the effectiveness of the proposed method.
The continuous-time Markov chain (CTMC) is the mathematical workhorse of evolutionary biology. Learning CTMC model parameters using modern, gradient-based methods requires the derivative of the matrix exponential evaluated at the CTMC's infinitesimal generator (rate) matrix. Motivated by the derivative's extreme computational complexity as a function of state space cardinality, recent work demonstrates the surprising effectiveness of a naive, first-order approximation for a host of problems in computational biology. In response to this empirical success, we obtain rigorous deterministic and probabilistic bounds for the error accrued by the naive approximation and establish a "blessing of dimensionality" result that is universal for a large class of rate matrices with random entries. Finally, we apply the first-order approximation within surrogate-trajectory Hamiltonian Monte Carlo for the analysis of the early spread of SARS-CoV-2 across 44 geographic regions that comprise a state space of unprecedented dimensionality for unstructured (flexible) CTMC models within evolutionary biology.
In this paper we argue that topic plays a fundamental role in conversations, and that the concept is needed in addition to that of genre to define interactions. In particular, the concepts of genre and topic need to be separated and orthogonally defined. This would enable modular, reliable and controllable flexible-domain dialogue systems.
In this article we shall discuss the theory of geodesics in information geometry, and an application in astrophysics. We will study how gradient flows in information geometry describe geodesics, explore the related mechanics by introducing a constraint, and apply our theory to Gaussian model and black hole thermodynamics. Thus, we demonstrate how deformation of gradient flows leads to more general Randers-Finsler metrics, describe Hamiltonian mechanics that derive from a constraint, and prove duality via canonical transformation. We also verified our theories for a deformation of the Gaussian model, and described dynamical evolution of flat metrics for Kerr and Reissner-Nordstr\"om black holes.
This paper explores an iterative coupling approach to solve linear thermo-poroelasticity problems, with its application as a high-fidelity discretization utilizing finite elements during the training of projection-based reduced order models. One of the main challenges in addressing coupled multi-physics problems is the complexity and computational expenses involved. In this study, we introduce a decoupled iterative solution approach, integrated with reduced order modeling, aimed at augmenting the efficiency of the computational algorithm. The iterative coupling technique we employ builds upon the established fixed-stress splitting scheme that has been extensively investigated for Biot's poroelasticity. By leveraging solutions derived from this coupled iterative scheme, the reduced order model employs an additional Galerkin projection onto a reduced basis space formed by a small number of modes obtained through proper orthogonal decomposition. The effectiveness of the proposed algorithm is demonstrated through numerical experiments, showcasing its computational prowess.
In this work we make us of Livens principle (sometimes also referred to as Hamilton-Pontryagin principle) in order to obtain a novel structure-preserving integrator for mechanical systems. In contrast to the canonical Hamiltonian equations of motion, the Euler-Lagrange equations pertaining to Livens principle circumvent the need to invert the mass matrix. This is an essential advantage with respect to singular mass matrices, which can yield severe difficulties for the modelling and simulation of multibody systems. Moreover, Livens principle unifies both Lagrangian and Hamiltonian viewpoints on mechanics. Additionally, the present framework avoids the need to set up the system's Hamiltonian. The novel scheme algorithmically conserves a general energy function and aims at the preservation of momentum maps corresponding to symmetries of the system. We present an extension to mechanical systems subject to holonomic constraints. The performance of the newly devised method is studied in representative examples.
Robust inferential methods based on divergences measures have shown an appealing trade-off between efficiency and robustness in many different statistical models. In this paper, minimum density power divergence estimators (MDPDEs) for the scale and shape parameters of the log-logistic distribution are considered. The log-logistic is a versatile distribution modeling lifetime data which is commonly adopted in survival analysis and reliability engineering studies when the hazard rate is initially increasing but then it decreases after some point. Further, it is shown that the classical estimators based on maximum likelihood (MLE) are included as a particular case of the MDPDE family. Moreover, the corresponding influence function of the MDPDE is obtained, and its boundlessness is proved, thus leading to robust estimators. A simulation study is carried out to illustrate the slight loss in efficiency of MDPDE with respect to MLE and, at besides, the considerable gain in robustness.
The goal of explainable Artificial Intelligence (XAI) is to generate human-interpretable explanations, but there are no computationally precise theories of how humans interpret AI generated explanations. The lack of theory means that validation of XAI must be done empirically, on a case-by-case basis, which prevents systematic theory-building in XAI. We propose a psychological theory of how humans draw conclusions from saliency maps, the most common form of XAI explanation, which for the first time allows for precise prediction of explainee inference conditioned on explanation. Our theory posits that absent explanation humans expect the AI to make similar decisions to themselves, and that they interpret an explanation by comparison to the explanations they themselves would give. Comparison is formalized via Shepard's universal law of generalization in a similarity space, a classic theory from cognitive science. A pre-registered user study on AI image classifications with saliency map explanations demonstrate that our theory quantitatively matches participants' predictions of the AI.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191