Parameterizing above Guaranteed Values: MaxSat and MaxCut

Mahajan, Meena ; Raman, Venkatesh (1999) Parameterizing above Guaranteed Values: MaxSat and MaxCut Journal of Algorithms, 31 (2). pp. 335-354. ISSN 0196-6774

[img] PDF

Official URL:

Related URL:


In this paper we investigate the parameterized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. LetGbe an arbitrary graph havingnvertices andmedges, and letfbe an arbitrary CNF formula withmclauses onnvariables. We improve Cai and Chen'sO(22ckcm) time algorithm for determining if at leastkclauses of ac-CNF formulafcan be satisfied; our algorithm runs inO(|f| + k2φk) time for arbitrary formulae and inO(cm + ckφk) time forc-CNF formulae, where φ is the golden ratio. We also give an algorithm for finding a cut of size at leastk; our algorithm runs inO(m + n + k4k) time. We then argue that the standard parameterization of these problems is unsuitable, because nontrivial situations arise only for large parameter values (k ≥ ⌈m/2⌉), in which range the fixed-parameter tractable algorithms are infeasible. A more meaningful question in the parameterized setting is to ask whether ⌈m/2⌉ + kclauses can be satisfied, or ⌈m/2⌉ + kedges can be placed in a cut. We show that these problems remain fixed-parameter tractable even under this parameterization. Furthermore, for up to logarithmic values of the parameter, our algorithms for these versions also run in polynomial time.

Item Type:Article
Source:Copyright of this article belongs to Elsevier B.V.
ID Code:127974
Deposited On:14 Oct 2022 11:32
Last Modified:14 Oct 2022 11:32

Repository Staff Only: item control page