Fixed-parameter tractability of satisfying beyond the number of variables

DOI10.1007/S00453-012-9697-4zbMATH Open1360.68502arXiv1212.0106OpenAlexW3099433168MaRDI QIDQ528862FDOQ528862

Yong-Cai Geng, Sumit K. Garg

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider a CNF formula $F$ as a multiset of clauses: $F=c_1,\mathrm{...},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 $vinV(F)$ and $cinF$ if $vinc$ or $$. 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)$- extsc{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 $delt{a}^{*}(F)=ma{x}_{F^{\prime }subseteqF}delta(F^{\prime }).$ 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 $delt{a}^{*}(F)$. To obtain our main result, we reduce $(u(F)+k)$- extsc{SAT} into the following parameterization of the {sc Hitting Set} problem (denoted by $(m-k)$-{sc Hitting Set}): given a collection $calC$ of $m$ subsets of a ground set $U$ of $n$ elements, decide whether there is $XsubseteqU$ such that $CcapXeqemptyset$ for each $CincalC$ and $|X|lem-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(lo{g}^{2}k)}(m+n{)}^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(sqrtk)}(m+n{)}^{O(1)})$. Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (2011).

Full work available at URL: https://arxiv.org/abs/1212.0106

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of facets resolved
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
• Parametrized complexity theory.
• Incompressibility through Colors and IDs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Color-coding
• Solving MAX-\(r\)-SAT above a tight lower bound
• Solving satisfiability in less than \(2^ n\) steps
• Faster algorithms for finding and counting subgraphs
• Kernel bounds for disjoint cycles and disjoint paths
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On subclasses of minimal unsatisfiable formulas
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems

Cited In (2)

• Partially Polynomial Kernels for Set Cover and Test Cover
• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment

This page was built for publication: Fixed-parameter tractability of satisfying beyond the number of variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528862)