Parameterizing above Guaranteed Values: MaxSat and MaxCut

Balasubramanian, 1998, An improved fixed parameter algorithm for vertex cover, Inform. Process. Lett., 65, 163, 10.1016/S0020-0190(97)00213-5 Cai, 1997, On fixed-parameter tractability and approximation of NP optimization problems, J. Comput. System Sci., 54, 465, 10.1006/jcss.1997.1490 Cai, 1997, On the amount of nondeterminism and the power of verifying, SIAM J. Comput., 26, 733, 10.1137/S0097539793258295 Cai, 1995, On input read modes of alternating turing machines, Theoret. Comput. Sci., 148, 33, 10.1016/0304-3975(94)00253-F Cai, 1997, A linear time algorithm for computing the intersection of all odd cycles in a graph, Discrete Appl. Math., 73, 27, 10.1016/S0166-218X(96)00074-1 Downey, 1995, Fixed parameter tractability and completeness I: Basic theory, SIAM J. Comput., 24, 873, 10.1137/S0097539792228228 Downey, 1995, Fixed Parameter tractibility and completeness II: Completeness for W[1], Theoret. Comput. Sci., 141, 109, 10.1016/0304-3975(94)00097-3 R. G. Downey, M. R. Fellows, Parameterized complexity R. G. Downey, M. R. Fellows, V. Raman, The Complexity of Irredundant Sets Parameterized by Size, IMSc-TR-97/06/24, Institute of Mathematical Sciences, 1997 Edwards, 1973, Some extremal properties of bipartite subgraphs, Canad. J. Math., 25, 475, 10.4153/CJM-1973-048-x Edwards, 1975, An improved lower bound for the number of edges in a largest bipartite subgraph M. R. Fellows Garey, 1979 Haglin, 1991, Approximation and intractability results for the maximum cut problem and its variants, IEE Trans. Comput., 40, 110, 10.1109/12.67327 Kohli, 1984, The minimum satisfiability problem, SIAM J. Discrete Math., 7, 275, 10.1137/S0895480191220836 Lieberherr, 1981, Complexity of partial satisfaction, J. Assoc. Comput. Mach., 28, 411, 10.1145/322248.322260 Marathe, 1996, On approximation algorithms for the minimum satisfiability problem, Inform. Process. Lett., 58, 23, 10.1016/0020-0190(96)00031-2 Nagamochi, 1992, A linear time algorithm for finding a sparsekk, Algorithmica, 7, 583, 10.1007/BF01758778 Nagamochi, 1992, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM J. Discrete Math., 5, 54, 10.1137/0405004 Papadimitriou, 1996, On limited nondeterminism and the complexity of the V-C dimension, J. Comput. System Sci., 53, 161, 10.1006/jcss.1996.0058 Poljak, 1982, A polynomial algorithm for constructing a large bipartite subgraph with an application to a satisfiability problem, Canad. J. Math., 34, 519, 10.4153/CJM-1982-036-8 Raman, 1998, A simplified NP-complete MAXSAT problem, Inform. Process. Lett., 65, 1, 10.1016/S0020-0190(97)00223-8 Sahni, 1976, P-complete approximation problems, J. Assoc. Comput. Mach., 23, 555, 10.1145/321958.321975 Stoer, 1997, A simple Min Cut algorithm, Journal of the ACM, 44, 585, 10.1145/263867.263872 Yannakakis, 1994, On the approximation of maximum satisfiability, J. Algorithms, 17, 475, 10.1006/jagm.1994.1045