In the $\mathcal{F}$-Minor-Free Deletion problem one is given an undirected graph $G$, an integer $k$, and the task is to determine whether there exists a vertex set $S$ of size at most $k$, so that $G-S$ contains no graph from the finite family $\mathcal{F}$ as a minor. It is known that whenever $\mathcal{F}$ contains at least one planar graph, then $\mathcal{F}$-Minor-Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size $k^{\mathcal{O}(1)}$ [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most $k$ vertices from a graph to make it outerplanar. This is a special case of $\mathcal{F}$-Minor-Free Deletion for the family $\mathcal{F} = \{K_4, K_{2,3}\}$. The class of outerplanar graphs is arguably the simplest class of graphs for which no explicit kernelization size bounds are known. By exploiting the combinatorial properties of outerplanar graphs we present elementary reduction rules decreasing the size of a graph. This yields a constructive kernel with $\mathcal{O}(k^4)$ vertices and edges. As a corollary, we derive that any minor-minimal obstruction to having an outerplanar deletion set of size $k$ has $\mathcal{O}(k^4)$ vertices and edges.
相關內容
The number-theoretic codes are a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts' codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$.
We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing $\sum_S\det({\bf A}_{S,S})^p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar. (2) $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})\det({\bf C}_{S,S})$ is NP-hard to approximate within a factor of $2^{O(|I|^{1-\epsilon})}$ or $2^{O(n^{1/\epsilon})}$ for any $\epsilon>0$, where $|I|$ is the input size and $n$ is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater. (3) There exists a $k^{O(k)}n^{O(1)}$-time algorithm for computing $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})$, where $k$ is the maximum rank of $\bf A$ and $\bf B$ or the treewidth of the graph formed by nonzero entries of $\bf A$ and $\bf B$. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix $\bf A$ of treewidth $w$: (4) We can compute a $2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time. (5) We can find a $2^{\sqrt n}$-approximation to unconstrained MAP inference in $w^{O(w\sqrt n)}n^{O(1)}$ time.
Given a simple graph $G$ and an integer $k$, the goal of $k$-Clique problem is to decide if $G$ contains a complete subgraph of size $k$. We say an algorithm approximates $k$-Clique within a factor $g(k)$ if it can find a clique of size at least $k / g(k)$ when $G$ is guaranteed to have a $k$-clique. Recently, it was shown that approximating $k$-Clique within a constant factor is W[1]-hard [Lin21]. We study the approximation of $k$-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Lin21] already implies an $n^{\Omega(\sqrt[6]{\log k})}$-time lower bound under ETH. We improve this lower bound to $n^{\Omega(\log k)}$. Using the gap-amplification technique by expander graphs, we also prove that there is no $k^{o(1)}$ factor FPT-approximation algorithm for $k$-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no $n^{O(\frac{k}{\log k})}$ algorithm to approximate $k$-Clique within a constant factor, then PIH is true.
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $\ell_1$ and $\ell_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In the the bipartite permutation vertex deletion problem we ask for a given $n$-vertex graph, whether we can remove at most $k$ vertices to obtain a bipartite permutation graph. This problem is NP-complete but it does admit an FPT algorithm parameterized by $k$. In this paper we study the kernelization of this problem and show that it admits a polynomial kernel with $O(k^{99})$ vertices.
In the current work we are concerned with sequences of graphs having a grid geometry, with a uniform local structure in a bounded domain $\Omega\subset {\mathbb R}^d$, $d\ge 1$. When $\Omega=[0,1]$, such graphs include the standard Toeplitz graphs and, for $\Omega=[0,1]^d$, the considered class includes $d$-level Toeplitz graphs. In the general case, the underlying sequence of adjacency matrices has a canonical eigenvalue distribution, in the Weyl sense, and it has been shown in the theoretical part of this work that we can associate to it a symbol $\boldsymbol{\mathfrak{f}}$. The knowledge of the symbol and of its basic analytical features provides key information on the eigenvalue structure in terms of localization, spectral gap, clustering, and global distribution. In the present paper, many different applications are discussed and various numerical examples are presented in order to underline the practical use of the developed theory. Tests and applications are mainly obtained from the approximation of differential operators via numerical schemes such as Finite Differences (FDs), Finite Elements (FEs), and Isogeometric Analysis (IgA). Moreover, we show that more applications can be taken into account, since the results presented here can be applied as well to study the spectral properties of adjacency matrices and Laplacian operators of general large graphs and networks, whenever the involved matrices enjoy a uniform local structure.
We propose a new representation of $k$-partite, $k$-uniform hypergraphs (i.e. a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short) by a finite set $P$ of points in $\mathbb{R}^d$ and a parameter $\ell\leq d-1$. Each point in $P$ is covered by $k={d\choose\ell}$ many axis-aligned affine $\ell$-dimensional subspaces of $\mathbb{R}^d$, which we call $\ell$-subspaces for brevity. We interpret each point in $P$ as a hyperedge that contains each of the covering $\ell$-subspaces as a vertex. The class of $(d,\ell)$-hypergraphs is the class of $k$-hypergraphs that can be represented in this way, where $k={d\choose\ell}$. The resulting classes of hypergraphs are fairly rich: Every $k$-hypergraph is a $(k,k-1)$-hypergraph. On the other hand, $(d,\ell)$-hypergraphs form a proper subclass of the class of all $d\choose\ell$-hypergraphs for $\ell<d-1$. In this paper we give a natural structural characterization of $(d,\ell)$-hypergraphs based on vertex cuts. This characterization leads to a polynomial-time recognition algorithm that decides for a given $d\choose\ell$-hypergraph whether or not it is a $(d,\ell)$-hypergraph and that computes a representation if existing. We assume that the dimension $d$ is constant and that the partitioning of the vertex set is prescribed.
Given an undirected graph $G=(V,E)$, a vertex $v\in V$ is edge-vertex (ev) dominated by an edge $e\in E$ if $v$ is either incident to $e$ or incident to an adjacent edge of $e$. A set $S^{ev}\subseteq E$ is an edge-vertex dominating set (referred to as ev-dominating set) of $G$ if every vertex of $G$ is ev-dominated by at least one edge of $S^{ev}$. The minimum cardinality of an ev-dominating set is the ev-domination number. The edge-vertex dominating set problem is to find a minimum ev-domination number. In this paper we prove that the ev-dominating set problem is {\tt NP-hard} on unit disk graphs. We also prove that this problem admits a polynomial-time approximation scheme on unit disk graphs. Finally, we give a simple 5-factor linear-time approximation algorithm.
It is well known [Lov\'{a}sz, 1967] that up to isomorphism a graph $G$ is determined by the homomorphism counts $\hom(F, G)$, i.e., the number of homomorphisms from $F$ to $G$, where $F$ ranges over all graphs. Moreover, it suffices that $F$ ranges over the graphs with at most as many vertices as $G$. Thus in principle we can answer any query concerning $G$ with only accessing the $\hom(\cdot,G)$'s instead of $G$ itself. In this paper, we zoom in on those queries that can be answered using a constant number of $\hom(\cdot,G)$ for every graph $G$. We observe that if a query $\varphi$ is expressible as a Boolean combination of universal sentences in first-order logic, then whether a graph $G$ satisfies $\varphi$ can be determined by the vector \[\overrightarrow{\mathrm{hom}}_{F_1, \ldots, F_k}(G):= \big(\mathrm{hom}(F_1, G), \ldots, \mathrm{hom}(F_k, G)\big),\] where the graphs $F_1,\ldots,F_k$ only depend on $\varphi$. This leads to a query algorithm for $\varphi$ that is non-adaptive in the sense that those $F_i$ are independent of the input $G$. On the other hand, we prove that the existence of an isolated vertex, which is not definable by such a $\varphi$ but in first-order logic, cannot be determined by any $\overrightarrow{\mathrm{hom}}_{F_1, \ldots, F_k}(\cdot)$. These results provide a clear delineation of the power of non-adaptive query algorithms with access to a constant number of $\hom(\cdot, G)$'s. For adaptive query algorithms, i.e., algorithms that might access some $\hom(F_{i+1}, G)$ with $F_{i+1}$ depending on $\hom(F_1, G), \ldots, \hom(F_i, G)$, we show that three homomorphism counts $\hom(\cdot,G)$ are both sufficient and in general necessary to determine the graph $G$. In particular, by three adaptive queries we can answer any question on $G$. Moreover, adaptively accessing two $\hom(\cdot, G)$'s is already enough to detect an isolated vertex.
A well-known line of work (Barron, 1993; Breiman, 1993; Klusowski & Barron, 2018) provides bounds on the width $n$ of a ReLU two-layer neural network needed to approximate a function $f$ over the ball $\mathcal{B}_R(\mathbb{R}^d)$ up to error $\epsilon$, when the Fourier based quantity $C_f = \frac{1}{(2\pi)^{d/2}} \int_{\mathbb{R}^d} \|\xi\|^2 |\hat{f}(\xi)| \ d\xi$ is finite. More recently Ongie et al. (2019) used the Radon transform as a tool for analysis of infinite-width ReLU two-layer networks. In particular, they introduce the concept of Radon-based $\mathcal{R}$-norms and show that a function defined on $\mathbb{R}^d$ can be represented as an infinite-width two-layer neural network if and only if its $\mathcal{R}$-norm is finite. In this work, we extend the framework of Ongie et al. (2019) and define similar Radon-based semi-norms ($\mathcal{R}, \mathcal{U}$-norms) such that a function admits an infinite-width neural network representation on a bounded open set $\mathcal{U} \subseteq \mathbb{R}^d$ when its $\mathcal{R}, \mathcal{U}$-norm is finite. Building on this, we derive sparse (finite-width) neural network approximation bounds that refine those of Breiman (1993); Klusowski & Barron (2018). Finally, we show that infinite-width neural network representations on bounded open sets are not unique and study their structure, providing a functional view of mode connectivity.
Given a finite family $\mathcal{F}$ of graphs, we say that a graph $G$ is "$\mathcal{F}$-free" if $G$ does not contain any graph in $\mathcal{F}$ as a subgraph. A vertex-coloured graph $H$ is called "rainbow" if no two vertices of $H$ have the same colour. Given an integer $s$ and a finite family of graphs $\mathcal{F}$, let $\ell(s,\mathcal{F})$ denote the smallest integer such that any properly vertex-coloured $\mathcal{F}$-free graph $G$ having $\chi(G)\geq \ell(s,\mathcal{F})$ contains an induced rainbow path on $s$ vertices. Scott and Seymour showed that $\ell(s,K)$ exists for every complete graph $K$. A conjecture of N. R. Aravind states that $\ell(s,C_3)=s$. The upper bound on $\ell(s,C_3)$ that can be obtained using the methods of Scott and Seymour setting $K=C_3$ are, however, super-exponential. Gy\`arf\`as and S\`ark\"ozy showed that $\ell(s,\{C_3,C_4\})=\mathcal{O}\big((2s)^{2s}\big)$. We show that $\ell(s,K_{2,r})\leq (r-1)(s-1)s/2+s$ and therefore, $\ell(s,C_4)\leq\frac{s^2+s}{2}$. This significantly improves Gy\`arf\`as and S\`ark\"ozy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that $\ell(s,\{C_3,C_4,\ldots,C_{g-1}\})\leq s^{1+\frac{4}{g-4}}$, where $g\geq 5$. Moreover, in each case, our results imply the existence of at least $s!/2$ distinct induced rainbow paths on $s$ vertices. Along the way, we obtain some new results on an oriented variant of the Gy\`arf\`as-Sumner conjecture. Let $\mathcal{B}_r$ denote the orientations of $K_{2,r}$ in which one vertex has out-degree $r$. We show that every $\mathcal{B}_r$-free oriented graph having chromatic number at least $(r-1)(s-1)(s-2)+s$ and every bikernel-perfect oriented graph with girth $g\geq 5$ having chromatic number at least $2s^{1+\frac{4}{g-4}}$ contains every oriented tree on at most $s$ vertices as an induced subgraph.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191