Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
111
0
0.0
(
0
)
Added by
Tom\\'a\\v{s} Masa\\v{r}\\'ik
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
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).
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.
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be the minimum number of leaves in the representing tree. We construct a fixed-parameter tractable algorithm testing isomorphism of chordal graphs with bounded leafage. The key point is a fixed-parameter tractable algorithm finding the automorphism group of a colored order-3 hypergraph with bounded sizes of color classes of vertices.
A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph there exists a set of at most k edges whose deletion results in a Konig graph. While the vertex version of the problem (Konig vertex deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the Konig Edge Deletion problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph G and a maximum matching M and we want a k-sized Konig edge deletion set that is disjoint from M, is fixed-parameter-tractable.
In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O(k^6 ).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
