Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

DOI10.1007/978-3-662-53174-7_1MaRDI QIDQ2827798zbMATH OpenOpenAlexFDO

Authors Christian Komusiewicz, André Nichterlein, Rolf Niedermeier

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In graph modification problems, one is given a graph G and the goal is to apply a minimum number of modification operations (such as edge deletions) to G such that the resulting graph fulfills a certain property. For example, the Cluster Deletion problem asks to delete as few edges as possible such that the resulting graph is a disjoint union of cliques. Graph modification problems appear in numerous applications, including the analysis of biological and social networks. Typically, graph modification problems are NP-hard, making them natural candidates for parameterized complexity studies. We discuss several fruitful interactions between the development of fixed-parameter algorithms and the design of heuristics for graph modification problems, featuring quite different aspects of mutual benefits.

Recommendations

• A novel branching strategy for parameterized graph modification problems
• Algorithms and experiments for parameterized approaches to hard graph problems
• A survey of parameterized algorithms and the complexity of edge modification
• Fast dynamic graph algorithms for parameterized problems
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Parameterized algorithms for Graph Burning problem
• Approximation algorithms for multi-parameter graph optimization problems

Cites work

• A Graph-Theoretic Approach to a Communications Problem
• A clustering algorithm based on graph connectivity
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• A refined complexity analysis of degree anonymization in graphs
• Algorithms and Data Structures
• Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
• Clustering with partial information
• Editing simple graphs
• Faster parameterized algorithms using linear programming
• Finding large degree-anonymous subgraphs is hard
• Fixed-parameter algorithms for cluster vertex deletion
• Graph-based data clustering with overlaps
• Graph-modeled data clustering: Exact algorithms for clique generation
• Heuristic algorithms in computational molecular biology
• Incremental list coloring of graphs, parameterized by conservation
• Local search: is brute-force avoidable?
• On Editing Graphs into 2-Club Clusters
• On the parameterized complexity of consensus clustering
• On the parameterized complexity of dynamic problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Properties of vertex packing and independence system polyhedra
• The complexity of degree anonymization by graph contractions
• The complexity of degree anonymization by vertex addition
• Which problems have strongly exponential complexity?
• Win-win kernelization for degree sequence completion problems

Cited in

(4)

• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• Parameterized algorithms for Graph Burning problem
• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations

This page was built for publication: Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827798)