** In an undirected graph, a matching cut is an edge cut which is also a matching. we refer MATCHING CUT to the problem of deciding if a given graph contain a matching cut or not. For the matching cut problem, the size of the edge cut also known as the number of crossing edges is a natural parameter. Gomes et al. in \cite{Gomes-Sau} showed that MATCHING CUT is FPT when parameterized by maximum size of the edge cut using a reduction on results provided by Marx et. al \cite{marx_treewidth_reduction}. However, they didn't provide an explicit bound on the running time as the treewidth reduction technique of \cite{marx_treewidth_reduction} relies on a MSOL formulation for matching cut and Courcelle's Theorem \cite{courcelle1990monadic} to show fixed parameter tractability. This motivated us to design an FPT algorithm for the MATCHING CUT where the dependence on the parameter is explicit. In this paper we present an FPT algorithm for matching cut problem for general graphs with running time $O(2^{O(k\log k)}n^{O(1)})$. This is the first FPT algorithm for the MATCHING CUT where the dependence on the matching cut size as a parameter is explicit and bounded. **

FPT：International Conference on Field-Programmable Technology。
Explanation：现场可编程技术国际会议。
Publisher：IEEE。
SIT： http://dblp.uni-trier.de/db/conf/fpt/

** In this paper, we develop and study approximately smooth basis constructions for isogeometric analysis over two-patch domains. One key element of isogeometric analysis is that it allows high order smoothness within one patch. However, for representing complex geometries, a multi-patch construction is needed. In this case, a $C^0$-smooth basis is easy to obtain, whereas $C^1$-smooth isogeometric functions require a special construction. Such spaces are of interest when solving numerically fourth-order PDE problems, such as the biharmonic equation and the Kirchhoff-Love plate or shell formulation, using an isogeometric Galerkin method. With the construction of so-called analysis-suitable $G^1$ (in short, AS-$G^1$) parametrizations, as introduced in (Collin, Sangalli, Takacs; CAGD, 2016), it is possible to construct $C^1$ isogeometric spaces which possess optimal approximation properties. These geometries need to satisfy certain constraints along the interfaces and additionally require that the regularity $r$ and degree $p$ of the underlying spline space satisfy $1 \leq r \leq p-2$. The problem is that most complex geometries are not AS-$G^1$ geometries. Therefore, we define basis functions for isogeometric spaces by enforcing approximate $C^1$ conditions following the basis construction from (Kapl, Sangalli, Takacs; CAGD, 2017). For this reason, the defined function spaces are not exactly $C^1$ but only approximately. We study the convergence behavior and define function spaces that converge optimally under $h$-refinement, by locally introducing functions of higher polynomial degree and lower regularity. The convergence rate is optimal in several numerical tests performed on domains with non-trivial interfaces. While an extension to more general multi-patch domains is possible, we restrict ourselves to the two-patch case and focus on the construction over a single interface. **

最优化
·

** Let $P$ be a set of $n$ points in $\mathbb{R}^2$. For a given positive integer $w<n$, our objective is to find a set $C \subset P$ of points, such that $CH(P\setminus C)$ has the smallest number of vertices and $C$ has at most $n-w$ points. We discuss the $O(wn^3)$ time dynamic programming algorithm for monotone decomposable functions (MDF) introduced for finding a class of optimal convex $w$-gons, with vertices chosen from $P$, and improve it to $O(n^3 \log w)$ time, which gives an improvement to the existing algorithm for MDFs if their input is a convex polygon. **

** Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching (if possible). We consider the competitiveness of online algorithms in both the adversarial order model (AOM) and the random order model (ROM). More specifically, we consider a bipartite stochastic graph $G = (U,V,E)$ where $U$ is the set of offline vertices, $V$ is the set of online vertices and $G$ has edge probabilities $(p_{e})_{e \in E}$ and edge weights $(w_{e})_{e \in E}$. Additionally, $G$ has probing constraints $(\scr{C}_{v})_{v \in V}$, where $\scr{C}_v$ indicates which sequences of edges adjacent to an online vertex $v$ can be probed. We assume that $U$ is known in advance, and that $\scr{C}_v$, together with the edge probabilities and weights adjacent to an online vertex are only revealed when the online vertex arrives. This model generalizes the various settings of the classical bipartite matching problem, and so our main contribution is in making progress towards understanding which classical results extend to the stochastic probing model. **

算法与数据结构
·

** We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and output a large matching of $G$. We prove that for an absolute constant $\epsilon_0 > 0$, one can find a $(2/3 + \epsilon_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3 + \Omega(1))$-approximation is achievable. **

** Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [ABSKS20] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $O(n^{3/2})$ (resp., $O(n^{7/5})$) to the weighted setting, where the additive error is $+2W$ (resp., $+4W$). This means that for every pair $u,v$, the additive stretch is at most $+2W_{u,v}$, where $W_{u,v}$ is the maximal edge weight on the shortest $u-v$ path. In addition, [ABSKS20] showed an algorithm yielding a $+8W_{max}$ spanner of size $O(n^{4/3})$, here $W_{max}$ is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $+(6+\varepsilon)W$ spanner for weighted graphs with size $O(n^{4/3})$ (for any constant $\varepsilon>0$), thus nearly matching the classical +6 spanner of size $O(n^{4/3})$ for unweighted graphs. Furthermore, we show a $+(2+\varepsilon)W$ subsetwise spanner of size $O(n\cdot\sqrt{|S|})$, improving the $+4W_{max}$ result of [ABSKS20] (that had the same size). We also show a simple randomized algorithm for a $+4W$ emulator of size $\tilde{O}(n^{4/3})$. In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $+\tilde{O}(\sqrt{n}\cdot W)$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [DHZ00] for unweighted graphs, we devise an efficient randomized algorithm producing a $+2W$ spanner for weighted graphs of size $\tilde{O}(n^{3/2})$ in $\tilde{O}(n^2)$ time. **