The proper conflict-free chromatic number, $\chi_{pcf}(G)$, of a graph $G$ is the least $k$ such that $G$ has a proper $k$-coloring in which for each non-isolated vertex there is a color appearing exactly once among its neighbors. The proper odd chromatic number, $\chi_{o}(G)$, of $G$ is the least $k$ such that $G$ has a proper coloring in which for every non-isolated vertex there is a color appearing an odd number of times among its neighbors. We say that a graph class $\mathcal{G}$ is $\chi_{pcf}$-bounded ($\chi_{o}$-bounded) if there is a function $f$ such that $\chi_{pcf}(G) \leq f(\chi(G))$ ($\chi_{o}(G) \leq f(\chi(G))$) for every $G \in \mathcal{G}$. Caro et al. (2022) asked for classes that are linearly $\chi_{pcf}$-bounded ($\chi_{pcf}$-bounded), and as a starting point, they showed that every claw-free graph $G$ satisfies $\chi_{pcf}(G) \le 2\Delta(G)+1$, which implies $\chi_{pcf}(G) \le 4\chi(G)+1$. They also conjectured that any graph $G$ with $\Delta(G) \ge 3$ satisfies $\chi_{pcf}(G) \le \Delta(G)+1$. In this paper, we improve the bound for claw-free graphs to a nearly tight bound by showing that such a graph $G$ satisfies $\chi_{pcf}(G) \le \Delta(G)+6$, and even $\chi_{pcf}(G) \le \Delta(G)+4$ if it is a quasi-line graph. Moreover, we show that convex-round graphs and permutation graphs are linearly $\chi_{pcf}$-bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly $\chi_{pcf}$-bounded to deciding if the bipartite graphs in the class are $\chi_{pcf}$-bounded by an absolute constant. This lemma complements a theorem of Liu (2022) and motivates us to further study boundedness in bipartite graphs. So among other results, we show that convex bipartite graphs are not $\chi_{o}$-bounded, and a class of bipartite circle graphs that is linearly $\chi_{o}$-bounded but not $\chi_{pcf}$-bounded.
相關內容
The dichromatic number of a digraph is the minimum integer $k$ such that it admits a $k$-dicolouring, i.e. a partition of its vertices into $k$ acyclic subdigraphs. We say that a digraph $D$ is a super-orientation of an undirected graph $G$ if $G$ is the underlying graph of $D$. If $D$ does not contain any pair of symmetric arcs, we just say that $D$ is an orientation of $G$. In this work, we give both lower and upper bounds on the dichromatic number of super-orientations of chordal graphs. We also show a family of orientations of cographs for which the dichromatic number is equal to the clique number of the underlying graph.
The key result of this paper is to find all the joint distributions of random vectors whose sums $S=X_1+\ldots+X_d$ are minimal in convex order in the class of symmetric Bernoulli distributions. The minimal convex sums distributions are known to be strongly negatively dependent. Beyond their interest per se, these results enable us to explore negative dependence within the class of copulas. In fact, there are two classes of copulas that can be built from multivariate symmetric Bernoulli distributions: the extremal mixture copulas, and the FGM copulas. We study the extremal negative dependence structure of the copulas corresponding to symmetric Bernoulli vectors with minimal convex sums and we explicitly find a class of minimal dependence copulas. Our main results stem from the geometric and algebraic representations of multivariate symmetric Bernoulli distributions, which effectively encode several of their statistical properties.
We consider the problem of counting 4-cycles ($C_4$) in an undirected graph $G$ of $n$ vertices and $m$ edges (in bipartite graphs, 4-cycles are also often referred to as $\textit{butterflies}$). There have been a number of previous algorithms for this problem based on sorting the graph by degree and using randomized hash tables. These are appealing in theory due to compact storage and fast access on average. But, the performance of hash tables can degrade unpredictably and are also vulnerable to adversarial input. We develop a new simpler algorithm for counting $C_4$ requiring $O(m\bar\delta(G))$ time and $O(n)$ space, where $\bar \delta(G) \leq O(\sqrt{m})$ is the $\textit{average degeneracy}$ parameter introduced by Burkhardt, Faber \& Harris (2020). It has several practical improvements over previous algorithms; for example, it is fully deterministic, does not require any sorting of the input graph, and uses only addition and array access in its inner loops. To the best of our knowledge, all previous efficient algorithms for $C_4$ counting have required $\Omega(m)$ space in addition to storing the input graph. Our algorithm is very simple and easily adapted to count 4-cycles incident to each vertex and edge. Empirical tests demonstrate that our array-based approach is $4\times$ -- $7\times$ faster on average compared to popular hash table implementations.
The grounded Laplacian matrix $\LL_{-S}$ of a graph $\calG=(V,E)$ with $n=|V|$ nodes and $m=|E|$ edges is a $(n-s)\times (n-s)$ submatrix of its Laplacian matrix $\LL$, obtained from $\LL$ by deleting rows and columns corresponding to $s=|S| \ll n $ ground nodes forming set $S\subset V$. The smallest eigenvalue of $\LL_{-S}$ plays an important role in various practical scenarios, such as characterizing the convergence rate of leader-follower opinion dynamics, with a larger eigenvalue indicating faster convergence of opinion. In this paper, we study the problem of adding $k \ll n$ edges among all the nonexistent edges forming the candidate edge set $Q = (V\times V)\backslash E$, in order to maximize the smallest eigenvalue of the grounded Laplacian matrix. We show that the objective function of the combinatorial optimization problem is monotone but non-submodular. To solve the problem, we first simplify the problem by restricting the candidate edge set $Q$ to be $(S\times (V\backslash S))\backslash E$, and prove that it has the same optimal solution as the original problem, although the size of set $Q$ is reduced from $O(n^2)$ to $O(n)$. Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio $(1-e^{-\alpha\gamma})/\alpha$ and time complexity $O(kn^4)$, where $\gamma$ and $\alpha$ are, respectively, submodularity ratio and curvature, whose bounds are provided for some particular cases. The other is a fast greedy algorithm without approximation guarantee, which has a running time $\tilde{O}(km)$, where $\tilde{O}(\cdot)$ suppresses the ${\rm poly} (\log n)$ factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency.
Given an undirected graph $G$ and a multiset of $k$ terminal pairs $\mathcal{X}$, the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $G$ has $k$ pairwise internally vertex-disjoint paths and $k$ pairwise edge-disjoint paths, respectively, connecting every terminal pair in~$\mathcal{X}$. In this paper, we study the kernelization complexity of \VDP~and~\EDP~on subclasses of chordal graphs. For \VDP, we design a $4k$ vertex kernel on split graphs and an $\mathcal{O}(k^2)$ vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For \textsc{EDP}, we first prove that the problem is $\mathsf{NP}$-complete on complete graphs. Then, we design an $\mathcal{O}(k^{2.75})$ vertex kernel for \EDP~on split graphs, and improve it to a $7k+1$ vertex kernel on threshold graphs. Lastly, we provide an $\mathcal{O}(k^2)$ vertex kernel for \EDP~on block graphs and a $2k+1$ vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al.~[Theory Comput. Syst., 2015].
Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs. While we do not settle the computational complexity status of recognizing this property, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension $3$, we reduce the problem to $2$-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$.
The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, QSDP is in $\mathsf{QSZK}$ merely within the constant polarizing regime, similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the $\mathsf{SZK}$ containment for SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new $\mathsf{QSZK}$-complete problems improve $\mathsf{QSZK}$ containments for QSDP beyond the polarizing regime and establish a simple $\mathsf{QSZK}$-hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in $\mathsf{PP}$, while the same problem without error is in $\mathsf{NQP}$.
In this work we show that given a connectivity graph $G$ of a $[[n,k,d]]$ quantum code, there exists $\{K_i\}_i, K_i \subset G$, such that $\sum_i |K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, and the $K_i$'s are $\tilde{\Omega}( \sqrt{{k}/{n}})$-expander. If the codes are classical we show instead that the $K_i$'s are $\tilde{\Omega}\left({{k}/{n}}\right)$-expander. We also show converses to these bounds. In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions. Finally, we prove structural theorems for graphs with no "dense" subgraphs which might be of independent interest.
For a finite set $\cal F$ of polynomials over fixed finite prime field of size $p$ containing all polynomials $x^2 - x$ a Nullstellensatz proof of the unsolvability of the system $$ f = 0\ ,\ \mbox{ all } f \in {\cal F} $$ in the field is a linear combination $\sum_{f \in {\cal F}} \ h_f \cdot f$ that equals to $1$ in the ring of polynomails. The measure of complexity of such a proof is its degree: $\max_f deg(h_f f)$. We study the problem to establish degree lower bounds for some {\em extended} NS proof systems: these systems prove the unsolvability of $\cal F$ by proving the unsolvability of a bigger set ${\cal F}\cup {\cal E}$, where set $\cal E$ may use new variables $r$ and contains all polynomials $r^p - r$, and satisfies the following soundness condition: -- - Any $0,1$-assignment $\overline a$ to variables $\overline x$ can be appended by an assignment $\overline b$ to variables $\overline r$ such that for all $g \in {\cal E}$ it holds that $g(\overline a, \overline b) = 0$. We define a notion of pseudo-solutions of $\cal F$ and prove that the existence of pseudo-solutions with suitable parameters implies lower bounds for two extended NS proof systems ENS and UENS defined in Buss et al. (1996/97). Further we give a combinatorial example of $\cal F$ and candidate pseudo-solutions based on the pigeonhole principle.
We introduce $\pi$-test, a privacy-preserving algorithm for testing statistical independence between data distributed across multiple parties. Our algorithm relies on privately estimating the distance correlation between datasets, a quantitative measure of independence introduced in Sz\'ekely et al. [2007]. We establish both additive and multiplicative error bounds on the utility of our differentially private test, which we believe will find applications in a variety of distributed hypothesis testing settings involving sensitive data.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191