A subset $S$ of vertices in a graph $G$ is a secure dominating set of $G$ if $S$ is a dominating set of $G$ and, for each vertex $u \not\in S$, there is a vertex $v \in S$ such that $uv$ is an edge and $(S \setminus \{v\}) \cup \{u\}$ is also a dominating set of $G$. The secure domination number of $G$, denoted by $\gamma_{s}(G)$, is the cardinality of a smallest secure dominating sets of $G$. In this paper, we prove that for any outerplanar graph with $n \geq 4$ vertices, $\gamma_{s}(G) \geq (n+4)/5$ and the bound is tight.
相關內容
Given some binary matrix $M$, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant $c > 0$ such that the algorithm terminates in $O(n^2)$ time with high probability and in expectation for random $n \times n$ binary matrices with i.i.d.\ Bernoulli $(p)$ entries $(m_{ij})_{ij=1}^n$ such that $\frac{c\log^2(n)}{n(\log\log(n))^2} \leq p \leq \frac{1}{2}$.
We consider a synchronous process of particles moving on the vertices of a graph $G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, $M$ particles are placed on a vertex of $G$. In subsequent time steps, all particles that are located on a vertex inhabited by at least two particles jump independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle; we call this (random) time step the dispersion time. In this work we study the case where $G$ is the complete graph on $n$ vertices and the number of particles is $M=n/2+\alpha n^{1/2} + o(n^{1/2})$, $\alpha\in \mathbb{R}$. This choice of $M$ corresponds to the critical window of the process, with respect to the dispersion time. We show that the dispersion time, if rescaled by $n^{-1/2}$, converges in $p$-th mean, as $n\rightarrow \infty$ and for any $p \in \mathbb{R}$, to a continuous and almost surely positive random variable $T_\alpha$. We find that $T_\alpha$ is the absorption time of a standard logistic branching process, thoroughly investigated by Lambert (2005), and we determine its expectation. In particular, in the middle of the critical window we show that $\mathbb{E}[T_0] = \pi^{3/2}/\sqrt{7}$, and furthermore we formulate explicit asymptotics when $|\alpha|$ gets large that quantify the transition into and out of the critical window. We also study the random variable counting the total number of jumps that are performed by the particles until the dispersion time is reached and prove that, if rescaled by $n\ln n$, it converges to $2/7$ in probability.
We develop a novel method to construct uniformly valid confidence bands for a nonparametric component $f_1$ in the sparse additive model $Y=f_1(X_1)+\ldots + f_p(X_p) + \varepsilon$ in a high-dimensional setting. Our method integrates sieve estimation into a high-dimensional Z-estimation framework, facilitating the construction of uniformly valid confidence bands for the target component $f_1$. To form these confidence bands, we employ a multiplier bootstrap procedure. Additionally, we provide rates for the uniform lasso estimation in high dimensions, which may be of independent interest. Through simulation studies, we demonstrate that our proposed method delivers reliable results in terms of estimation and coverage, even in small samples.
A U(1)-connection graph $G$ is a graph in which each oriented edge is endowed with a unit complex number, the latter being conjugated under orientation flip. We consider cycle-rooted spanning forests (CRSFs), a particular kind of spanning subgraphs of $G$ that have recently found computational applications as randomized spectral sparsifiers. In this context, CRSFs are drawn from a determinantal measure. Under a condition on the connection, Kassel and Kenyon gave an elegant algorithm, named CyclePopping, to sample from this distribution. The algorithm is an extension of the celebrated algorithm of Wilson that uses a loop-erased random walk to sample uniform spanning trees. In this paper, we give an alternative, elementary proof of correctness of CyclePopping for CRSF sampling; we fill the gaps of a proof sketch by Kassel, who was himself inspired by Marchal's proof of the correctness of Wilson's original algorithm. One benefit of the full proof \`a la Marchal is that we obtain a concise expression for the law of the number of steps to complete the sampling procedure, shedding light on practical situations where the algorithm is expected to run fast. Furthermore, we show how to extend the proof to more general distributions over CRSFs, which are not determinantal. The correctness of CyclePopping is known even in the non-determinantal case from the work of Kassel and Kenyon, so our merit is only to provide an alternate proof. One interest of this alternate proof is again to provide the distribution of the time complexity of the algorithm, in terms of a Poisson point process on the graph loops, or equivalently as a Poisson process on pyramids of cycles, a combinatorial notion introduced by Viennot. Finally, we strive to make the connections to loop measures and combinatorial structures as explicit as possible, to provide a reference for future extensions of the algorithm and its analysis.
We give a simple, greedy $O(n^{\omega+0.5})=O(n^{2.872})$-time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds whenever the size of the planted clique is $k\geq O(\sqrt{n} \log^2 n)$. In the model, the edges touching the vertices in the planted $k$-clique are drawn independently with probability $p=1/2$ while the edges not touching the planted clique are chosen by an adversary in response to the random choices. Our result shows that the computational threshold in the semirandom setting is within a $O(\log^2 n)$ factor of the information-theoretic one [Ste17] thus resolving an open question of Steinhardt. This threshold also essentially matches the conjectured computational threshold for the well-studied special case of fully random planted clique. All previous algorithms [CSV17, MMT20, BKS23] in this model are based on rather sophisticated rounding algorithms for entropy-constrained semidefinite programming relaxations and their sum-of-squares strengthenings and the best known guarantee is a $n^{O(1/\epsilon)}$-time algorithm to list-decode planted cliques of size $k \geq \tilde{O}(n^{1/2+\epsilon})$. In particular, the guarantee trivializes to quasi-polynomial time if the planted clique is of size $O(\sqrt{n} \operatorname{polylog} n)$. Our algorithm achieves an almost optimal guarantee with a surprisingly simple greedy algorithm. The prior state-of-the-art algorithmic result above is based on a reduction to certifying bounds on the size of unbalanced bicliques in random graphs -- closely related to certifying the restricted isometry property (RIP) of certain random matrices and known to be hard in the low-degree polynomial model. Our key idea is a new approach that relies on the truth of -- but not efficient certificates for -- RIP of a new class of matrices built from the input graphs.
Let $G$ be a graph with $n$ vertices and $m$ edges. One of several hierarchies towards the stability number of $G$ is the exact subgraph hierarchy (ESH). On the first level it computes the Lov\'{a}sz theta function $\vartheta(G)$ as semidefinite program (SDP) with a matrix variable of order $n+1$ and $n+m+1$ constraints. On the $k$-th level it adds all exact subgraph constraints (ESC) for subgraphs of order $k$ to the SDP. An ESC ensures that the submatrix of the matrix variable corresponding to the subgraph is in the correct polytope. By including only some ESCs into the SDP the ESH can be exploited computationally. In this paper we introduce a variant of the ESH that computes $\vartheta(G)$ through an SDP with a matrix variable of order $n$ and $m+1$ constraints. We show that it makes sense to include the ESCs into this SDP and introduce the compressed ESH (CESH) analogously to the ESH. Computationally the CESH seems favorable as the SDP is smaller. However, we prove that the bounds based on the ESH are always at least as good as those of the CESH. In computational experiments sometimes they are significantly better. We also introduce scaled ESCs (SESCs), which are a more natural way to include exactness constraints into the smaller SDP and we prove that including an SESC is equivalent to including an ESC for every subgraph.
Given a simple weighted directed graph $G = (V, E, \omega)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $\omega \equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022].
An $(m,n,R)$-de Bruijn covering array (dBCA) is a doubly periodic $M \times N$ array over an alphabet of size $q$ such that the set of all its $m \times n$ windows form a covering code with radius $R$. An upper bound of the smallest array area of an $(m,n,R)$-dBCA is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and $(m,n,R)$-dBCAs with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.
We present an $O(1)$-round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive a $O(\log n)$-round fully-scalable massively parallel algorithm for solving the exact longest increasing subsequence (LIS) problem. For a fully-scalable MPC regime, this result substantially improves the previously known algorithm of $O(\log^4 n)$-round complexity, and matches the best algorithm for computing the $(1+\epsilon)$-approximation of LIS.
A {\it pure significance test} (PST) tests a simple null hypothesis $H_f:Y\sim f$ {\it without specifying an alternative hypothesis} by rejecting $H_f$ for {\it small} values of $f(Y)$. When the sample space supports a proper uniform pmf $f_\mathrm{unif}$, the PST can be viewed as a classical likelihood ratio test for testing $H_f$ against this uniform alternative. Under this interpretation, standard test features such as power, Kullback-Leibler divergence, and expected $p$-value can be considered. This report focuses on PSTs for multinomial and binomial distributions, and for the related goodness-of-fit testing problems with the uniform alternative. The case of repeated observations cannot be reduced to the single observation case via sufficiency. The {\it ordered binomial distribution}, apparently new, arises in the course of this study.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191