We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w: V(G) to mathbb{Q}_{geq 0}$, the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices $
X$ such that $G-X$ is a split graph. It is easy to show that a graph is a split graph if and only it it does not contain a $4$-cycle, $5$-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy $5$-approximation algorithm. On the other hand, for every $delta >0$, SVD does not admit a $(2-delta)$-approximation algorithm, unless P=NP or the Unique Games Conjecture fails. For every $epsilon >0$, Lokshtanov, Misra, Panolan, Philip, and Saurabh recently gave a randomized $(2+epsilon)$-approximation algorithm for SVD. In this work we give an extremely simple deterministic $(2+epsilon)$-approximation algorithm for SVD.
This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-wei
ghted graph $G=(V,E)$, which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex $v$ in the cover, the number of $v$s incident edges covered by the copy is up to a given capacity of $v$. We extend Bhattacharya et al.s work [SODA15 and ICALP15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with $O(log n / epsilon)$ amortized update time, where $n$ is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a nonuniform and unsplittable demand, and (2) the more general capacitated set cover problem.
We present a massively parallel algorithm, with near-linear memory per machine, that computes a $(2+varepsilon)$-approximation of minimum-weight vertex cover in $O(loglog d)$ rounds, where $d$ is the average degree of the input graph. Our result fi
lls the key remaining gap in the state-of-the-art MPC algorithms for vertex cover and matching problems; two classic optimization problems, which are duals of each other. Concretely, a recent line of work---by Czumaj et al. [STOC18], Ghaffari et al. [PODC18], Assadi et al. [SODA19], and Gamlath et al. [PODC19]---provides $O(loglog n)$ time algorithms for $(1+varepsilon)$-approximate maximum weight matching as well as for $(2+varepsilon)$-approximate minimum cardinality vertex cover. However, the latter algorithm does not work for the general weighted case of vertex cover, for which the best known algorithm remained at $O(log n)$ time complexity.
We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The objective is to maximise $omega$ subject to $Ax le 1$, $Cx ge omega 1$, and $x ge 0$ for nonnegative matrices $A$ and $C$. The approximation ratio o
f our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$-Edge-Connected and $p$-Vertex-Connected VC problem (where $p geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not
admit a polynomial kernel unless $NP subseteq coNP/poly$, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. We obtain an $O(2^{O(pk)}n^{O(1)})$-time algorithm for the $p$-Edge-Connected VC and an $O(2^{O(k^2)}n^{O(1)})$-time algorithm for the $p$-Vertex-Connected VC. Finally, we describe a $2(p+1)$-approximation algorithm for the $p$-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning $p$-vertex/edge-connected subgraph of a $p$-vertex/edge-connected graph obtained independently by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).