Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARAMETERIZED COMPLEXITY:
Reports tagged with Parameterized Complexity:
TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

#### On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>> TR97-006 | 31st January 1997 Marco Cesati, Miriam Di Ianni #### Parameterized Parallel Complexity Comments: 1 We consider the framework of Parameterized Complexity, and we investigate the issue of which problems do admit efficient fixed parameter parallel algorithms by introducing two different degrees of efficiently parallelizable parameterized problems, PNC and FPP. We sketch both some FPP-algorithms solving natural parameterized problems and ... more >>> TR00-080 | 24th July 2000 Marco Cesati #### Perfect Code is W[1]-complete We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted more >>> TR01-023 | 13th March 2001 Jochen Alber, Henning Fernau, Rolf Niedermeier #### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems Revisions: 1 A parameterized problem is called fixed parameter tractable if it admits a solving algorithm whose running time on input instance$(I,k)$is$f(k) \cdot |I|^\alpha$, where$f$is an arbitrary function depending only on~$k$. Typically,$f$is some exponential function, e.g.,$f(k)=c^k$for ... more >>> TR04-027 | 20th February 2004 Henning Fernau #### Parametric Duality: Kernel Sizes and Algorithmics We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize" parameterized algorithms. more >>> TR06-011 | 2nd January 2006 Yijia Chen, Martin Grohe #### An Isomorphism between Subexponential and Parameterized Complexity Theory We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories. more >>> TR06-072 | 25th February 2006 Henning Fernau #### Parameterized Algorithms for Hitting Set: the Weighted Case We are going to analyze simple search tree algorithms for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set. ... more >>> TR07-001 | 19th November 2006 Stefan S. Dantchev, Barnaby Martin, Stefan Szeider #### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution Revisions: 2 We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>> TR07-091 | 10th September 2007 Martin Grohe #### Logic, Graphs, and Algorithms Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>> TR07-106 | 10th September 2007 Yijia Chen, Martin Grohe, Magdalena Grüber #### On Parameterized Approximability Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability. The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems. more >>> TR07-137 | 6th November 2007 Yijia Chen, Jörg Flum, Moritz Müller #### Lower Bounds for Kernelizations Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>> TR08-063 | 21st April 2008 Müller Moritz #### Valiant-Vazirani Lemmata for Various Logics We show analogues of a theorem due to Valiant and Vazirani for intractable parameterized complexity classes such as W[P], W[SAT] and the classes of the W-hierarchy as well as those of the A-hierarchy. We do so by proving a general logical'' version of it which may be of independent interest ... more >>> TR08-083 | 10th June 2008 Yijia Chen, Jörg Flum #### A logic for PTIME and a parameterized halting problem In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>> TR09-131 | 2nd December 2009 Stephan Kreutzer, Anuj Dawar #### Parameterized Complexity of First-Order Logic Revisions: 2 We show that if$\mathcal C$is a class of graphs which is "nowhere dense" then first-order model-checking is fixed-parameter tractable on$\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ... more >>> TR09-147 | 30th December 2009 Stephan Kreutzer #### Algorithmic Meta-Theorems Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a structural component, that is they are results of the form: "every computational problem that can be formalised in a given logic L ... more >>> TR10-038 | 10th March 2010 Dieter van Melkebeek, Holger Dell #### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses Revisions: 1 Consider the following two-player communication process to decide a language$L$: The first player holds the entire input$x$but is polynomially bounded; the second player is computationally unbounded but does not know any part of$x$; their goal is to cooperatively decide whether$x$belongs to$L$at small ... more >>> TR10-059 | 8th April 2010 Olaf Beyersdorff, Nicola Galesi, Massimo Lauria #### Hardness of Parameterized Resolution Parameterized Resolution and, moreover, a general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that paper, Dantchev et al. show a complexity gap in tree-like Parameterized Resolution for propositional formulas arising from translations of first-order principles. We broadly investigate Parameterized Resolution obtaining the following ... more >>> TR10-198 | 13th December 2010 Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov #### Parameterized Bounded-Depth Frege is Not Optimal A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>> TR11-071 | 27th April 2011 Serge Gaspers, Stefan Szeider #### The Parameterized Complexity of Local Consistency Revisions: 1 We investigate the parameterized complexity of deciding whether a constraint network is$k$-consistent. We show that, parameterized by$k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size$d$and the maximum number$\ell$of constraints in which a variable occurs. ... more >>> TR11-072 | 1st May 2011 Danny Hermelin, Xi Wu #### Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization Revisions: 1 We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let$d \ge 2$be some constant and let$L_1, L_2 \subseteq \{0,1\}^* \times \N$be two parameterized problems where the unparameterized version of$L_1$is \NP-hard. ... more >>> TR13-162 | 1st October 2013 Janka Chlebíková, Morgan Chopin #### The Firefighter Problem: A Structural Analysis Revisions: 1 We consider the complexity of the firefighter problem where${b \geq 1}$firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree$b+3$for any fixed budget ... more >>> TR14-004 | 30th November 2013 Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty #### On$r$-Simple$k$-Path An$r$-simple$k$-path is a {path} in the graph of length$k$that passes through each vertex at most$r$times. The \simpath{r}{k} problem, given a graph$G$as input, asks whether there exists an$r$-simple$k$-path in$G$. We first show that this problem is NP-Complete. We then show ... more >>> TR14-075 | 16th May 2014 Holger Dell #### A simple proof that AND-compression of NP-complete problems is hard Revisions: 3 Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result. An AND-compression is ... more >>> TR14-096 | 29th July 2014 Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran #### Solving Linear Equations Parameterized by Hamming Weight Given a system of linear equations$Ax=b$over the binary field$\mathbb{F}_2$and an integer$t\ge 1$, we study the following three algorithmic problems: 1. Does$Ax=b$have a solution of weight at most$t$? 2. Does$Ax=b$have a solution of weight exactly$t$? 3. Does$Ax=b$have a ... more >>> TR14-116 | 6th September 2014 Rahul Mehta #### 2048 is (PSPACE) Hard, but Sometimes Easy We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result holds for a version of the problem where the player has oracle access to the computer player's moves. Specifically, we show that for an$n \times n$game board$G$, computing a more >>> TR14-134 | 10th October 2014 Martin Lück, Arne Meier, Irina Schindler #### Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies Revisions: 3 We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>> TR15-013 | 28th January 2015 Subhash Khot, Igor Shinkar #### On Hardness of Approximating the Parameterized Clique Problem In the$Gap-clique(k, \frac{k}{2})$problem, the input is an$n$-vertex graph$G$, and the goal is to decide whether$G$contains a clique of size$k$or contains no clique of size$\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the$Gap-clique(k, \frac{k}{2})$problem ... more >>> TR15-130 | 11th August 2015 Ronald de Haan #### An Overview of Non-Uniform Parameterized Complexity We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. ... more >>> TR16-157 | 13th October 2016 Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran #### Parameterized Complexity of Small Weight Automorphisms We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>> TR17-186 | 29th November 2017 Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi #### On the Parameterized Complexity of Approximating Dominating Set Revisions: 1 We study the parameterized complexity of approximating the$k$-Dominating Set (domset) problem where an integer$k$and a graph$G$on$n$vertices are given as input, and the goal is to find a dominating set of size at most$F(k) \cdot k$whenever the graph$G$has a dominating ... more >>> TR18-057 | 26th March 2018 Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi #### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH The$k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over$\mathbb F_2$, which can be stated as follows: given a generator matrix$\mathbf A$and an integer$k$, determine whether the code generated by$\mathbf A$has distance at most$k$. Here,$k$... more >>> TR19-115 | 4th September 2019 Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx #### Parameterized Intractability of Even Set and Shortest Vector Problem The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over$\mathbb{F}_2\$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

TR20-086 | 5th June 2020
Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

#### A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

more >>>

ISSN 1433-8092 | Imprint