Parameterizing edge modification problems above lower bounds

DOI10.1007/s00224-016-9746-5zbMath1386.68075arXiv1512.04047OpenAlexW2578359728MaRDI QIDQ1635817

Vincent Froese, Christian Komusiewicz, René van Bevern

Publication date: 1 June 2018

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.04047

zbMATH Keywords

NP-hard problemcluster editingkernelizationfeedback arc setfixed-parameter algorithmgraph-based clusteringsubgraph packing

Mathematics Subject Classification ID

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

Related Items (6)

Combining clickstream analyses and graph-modeled data clustering for identifying common response processes ⋮ Parameterizing edge modification problems above lower bounds ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Parameterized algorithms for module map problems ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A \(2k\) kernel for the cluster editing problem
• Graph-based data clustering with overlaps
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Exact exponential algorithms.
• Kernels for feedback arc set in tournaments
• Complexity and parameterized algorithms for cograph editing
• Cluster editing with locally bounded modifications
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Isolation concepts for efficiently enumerating dense subgraphs
• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• A more effective linear kernelization for cluster editing
• Almost 2-SAT is fixed-parameter tractable
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterizing edge modification problems above lower bounds
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• A golden ratio parameterized algorithm for cluster editing
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Applying modular decomposition to parameterized cluster editing problems
• Incompressibility of \(H\)-free edge modification problems
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
• Exploring the Subexponential Complexity of Completion Problems
• On Generating Triangle-Free Graphs
• Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
• On Multiway Cut Parameterized above Lower Bounds
• Tight bounds for parameterized complexity of Cluster Editing
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Fast FAST
• Two Edge Modification Problems without Polynomial Kernels
• Edge-Deletion Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
• Faster Parameterized Algorithms Using Linear Programming
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Ranking Tournaments
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Parameterizing edge modification problems above lower bounds