اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the query complexity of estimating the distance to hereditary graph properties
308
0
0.0
(
0
)
نشر من قبل
Yoshiharu Kohayakawa
تاريخ النشر
2019
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a family of graphs $mathcal{F}$, we prove that the normalized edit distance of any given graph $Gamma$ to being induced $mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan Regularity Lemma and on a Removal Lemma for $mathcal{F}$.
قيم البحث
اقرأ أيضاً
We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $Pi$ and an integer parameter $k$, the general problem $
P(G,Pi,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $Pi$. This problem, $P(G,Pi,k)$ has been proved to be NP-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be W[1]-complete by Khot and Raman, if $Pi$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is W[1]-complete on general graphs when $Pi$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes. Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that: $P(G,Pi,k)$ is solvable in polynomial time when the graph $G$ is co-bipartite and $Pi$ is the property of being planar, bipartite or triangle-free (or vice-versa). $P(G,Pi,k)$ is FPT when the graph $G$ is planar, bipartite or triangle-free and $Pi$ is the property of being planar, bipartite or triangle-free, or graph $G$ is co-bipartite and $Pi$ is the property of being co-bipartite. $P(G,Pi,k)$ is W[1]-complete when the graph $G$ is $C_4$-free, $K_{1,4}$-free or a unit disk graph and $Pi$ is the property of being either planar or bipartite.
There has been substantial interest in estimating the value of a graph parameter, i.e., of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Gra
ph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity $q_z=q_z(epsilon)$ of an estimable parameter $z$ is the size of a random sample of a graph $G$ required to ensure that the value of $z(G)$ may be estimated within an error of $epsilon$ with probability at least 2/3. In this paper, for any fixed monotone graph property $mathcal{P}=mbox{Forb}(mathcal{F})$, we study the sample complexity of estimating a bounded graph parameter $z_{mathcal{P}}$ that, for an input graph $G$, counts the number of spanning subgraphs of $G$ that satisfy $mathcal{P}$. To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property $mathcal{P}$ may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of $mathcal{P}$. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.
Given a hereditary property of graphs $mathcal{H}$ and a $pin [0,1]$, the edit distance function ${rm ed}_{mathcal{H}}(p)$ is asymptotically the maximum proportion of edge-additions plus edge-deletions applied to a graph of edge density $p$ sufficien
t to ensure that the resulting graph satisfies $mathcal{H}$. The edit distance function is directly related to other well-studied quantities such as the speed function for $mathcal{H}$ and the $mathcal{H}$-chromatic number of a random graph. Let $mathcal{H}$ be the property of forbidding an ErdH{o}s-R{e}nyi random graph $Fsim mathbb{G}(n_0,p_0)$, and let $varphi$ represent the golden ratio. In this paper, we show that if $p_0in [1-1/varphi,1/varphi]$, then a.a.s. as $n_0toinfty$, begin{align*} {rm ed}_{mathcal{H}}(p) = (1+o(1)),frac{2log n_0}{n_0} cdotminleft{ frac{p}{-log(1-p_0)}, frac{1-p}{-log p_0} right}. end{align*} Moreover, this holds for $pin [1/3,2/3]$ for any $p_0in (0,1)$.
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alp
habet $mathcal{A} = {1,2,ldots, k}$ (textit{i.e.,} $h_iinmathcal{A}$ for all $iin{1,2,ldots, n}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the textit{codebreaker}) first submits a query sequence $Q_t = (q_1, q_2, ldots, q_n)$ with $q_iin mathcal{A}$ for all $i$, and second receives feedback $Delta(Q_t, H)$, where $Delta$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t = H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of ${1,2,ldots, n}$, we prove that $f(n, n)ge n - loglog n$ for all sufficiently large $n$. Second, we show that Knuths Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=Omega(nlog k)$.
Let $H$ be a graph and $tgeq sgeq 2$ be integers. We prove that if $G$ is an $n$-vertex graph with no copy of $H$ and no induced copy of $K_{s,t}$, then $lambda(G) = Oleft(n^{1-1/s}right)$ where $lambda(G)$ is the spectral radius of the adjacency mat
rix of $G$. Our results are motivated by results of Babai, Guiduli, and Nikiforov bounding the maximum spectral radius of a graph with no copy (not necessarily induced) of $K_{s,t}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
