Let $G$ be a multigraph with $n$ vertices and $e>4n$ edges, drawn in the plane such that any two parallel edges form a simple closed curve with at least one vertex in its interior and at least one vertex in its exterior. Pach and T\'oth (A Crossing Lemma for Multigraphs, SoCG 2018) extended the Crossing Lemma of Ajtai et al. (Crossing-free subgraphs, North-Holland Mathematics Studies, 1982) and Leighton (Complexity issues in VLSI, Foundations of computing series, 1983) by showing that if no two adjacent edges cross and every pair of nonadjacent edges cross at most once, then the number of edge crossings in $G$ is at least $\alpha e^3/n^2$, for a suitable constant $\alpha>0$. The situation turns out to be quite different if nonparallel edges are allowed to cross any number of times. It is proved that in this case the number of crossings in $G$ is at least $\alpha e^{2.5}/n^{1.5}$. The order of magnitude of this bound cannot be improved.
相關內容
We study online matching in the Euclidean $2$-dimesional plane with non-crossing constraint. The offline version was introduced by Atallah in 1985 and the online version was introduced and studied more recently by Bose et al. The input to the problem consists of a sequence of points, and upon arrival of a point an algorithm can match it with a previously unmatched point provided that line segments corresponding to the matched edges do not intersect. The decisions are irrevocable, and while an optimal offline solution always matches all the points, an online algorithm cannot match all the points in the worst case, unless it is given some side information, i.e., advice. We study two versions of this problem -- monomchromatic (MNM) and bichromatic (BNM). We show that advice complexity of solving BNM optimally on a circle (or, more generally, on inputs in a convex position) is tightly bounded by the logarithm of the $n^\text{th}$ Catalan number from above and below. This result corrects the previous claim of Bose et al. that the advice complexity is $\log(n!)$. At the heart of the result is a connection between non-crossing constraint in online inputs and $231$-avoiding property of permutations of $n$ elements We also show a lower bound of $n/3-1$ and an upper bound of $3n$ on the advice complexity for MNM on a plane. This gives an exponential improvement over the previously best known lower bound and an improvement in the constant of the leading term in the upper bound. In addition, we establish a lower bound of $\frac{\alpha}{2}\infdiv{\frac{2(1-\alpha)}{\alpha}}{1/4}n$ on the advice complexity for achieving competitive ratio $\alpha$ for MNM on a circle. Standard tools from advice complexity, such as partition trees and reductions from string guessing problem, do not seem to apply to MNM/BNM, so we have to design our lower bounds from first principles.
We study a variant of the classical $k$-median problem known as diversity-aware $k$-median (introduced by Thejaswi et al. 2021), where we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset.We investigate the fixed-parameter tractability of this problem and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters of the problem. Motivated by these results we present a fixed parameter approximation algorithm with approximation ratio $(1 + \frac{2}{e} +\epsilon)$, and argue that this ratio is essentially tight assuming the gap-exponential time hypothesis. We also present a simple, practical local-search algorithm that gives a bicriteria $(2k, 3+\epsilon)$ approximation with better running time bounds.
Unlike univariate extreme value theory, multivariate extreme value distributions cannot be specified through a finite-dimensional parameter family of distributions. Instead, the many facets of multivariate extremes are mirrored in the inherent dependence structure of component-wise maxima which must be dissociated from the limiting extreme behaviour of its marginal distribution functions before a probabilistic characterisation of an extreme value quality can be determined. Mechanisms applied to elicit extremal dependence typically rely on standardisation of the unknown marginal distribution functions from which pseudo-observations for either Pareto or Fr\'echet marginals result. The relative merits of both of these choices for transformation of marginals have been discussed in the literature, particularly in the context of domains of attraction of an extreme value distribution. This paper is set within this context of modelling penultimate dependence as it proposes a unifying class of estimators for the residual dependence index that eschews consideration of choice of marginals. In addition, a reduced bias variant of the new class of estimators is introduced and their asymptotic properties are developed. The pivotal role of the unifying marginal transform in effectively removing bias is borne by a comprehensive simulation study. The leading application in this paper comprises an analysis of asymptotic independence between rainfall occurrences originating from monsoon-related events at several locations in Ghana.
We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of the grid. A move consists of selecting an unselected 1 tile and then filling the next unfilled square in a chosen direction from that tile (similar to Tipover and Cross Purposes). We prove NP-completeness of deciding whether the target square can be filled, by a reduction from rectilinear planar monotone 3SAT.
We study the computational complexity of the popular board game backgammon. We show that deciding whether a player can win from a given board configuration is NP-Hard, PSPACE-Hard, and EXPTIME-Hard under different settings of known and unknown opponents' strategies and dice rolls. Our work answers an open question posed by Erik Demaine in 2001. In particular, for the real life setting where the opponent's strategy and dice rolls are unknown, we prove that determining whether a player can win is EXPTIME-Hard. Interestingly, it is not clear what complexity class strictly contains each problem we consider because backgammon games can theoretically continue indefinitely as a result of the capture rule.
Enumerating all connected induced subgraphs of a given order $k$ is a computationally difficult problem. Elbassioni has proposed an algorithm based on reverse search with a delay of $O(k\cdot min\{(n-k),k\Delta\}\cdot(k(\Delta+\log{k})+\log{n}))$, where $n$ is the number of vertices and $\Delta$ is the maximum degree of input graph \cite{6}. In this short note, we present an algorithm with an improved delay of $O(k\cdot min\{(n-k),k\Delta\}\cdot(k\log{\Delta}+\log{n}))$ by introducing a new neighborhood definition. This also improves upon the current best delay bound $O(k^2\Delta)$\cite{4} for this problem for large $k$.
It is known that the vertex connectivity of a planar graph can be computed in linear time. We extend this result to the class of locally maximal 1-plane graphs: graphs that have an embedding with at most one crossing per edge such that the endpoints of each pair of crossing edges induce the complete graph $K_4$
We consider a problem introduced by Feige, Gamarnik, Neeman, R\'acz and Tetali [2020], that of finding a large clique in a random graph $G\sim G(n,\frac{1}{2})$, where the graph $G$ is accessible by queries to entries of its adjacency matrix. The query model allows some limited adaptivity, with a constant number of rounds of queries, and $n^\delta$ queries in each round. With high probability, the maximum clique in $G$ is of size roughly $2\log n$, and the goal is to find cliques of size $\alpha\log n$, for $\alpha$ as large as possible. We prove that no two-rounds algorithm is likely to find a clique larger than $\frac{4}{3}\delta\log n$, which is a tight upper bound when $1\leq\delta\leq \frac{6}{5}$. For other ranges of parameters, namely, two-rounds with $\frac{6}{5}<\delta<2$, and three-rounds with $1\leq\delta<2$, we improve over the previously known upper bounds on $\alpha$, but our upper bounds are not tight. If early rounds are restricted to have fewer queries than the last round, then for some such restrictions we do prove tight upper bounds.
For a graph $G=(V,E)$, a subset $D$ of vertex set $V$, is a dominating set of $G$ if every vertex not in $D$ is adjacent to atleast one vertex of $D$. A dominating set $D$ of a graph $G$ with no isolated vertices is called a paired dominating set (PD-set), if $G[D]$, the subgraph induced by $D$ in $G$ has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem remains NP-complete even when $G$ belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the positive side, the problem is efficiently solvable for many graph classes including intervals graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graph. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time $2$-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (in Theor. Comput. Sci., $591 (2015): 99-105$ and Algorithmica, $ 82 (2020) :2809-2840$).
We study the minimum vertex cover problem in the following stochastic setting. Let $G$ be an arbitrary given graph, $p \in (0, 1]$ a parameter of the problem, and let $G_p$ be a random subgraph that includes each edge of $G$ independently with probability $p$. We are unaware of the realization $G_p$, but can learn if an edge $e$ exists in $G_p$ by querying it. The goal is to find an approximate minimum vertex cover (MVC) of $G_p$ by querying few edges of $G$ non-adaptively. This stochastic setting has been studied extensively for various problems such as minimum spanning trees, matroids, shortest paths, and matchings. To our knowledge, however, no non-trivial bound was known for MVC prior to our work. In this work, we present a: * $(2+\epsilon)$-approximation for general graphs which queries $O(\frac{1}{\epsilon^3 p})$ edges per vertex, and a * $1.367$-approximation for bipartite graphs which queries $poly(1/p)$ edges per vertex. Additionally, we show that at the expense of a triple-exponential dependence on $p^{-1}$ in the number of queries, the approximation ratio can be improved down to $(1+\epsilon)$ for bipartite graphs. Our techniques also lead to improved bounds for bipartite stochastic matching. We obtain a $0.731$-approximation with nearly-linear in $1/p$ per-vertex queries. This is the first result to break the prevalent $(2/3 \sim 0.66)$-approximation barrier in the $poly(1/p)$ query regime, improving algorithms of [Behnezhad et al; SODA'19] and [Assadi and Bernstein; SOSA'19].
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191