Parameterizing above or below guaranteed values

DOI10.1016/j.jcss.2008.08.004zbMath1155.68400OpenAlexW2008444606MaRDI QIDQ1004602

Somnath Sikdar, Meena Mahajan, Venkatesh Raman

Publication date: 11 March 2009

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.08.004

zbMATH Keywords

NP-optimization problemsfixed-parameter tractabilityparameterized complexityabove guarantee parameterizations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (45)

Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ Studies in Computational Aspects of Voting ⋮ On the kernelization of split graph problems ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\) ⋮ Note on maximal bisection above tight lower bound ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Unnamed Item ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Detours in directed graphs ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Greed is good for deterministic scale-free networks ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Betweenness parameterized above tight lower bound ⋮ Going Far from Degeneracy ⋮ Note on Max Lin-2 above average ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ Ranking and Drawing in Subexponential Time ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Unnamed Item ⋮ Parameterized Traveling Salesman Problem: Beating the Average ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Unnamed Item ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Recognizing \(k\)-clique extendible orderings ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds ⋮ Acyclic Digraphs ⋮ Parameterizations of test cover with bounded test sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Optimization, approximation, and complexity classes
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Profile minimization problem for matrices and graphs
• On fixed-parameter tractability and approximability of NP optimization problems
• Approximating minimum feedback sets and multicuts in directed graphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parametrized complexity theory.
• Recognizing Berge graphs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• The Linear Arrangement Problem Parameterized Above Guaranteed Value
• Parameterizing MAX SNP Problems Above Guaranteed Values
• Fixed-Parameter Complexity of Minimum Profile Problems
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Parameterized Approximability
• Parameterized Approximation Problems
• Wheel-Free Deletion Is W[2-Hard]
• Obtaining a Planar Graph by Vertex Deletion
• Fixed-Parameter Algorithms for Kemeny Scores
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Chordal Deletion Is Fixed-Parameter Tractable
• On interval graphs and matrice profiles
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• On Syntactic versus Computational Views of Approximability
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Approximation algorithms for NP-complete problems on planar graphs
• New Upper Bounds for Maximum Satisfiability
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• On the advantage over a random assignment

This page was built for publication: Parameterizing above or below guaranteed values