Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRaising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
67
0
0.0
(
0
)
Added by
Geevarghese Philip
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph $G$ and $kinmathbb{N}$ as input, does $G$ have a vertex cover of size at most $(2LP-MM)+k$? Here $MM$ is the size of a maximum matching of $G$, $LP$ is the value of an optimum solution to the relaxed (standard) LP for Vertex Cover on $G$, and $k$ is the parameter. Since $(2LP-MM)geq{LP}geq{MM}$, this is a stricter parameterization than those---namely, above-$MM$, and above-$LP$---which have been studied so far. We prove that Vertex Cover is fixed-parameter tractable for this stricter parameter $k$: We derive an algorithm which solves Vertex Cover in time $O^{*}(3^{k})$, pushing the envelope further on the parameterized tractability of Vertex Cover.
rate research
Read More
We consider a CNF formula $F$ as a multiset of clauses: $F={c_1,..., c_m}$. The set of variables of $F$ will be denoted by $V(F)$. Let $B_F$ denote the bipartite graph with partite sets $V(F)$ and $F$ and with an edge between $v in V(F)$ and $c in F$ if $v in c$ or $bar{v} in c$. The matching number $ u(F)$ of $F$ is the size of a maximum matching in $B_F$. In our main result, we prove that the following parameterization of {sc MaxSat} (denoted by $( u(F)+k)$-textsc{SAT}) is fixed-parameter tractable: Given a formula $F$, decide whether we can satisfy at least $ u(F)+k$ clauses in $F$, where $k$ is the parameter. A formula $F$ is called variable-matched if $ u(F)=|V(F)|.$ Let $delta(F)=|F|-|V(F)|$ and $delta^*(F)=max_{Fsubseteq F} delta(F).$ Our main result implies fixed-parameter tractability of {sc MaxSat} parameterized by $delta(F)$ for variable-matched formulas $F$; this complements related results of Kullmann (2000) and Szeider (2004) for {sc MaxSat} parameterized by $delta^*(F)$. To obtain our main result, we reduce $( u(F)+k)$-textsc{SAT} into the following parameterization of the {sc Hitting Set} problem (denoted by $(m-k)$-{sc Hitting Set}): given a collection $cal C$ of $m$ subsets of a ground set $U$ of $n$ elements, decide whether there is $Xsubseteq U$ such that $Ccap X eq emptyset$ for each $Cin cal C$ and $|X|le m-k,$ where $k$ is the parameter. Gutin, Jones and Yeo (2011) proved that $(m-k)$-{sc Hitting Set} is fixed-parameter tractable by obtaining an exponential kernel for the problem. We obtain two algorithms for $(m-k)$-{sc Hitting Set}: a deterministic algorithm of runtime $O((2e)^{2k+O(log^2 k)} (m+n)^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(sqrt{k})} (m+n)^{O(1)})$. Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (2011).
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes ${mathsf{cycles, trees, forests, chordal, cactus, eventext{-}holetext{-}free, clawtext{-}free}}$, there are schedules that use $O(varepsilon^{-1})$ batches and incur only a $1+varepsilon$ multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in $O(varepsilon^{-1}log^* n)$ distributed time, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.
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 fills 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.
A common approach for designing scalable algorithms for massive data sets is to distribute the computation across, say $k$, machines and process the data using limited communication between them. A particularly appealing framework here is the simultaneous communication model whereby each machine constructs a small representative summary of its own data and one obtains an approximate/exact solution from the union of the representative summaries. If the representative summaries needed for a problem are small, then this results in a communication-efficient and round-optimal protocol. While many fundamental graph problems admit efficient solutions in this model, two prominent problems are notably absent from the list of successes, namely, the maximum matching problem and the minimum vertex cover problem. Indeed, it was shown recently that for both these problems, even achieving a polylog$(n)$ approximation requires essentially sending the entire input graph from each machine. The main insight of our work is that the intractability of matching and vertex cover in the simultaneous communication model is inherently connected to an adversarial partitioning of the underlying graph across machines. We show that when the underlying graph is randomly partitioned across machines, both these problems admit randomized composable coresets of size $widetilde{O}(n)$ that yield an $widetilde{O}(1)$-approximate solution. This results in an $widetilde{O}(1)$-approximation simultaneous protocol for these problems with $widetilde{O}(nk)$ total communication when the input is randomly partitioned across $k$ machines. We further prove the optimality of our results. Finally, by a standard application of composable coresets, our results also imply MapReduce algorithms with the same approximation guarantee in one or two rounds of communication
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
