Parametrized complexity theory.
From MaRDI portal
Publication:2488567
zbMath1143.68016MaRDI QIDQ2488567
Publication date: 24 May 2006
Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items
Complexity and monotonicity results for domination games ⋮ Structural tractability of counting of solutions to conjunctive queries ⋮ Structural decompositions for problems with global constraints ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Win-win kernelization for degree sequence completion problems ⋮ Hull number: \(P_5\)-free graphs and reduction rules ⋮ A parameterized study of maximum generalized pattern matching problems ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Tractability-preserving transformations of global cost functions ⋮ The label cut problem with respect to path length and label frequency ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ On the hardness of bribery variants in voting with CP-nets ⋮ Rural postman parameterized by the number of components of required edges ⋮ On the parameterised complexity of string morphism problems ⋮ Algorithms for the workflow satisfiability problem engineered for counting constraints ⋮ \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ Kernelization using structural parameters on sparse graph classes ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Courcelle's theorem for triangulations ⋮ Constraining the number of positive responses in adaptive, non-adaptive, and two-stage group testing ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Relativization makes contradictions harder for resolution ⋮ Shuffled languages -- representation and recognition ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Approximation algorithms for orienting mixed graphs ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Two-layer planarization parameterized by feedback edge set ⋮ The complexity of the stamp folding problem ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game ⋮ Parameterized complexity of \(k\)-Chinese postman problem ⋮ Parameterized maximum path coloring ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Parameterized complexity of MaxSat above average ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Revisiting the complexity of and/or graph solution ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Aspects of a multivariate complexity analysis for rectangle tiling ⋮ Improved bounds for spanning trees with many leaves ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ On making directed graphs transitive ⋮ Parameterized complexity of generalized domination problems ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Mod/Resc parsimony inference: theory and application ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ Minimum common string partition revisited ⋮ Parameterized Eulerian strong component arc deletion problem on tournaments ⋮ Local search: is brute-force avoidable? ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Graph-based data clustering with overlaps ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ On the directed full degree spanning tree problem ⋮ Lower bounds on kernelization ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Subexponential parameterized algorithms ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Patterns with bounded treewidth ⋮ Complexity of splits reconstruction for low-degree trees ⋮ Approximation algorithms for intersection graphs ⋮ Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Minimizing Rosenthal potential in multicast games ⋮ On the parameterized complexity of non-monotonic logics ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ Augmenting graphs to minimize the diameter ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ On finding optimal polytrees ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Parameterizations of test cover with bounded test sizes ⋮ Backdoors to q-Horn ⋮ Parameterized algorithms for finding square roots ⋮ Approximation schemes for the generalized extensible bin packing problem ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ On notions of regularity for data languages ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Parameterized pursuit-evasion games ⋮ Separator-based data reduction for signed graph balancing ⋮ Interval scheduling and colorful independent sets ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Exact algorithms for computing the tree edit distance between unordered trees ⋮ Meta-kernelization with structural parameters ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ On the hardness of labeled correlation clustering problem: a parameterized complexity view ⋮ Directed elimination games ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Algorithms solving the matching cut problem ⋮ The complexity of degree anonymization by vertex addition ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Directed NLC-width ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Contracting planar graphs to contractions of triangulations ⋮ Algorithms and complexity results for persuasive argumentation ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Bandwidth on AT-free graphs ⋮ Searching the \(k\)-change neighborhood for TSP is W[1-hard] ⋮ Parameterized complexity of control problems in Maximin election ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ Note on Max Lin-2 above average ⋮ Spanners in sparse graphs ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ Implicit branching and parameterized partial cover problems ⋮ The minimum feasible tileset problem ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ On the parameterized complexity of the edge monitoring problem ⋮ Campaign management under approval-driven voting rules ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ On the path-width of integer linear programming ⋮ From imperative to rule-based graph programs ⋮ A linear kernel for planar red-blue dominating set ⋮ The parameterized complexity of the shared center problem ⋮ Incremental problems in the parameterized complexity setting ⋮ The complexity of finding effectors ⋮ Graph editing problems with extended regularity constraints ⋮ List H-coloring a graph by removing few vertices ⋮ On the parameterized complexity of reconfiguration problems ⋮ On parameterized independent feedback vertex set ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ On the fixed-parameter tractability of parameterized model-checking problems ⋮ Parameterizing by the number of numbers ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Treewidth computations. I: Upper bounds ⋮ Parameterized graph cleaning problems ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ On the positive-negative partial set cover problem ⋮ The parameterized complexity of probability amplification ⋮ Cluster editing with locally bounded modifications ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Average parameterization and partial kernelization for computing medians ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Boolean-width of graphs ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ A kernelization algorithm for \(d\)-hitting set ⋮ Causal graphs and structurally restricted planning ⋮ Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ A note on width-parameterized SAT: an exact machine-model characterization ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Complexity of secure sets ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ An optimal algorithm for global optimization and adaptive covering ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ On the parameterized complexity of associative and commutative unification ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Editing to a planar graph of given degrees ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ The complexity of nonrepetitive coloring ⋮ Parameterizing above or below guaranteed values ⋮ The minimum spanning strong subdigraph problem is fixed parameter tractable ⋮ A more effective linear kernelization for cluster editing ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ On the treewidth of dynamic graphs ⋮ Red-blue covering problems and the consecutive ones property ⋮ An improved kernel size for rotation distance in binary trees ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Kernel Bounds for Path and Cycle Problems ⋮ Parameterized Maximum Path Coloring ⋮ Naive entropy of dynamical systems ⋮ The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability ⋮ Fast learning of relational dependency networks ⋮ Are there any nicely structured preference profiles nearby? ⋮ Computing equality-free and repetitive string factorisations ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Finding disjoint dense clubs in a social network ⋮ On the kernelization of split graph problems ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Complexity results for rainbow matchings ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ The relative clique-width of a graph ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ From causes for database queries to repairs and model-based diagnosis and back ⋮ Parameterized and exact algorithms for class domination coloring ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Parameterized complexity of completeness reasoning for conjunctive queries ⋮ Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Regularizing conjunctive features for classification ⋮ The complexity of degree anonymization by graph contractions ⋮ Packing arc-disjoint cycles in tournaments ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ The parameterized space complexity of embedding along a path ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ On compiling structured CNFs to OBDDs ⋮ Discrete multi-module capacitated lot-sizing problems with multiple items ⋮ On the Parameterized Complexity of Associative and Commutative Unification ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ Parameterized edge Hamiltonicity ⋮ Metric Dimension of Bounded Width Graphs ⋮ A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time ⋮ Finding Consensus Strings with Small Length Difference Between Input and Solution Strings ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints ⋮ Algorithms Solving the Matching Cut Problem ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ A Dichotomy Result for Ramsey Quantifiers ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Privacy in Elections: k-Anonymizing Preference Orders ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Knapsack problems: a parameterized point of view ⋮ The complexity of binary matrix completion under diameter constraints ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Tractable cases of the extended global cardinality constraint ⋮ A multistage view on 2-satisfiability ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Constrained hitting set problem with intervals ⋮ The effect of homogeneity on the computational complexity of combinatorial data anonymization ⋮ Radiation hybrid map construction problem parameterized ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Parameterized domination in circle graphs ⋮ Contracting graphs to paths and trees ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Digraph width measures in parameterized algorithmics ⋮ Imbalance is fixed parameter tractable ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Parameterized algorithms for load coloring problem ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ Searching for better fill-in ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ The price of query rewriting in ontology-based data access ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ The parameterized complexity of maximality and minimality problems ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Parameterized Complexity of CTL ⋮ Most frugal explanations in Bayesian networks ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ On tree width, bramble size, and expansion ⋮ Strong Backdoors for Default Logic ⋮ Faster Computation of Path-Width ⋮ Some Hard Families of Parameterized Counting Problems ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth ⋮ Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ Parameterized complexity of the maximum independent set problem and the speed of hereditary properties ⋮ On the Path Separability of Planar Graphs ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Parameterized model checking of rendezvous systems ⋮ A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition ⋮ Computational complexity of distance edge labeling ⋮ Document spanners: from expressive power to decision problems ⋮ Reconfiguration on nowhere dense graph classes ⋮ Two edge modification problems without polynomial kernels ⋮ The complexity of probabilistic lobbying ⋮ Note on maximal bisection above tight lower bound ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Parameterized complexity of superstring problems ⋮ Change-making problems revisited: a parameterized point of view ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Spanners of bounded degree graphs ⋮ Subexponential algorithms for partial cover problems ⋮ A kernel of order \(2k-c\log k\) for vertex cover ⋮ Automata for the verification of monadic second-order graph properties ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Parameterized complexity of team formation in social networks ⋮ Parameterized complexity of theory of mind reasoning in dynamic epistemic logic ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Towards a dichotomy for the possible winner problem in elections based on scoring rules ⋮ Betweenness parameterized above tight lower bound ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Approximate inference in Bayesian networks: parameterized complexity results ⋮ Multi-attribute proportional representation ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Pattern-guided \(k\)-anonymity ⋮ The parameterized complexity of the rainbow subgraph problem ⋮ Finding supported paths in heterogeneous networks ⋮ Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey ⋮ The complexity of dominating set in geometric intersection graphs ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ The complexity of routing with collision avoidance ⋮ Enumerating models of DNF faster: breaking the dependency on the formula size ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ The complexity landscape of decompositional parameters for ILP ⋮ The critical node detection problem in networks: a survey ⋮ Min-max cover of a graph with a small number of parts ⋮ On the complexity of finding and counting solution-free sets of integers ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Parameterized complexity of asynchronous border minimization ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Augmenting tractable fragments of abstract argumentation ⋮ On the evaluation of election outcomes under uncertainty ⋮ Practical access to dynamic programming on tree decompositions ⋮ On the approximate compressibility of connected vertex cover ⋮ The complexity of finding small separators in temporal graphs ⋮ The treewidth of proofs ⋮ On the parameterized complexity of consensus clustering ⋮ Complexity analysis via approach spaces ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Parameterized counting of partially injective homomorphisms ⋮ A parameterized perspective on protecting elections ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ A polynomial kernel for trivially perfect editing ⋮ Factoring a band matrix over a semiring ⋮ The complexity of homomorphism factorization ⋮ On the threshold of intractability ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ The Reeb graph edit distance is universal ⋮ Optimal tree decompositions revisited: a simpler linear-time FPT algorithm ⋮ The complexity of finding temporal separators under waiting time constraints ⋮ Structurally parameterized \(d\)-scattered set ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Graph operations characterizing rank-width ⋮ The parameterized complexity of the induced matching problem ⋮ Parameterized computational complexity of control problems in voting systems ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ On problems without polynomial kernels ⋮ A polynomial kernel for diamond-free editing ⋮ Parameterized learnability of juntas ⋮ A parameterized view on matroid optimization problems ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Minimum leaf out-branching and related problems ⋮ Exact multi-covering problems with geometric sets ⋮ Vertex fusion under distance constraints ⋮ Parameterized complexity of candidate control in elections and related digraph problems ⋮ An extension of the bivariate chromatic polynomial ⋮ On the shape of decomposable trees ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Some aspects of the database resilience ⋮ Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ Counting maximal antichains and independent sets ⋮ A logical approach to multicut problems ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Parameterized complexity of the induced subgraph problem in directed graphs ⋮ On the parameterized complexity of \(d\)-dimensional point set pattern matching ⋮ Bounded fixed-parameter tractability and reducibility ⋮ Finding all leftmost separators of size \(\le k\) ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Parameterized complexity of reconfiguration of atoms ⋮ A note on the gap between rank and border rank ⋮ Parameterized complexity classes beyond para-NP ⋮ Narrow sieves for parameterized paths and packings ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Paradigms for parameterized enumeration ⋮ Component order connectivity in directed graphs ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Reoptimization of parameterized problems ⋮ Complexity of edge monitoring on some graph classes ⋮ Sparse obstructions for minor-covering parameters ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Stable marriage with groups of similar agents ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ On the universal steganography of optimal rate ⋮ Parameterized dynamic cluster editing ⋮ An improvement of Reed's treewidth approximation ⋮ On the parameterized complexity of the synthesis of Boolean nets with restricted place environments ⋮ Constrained synchronization and commutativity ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem ⋮ Constant thresholds can make target set selection tractable ⋮ On the complexity of the identifiable subgraph problem ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ On explaining integer vectors by few homogeneous segments ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Colored hypergraph isomorphism is fixed parameter tractable ⋮ Algorithms for propositional model counting ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ A fixed-parameter perspective on \#BIS ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Probabilistic sentence satisfiability: an approach to PSAT ⋮ Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ Stability for maximal independent sets ⋮ Consensus strings with small maximum distance and small distance sum ⋮ On width measures and topological problems on semi-complete digraphs ⋮ A multiparametric view on answer set programming ⋮ On some matching problems under the color-spanning model ⋮ Backdoors to planning ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Evaluating Datalog via tree automata and cycluits ⋮ The parameterized complexity of the minimum shared edges problem ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ Colored cut games ⋮ Structural parameterizations of Tracking Paths problem ⋮ New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions ⋮ A polynomial kernel for bipartite permutation vertex deletion ⋮ CNF satisfiability in a subspace and related problems ⋮ Dynamic kernels for hitting sets and set packing ⋮ On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times ⋮ The complexity of finding harmless individuals in social networks ⋮ Eternal vertex cover on bipartite graphs ⋮ Fixed-parameter complexity and approximability of norm maximization ⋮ On structural parameterizations for the 2-club problem ⋮ Backdoors to tractable answer set programming ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ On sparsification for computing treewidth ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Red-black planning: a new systematic approach to partial delete relaxation ⋮ The complexity of quantum circuit mapping with fixed parameters ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ Combinatorial voter control in elections ⋮ Parameterized analysis of paging and list update algorithms ⋮ Using patterns to form homogeneous teams ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ On the complexity of finding a largest common subtree of bounded degree ⋮ A characterisation of clique-width through nested partitions ⋮ Approximability and parameterized complexity of multicover by \(c\)-intervals ⋮ Clique-width and edge contraction ⋮ Faster parameterized algorithms for deletion to split graphs ⋮ Counting triangulations and other crossing-free structures via onion layers ⋮ A complete parameterized complexity analysis of bounded planning ⋮ Editing to a graph of given degrees ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter ⋮ Finding fixed point free elements and small bases in permutation groups ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Tandem Duplications, Segmental Duplications and Deletions, and Their Applications ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ A Retrospective on (Meta) Kernelization ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ An Improvement of Reed’s Treewidth Approximation ⋮ On the Complexity of Intersecting Regular, Context-Free, and Tree Languages ⋮ Competitive Diffusion on Weighted Graphs ⋮ Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ On Compiling CNFs into Structured Deterministic DNNFs ⋮ Harary polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Complexity Classes under Logical Reductions ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ On Compiling Structured CNFs to OBDDs ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Editing to a Planar Graph of Given Degrees ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Computing Equality-Free String Factorisations ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Unnamed Item ⋮ Unique Covering Problems with Geometric Sets ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Unnamed Item ⋮ Computing Hitting Set Kernels By AC^0-Circuits ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Bounded Treewidth and Space-Efficient Linear Algebra ⋮ Algorithms for Propositional Model Counting ⋮ Improved Algorithms for Bicluster Editing ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ A Purely Democratic Characterization of W[1] ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs ⋮ Parameterized Derandomization ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ Fixed-Parameter Algorithms for Kemeny Scores ⋮ Minimum Leaf Out-Branching Problems ⋮ Unnamed Item ⋮ Parameterized Computational Complexity of Dodgson and Young Elections ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multicut Is FPT ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fractals for Kernelization Lower Bounds ⋮ Many-one reductions and the category of multivalued functions ⋮ Unnamed Item ⋮ How Bad is the Freedom to Flood-It? ⋮ Backdoor Sets for CSP. ⋮ Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Finding Disjoint Dense Clubs in an Undirected Graph ⋮ On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Computing $k$-Atomicity in Polynomial Time ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Practical Access to Dynamic Programming on Tree Decompositions ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Monadic Second Order Logic on Graphs with Local Cardinality Constraints ⋮ Parameterized Complexity of the Arc-Preserving Subsequence Problem ⋮ Drawing Graphs on Few Circles and Few Spheres ⋮ Bidimensionality and Kernels ⋮ The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Planar Capacitated Dominating Set Is W[1-Hard] ⋮ On Finding Directed Trees with Many Leaves ⋮ Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ On the Directed Degree-Preserving Spanning Tree Problem ⋮ Digraphs of Bounded Width ⋮ Backdoors into Two Occurrences ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ Parameterized complexity of perfectly matched sets ⋮ Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs ⋮ On data reduction for dynamic vector bin packing ⋮ Perfect forests in graphs and their extensions ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ On the complexity of coloring ‐graphs ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Parameterised counting in logspace ⋮ Equitable scheduling on a single machine ⋮ Gehrlein stable committee with multi-modal preferences ⋮ Faster Property Testers in a Variation of the Bounded Degree Model ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Disentangling the computational complexity of network untangling ⋮ Complexity of minimum-size arc-inconsistency explanations ⋮ CSP beyond tractable constraint languages ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Foundations of graph path query languages. Course notes for the reasoning web summer school 2021 ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Parameterized complexity of propositional inclusion and independence logic ⋮ Unnamed Item ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Extremal Uniquely Resolvable Multisets ⋮ Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ A Most General Edge Elimination Polynomial ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Hitting Selected (Odd) Cycles ⋮ Parameterized (Approximate) Defective Coloring ⋮ A Practical Approach for the FIFO Stack-Up Problem ⋮ Unnamed Item ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Explicit small heights in infinite non-abelian extensions ⋮ On the complexity of existential positive queries ⋮ Robustness among multiwinner voting rules ⋮ A Practical Approach to Courcelle's Theorem ⋮ Partially Polynomial Kernels for Set Cover and Test Cover ⋮ Slightly Superexponential Parameterized Problems ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Default logic and bounded treewidth ⋮ On the parameterized complexity of approximate counting ⋮ Probabilistic Logic Learning from Haplotype Data ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Parameterized certificate dispersal and its variants ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ The Parameterized Complexity of Graph Cyclability ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ Covering Graphs with Few Complete Bipartite Subgraphs ⋮ Faster Existential FO Model Checking on Posets ⋮ The Complexity of Decomposing Modal and First-Order Theories ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Obtaining a proportional allocation by deleting items ⋮ Maximum cuts in edge-colored graphs ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Unnamed Item ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ On the Descriptive Complexity of Color Coding ⋮ Counting Answers to Existential Questions ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ The Dominating Set Problem in Geometric Intersection Graphs ⋮ On the Complexity of Bounded Context Switching. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Parameterized Graph Editing with Chosen Vertex Degrees ⋮ Parameterized Algorithms for Generalized Domination ⋮ On Computing the Maximum Parsimony Score of a Phylogenetic Network ⋮ Unnamed Item ⋮ Network-Based Vertex Dissolution ⋮ Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Calculation of Discrepancy Measures and Applications ⋮ A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction
