In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of $\mathbb{R}^{N}$ such that for each $v \in V$ the ball $B(v, 1)$ intersects V on at least $\delta|V|$ points, then for every $\varepsilon\gt0$, the points of V can be covered with $f(\delta, \varepsilon)$ balls $B(v, 1+\varepsilon)$ with $v \in V$. DNL also applies to other metric spaces and to abstract set systems, where elements are compared pairwise with respect to (near) disjointness. In its strongest form, DNL provides an $\varepsilon$-clustering with size exponential in $\varepsilon^{-1}$, which amounts to a Regularity Lemma with 0/1 densities of some trigraph. Trigraphs are graphs with additional red edges. They are natural instances of partial concept classes, introduced by Alon, Hanneke, Holzman and Moran [FOCS 2021]. This paper is mainly a combinatorial study of the generalization of VapnikCervonenkis dimension to partial concept classes. The main point is to show how trigraphs can sometimes explain the success of random sampling even though the VC-dimension of the underlying graph is unbounded. All the results presented here are effective in the sense of computation: they primarily rely on uniform sampling with the same success rate as in classical VC-dimension theory. Among some applications of DNL, we show that $\left(\frac{3 t-8}{3 t-5}+\varepsilon\right) \cdot n$-regular $K_{t}$-free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree $n / 3-n^{1-\varepsilon}$ have bounded chromatic number (this does not hold with $n / 3-n^{1-o(1)}$). For tournaments, DNL implies that the domination number is bounded in terms of the fractional chromatic number. Also, $(1 / 2-\varepsilon)$-majority digraphs have bounded domination, independently of the number of voters.

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth “chunks”. This approach was however previously limited to circuits with a “layered” structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions: Fractionally linear-communication MPC in the correlated randomness model. We provide an N -party protocol for computing an n -input, m -output \(\mathbb {F}\) -arithmetic circuit with s internal gates (over any basis of binary gates) with communication complexity \((\frac{2}{3}s + n + m)\cdot N\cdot \log |\mathbb {F}|\) , which can be improved to \(((1+\epsilon )\cdot \frac{2}{5}s+n+m)\cdot N\cdot \log |\mathbb {F}|\) (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than \(s\cdot N\cdot \log |\mathbb {F}|\) bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold. Sublinear-Communication MPC. Assuming the existence of N -party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure N -party computation for all \(\log ^{1+o(1)}\) -depth (resp. \((\log \log )^{1+o(1)}\) -depth) circuits. Previously, this result was limited to \((\mathcal {O}(\log ))\) -depth (resp. \((\mathcal {O}(\log \log ))\) -depth) circuits, or to circuits with a specific structure ( e.g. layered). The \(\boldsymbol{{N\atopwithdelims ()1}}\) -OT complexity of MPC. We introduce the “ \(N\atopwithdelims ()1\) -OT complexity of MPC ” of a function f , denoted \(C_N(f)\) , as the number of oracle calls required to securely compute f in the \(N\atopwithdelims ()1\) -OT hybrid model. We establish the following upper bound: for every \(N\ge 2\) , \(C_N(f) \le (1+g(N))\cdot \frac{2 |f|}{5}\) , where g ( N ) is an explicit vanishing function. We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for M AXIMUM C LIQUE on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics ’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2 Õ( n 2/3 ) for M AXIMUM C LIQUE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for M AX C LIQUE on disk and unit ball graphs. M AX C LIQUE on unit ball graphs is equivalent to finding, given a collection of points in R 3 , a maximum subset of points with diameter at most some fixed value. In stark contrast, M AXIMUM C LIQUE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2 n 1−ɛ , unless the Exponential Time Hypothesis fails.

We propose a polynomial-time algorithm which takes as input a finite set of points of R^3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii, in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball graphs and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails.

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

Given a family $\mathcal{F}$ of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of $\mathcal{F}$. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition.