We show that the \textsc{Maximum Weight Independent Set} problem (\textsc{MWIS}) can be solved in quasi-polynomial time on $H$-free graphs (graphs excluding a fixed graph $H$ as an induced subgraph) for every $H$ whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of \textsc{MWIS} in $\mathcal{F}$-free graphs for any finite set $\mathcal{F}$ of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer $t \geq 1$. Let $S_{t,t,t}$ be the graph created from three paths on $t$ edges by identifying one endpoint of each path into a single vertex. We show that, given a graph $G$, one can in polynomial time find either an induced $S_{t,t,t}$ in $G$, or a balanced separator consisting of $\Oh(\log |V(G)|)$ vertex neighborhoods in $G$, or an extended strip decomposition of $G$ (a decomposition almost as useful for recursion for \textsc{MWIS} as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of $G$. This is a strengthening of a result of Majewski et al.\ [ICALP~2022] which provided such an extended strip decomposition only after the deletion of $\Oh(\log |V(G)|)$ vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.
相關內容
We present a new algorithm for finding isolated zeros of a system of real-valued functions in a bounded interval in $\mathbb{R}^n$. It uses the Chebyshev proxy method combined with a mixture of subdivision, reduction methods, and elimination checks that leverage special properties of Chebyshev polynomials. We prove the method has R-quadratic convergence locally near simple zeros of the system. We also analyze the temporal complexity and the numerical stability of the algorithm and provide numerical evidence in dimensions up to three that the method is both fast and accurate on a wide range of problems. The algorithm should also work well in higher dimensions. Our tests show that the algorithm outperforms other standard methods on this problem of finding all real zeros in a bounded domain. Our Python implementation of the algorithm is publicly available.
For a metric $\mu$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[\mu]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)\mu(\gamma(x),\gamma(y))$ subject to $\gamma:V\rightarrow T,\ \gamma(t)=t\ (\forall t\in T)$, where the sum is taken over all unordered pairs in $V$. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics $\mu$ for which 0-Ext$[\mu]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and \v{Z}ivn\'{y} 2016) specialized to 0-Ext$[\mu]$. In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[\mu]$ of the minimum 0-extension problem, where $\mu$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[\mu]$ to $\overrightarrow{0}$-Ext$[\mu]$: If $\mu$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is NP-hard. We also show a partial converse: If $\mu$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[\mu]$, and establish a dichotomy for the case where $\mu$ is a directed metric of a star.
Given a complex high-dimensional distribution over $\{\pm 1\}^n$, what is the best way to increase the expected number of $+1$'s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been widely studied in social networks, biology, and computer science. In this paper, we consider influence maximization on the Ising model which is a prototypical example of undirected graphical models and has wide applications in many real-world problems. We establish a sharp computational phase transition for influence maximization on sparse Ising models under a bounded budget: In the high-temperature regime, we give a linear-time algorithm for finding a small subset of variables and their values which achieve nearly optimal influence; In the low-temperature regime, we show that the influence maximization problem cannot be solved in polynomial time under commonly-believed complexity assumption. The critical temperature coincides with the tree uniqueness/non-uniqueness threshold for Ising models which is also a critical point for other computational problems including approximate sampling and counting.
We propose a method for estimating a log-concave density on $\mathbb R^d$ from samples, under the assumption that there exists an orthogonal transformation that makes the components of the random vector independent. While log-concave density estimation is hard both computationally and statistically, the independent components assumption alleviates both issues, while still maintaining a large non-parametric class. We prove that under mild conditions, at most $\tilde{\mathcal{O}}(\epsilon^{-4})$ samples (suppressing constants and log factors) suffice for our proposed estimator to be within $\epsilon$ of the original density in squared Hellinger distance. On the computational front, while the usual log-concave maximum likelihood estimate can be obtained via a finite-dimensional convex program, it is slow to compute -- especially in higher dimensions. We demonstrate through numerical experiments that our estimator can be computed efficiently, making it more practical to use.
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov\'{a}sz--Schrijver SDP operator $\text{LS}_+$, with a particular focus on finding and characterizing the smallest graphs with a given $\text{LS}_+$-rank (the least number of iterations of the $\text{LS}_+$ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating $\text{LS}_+$-minimal graphs and study its properties. We also provide several new $\text{LS}_+$-minimal graphs, most notably the first known instances of $12$-vertex graphs with $\text{LS}_+$-rank $4$, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a $9$-vertex graph with $\text{LS}_+$-rank $3$ in 2006.
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov{\'a}sz--Schrijver SDP operator $\LS_+$, with a particular focus on a search for relatively small graphs with high $\LS_+$-rank (the least number of iterations of the $\LS_+$ operator on the fractional stable set polytope to compute the stable set polytope). We provide families of graphs whose $\LS_+$-rank is asymptotically a linear function of its number of vertices, which is the best possible up to improvements in the constant factor (previous best result in this direction, from 1999, yielded graphs whose $\LS_+$-rank only grew with the square root of the number of vertices).
Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. Compared to classical key exchange, it has two main advantages: (i) The key is unconditionally hidden to the eyes of any attacker, and (ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures. On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages using public-key encryption. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange. In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions. That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new construction of quantum public-key encryption (QPKE) whose security, much like its classical counterpart, only relies on authenticated classical channels.
We establish the unique ergodicity of the Markov chain generated by the stochastic theta method (STM) with $\theta \in [1/2, 1]$ for monotone SODEs, without growth restriction on the coefficients, driven by nondegenerate multiplicative noise. The main ingredient of the arguments lies in the construction of new Lyapunov functions, involving the coefficients, the stepsize, and $\theta$, and the irreducibility and the strong Feller property for the STM. We also generalize the arguments to the STM and its Galerkin-based full discretizations for a class of monotone SPDEs driven by infinite-dimensional nondegenerate multiplicative trace-class noise. Applying these results to the stochastic Allen--Cahn equation indicates that its drift-implicit Euler scheme is uniquely ergodic for any interface thickness, which gives an affirmative answer to a question proposed in (J. Cui, J. Hong, and L. Sun, Stochastic Process. Appl. (2021): 55--93). Numerical experiments verify our theoretical results.
For an input graph $G=(V, E)$ and a source vertex $s \in V$, the \emph{$\alpha$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$\alpha$-VSDO}) answers an $\alpha$-approximate distance from $s$ to $t$ in $G-x$ for any query $(x, t)$. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new \emph{nearly linear time} algorithm of constructing the $(1 + \epsilon)$-VSDO for any weighted directed graph of $n$ vertices and $m$ edges with integer weights in range $[1, W]$, and any positive constant $\epsilon \in (0, 1]$. More precisely, the presented oracle attains $\tilde{O}(m / \epsilon + n /\epsilon^2)$ construction time, $\tilde{O}(n/ \epsilon)$ size, and $\tilde{O}(1/\epsilon)$ query time for any polynomially-bounded $W$. To the best of our knowledge, this is the first non-trivial result for SSRP/VSDO beating the trivial $\tilde{O}(mn)$ computation time for directed graphs with polynomially-bounded edge weights. Such a result has been unknown so far even for the setting of $(1 + \epsilon)$-approximation. It also implies that the known barrier of $\Omega(m\sqrt{n})$ time for the exact SSRP by Chechik and Magen~[ICALP2020] does not apply to the case of approximation.
In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings $s^1,\dots,s^n$ of total length $L$ that is a dictionary, and a string $t$ of length $m$ that is texts. The first version of the problem is assembling $t$ from the dictionary. The second version is the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). In this case, $t$ is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring. These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with $O(m+\log m\sqrt{nL})$ running time. In the case of SSP, we present a quantum algorithm with running time $O(n^3 1.728^n +L +\sqrt{L}n^{1.5}+\sqrt{L}n\log^2L\log^2n)$.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191