License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.10
URN: urn:nbn:de:0030-drops-120849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12084/
Go to the corresponding LIPIcs Volume Portal

Gottesbüren, Lars ; Hamann, Michael ; Schoch, Philipp ; Strasser, Ben ; Wagner, Dorothea ; Zühlsdorf, Sven

Engineering Exact Quasi-Threshold Editing

pdf-format:
LIPIcs-SEA-2020-10.pdf (1 MB)

Abstract

Quasi-threshold graphs are {C₄, P₄}-free graphs, i.e., they do not contain any cycle or path of four nodes as an induced subgraph. We study the {C₄, P₄}-free editing problem, which is the problem of finding a minimum number of edge insertions or deletions to transform an input graph into a quasi-threshold graph. This problem is NP-hard but fixed-parameter tractable (FPT) in the number of edits by using a branch-and-bound algorithm and admits a simple integer linear programming formulation (ILP). Both methods are also applicable to the general ℱ-free editing problem for any finite set of graphs ℱ. For the FPT algorithm, we introduce a fast heuristic for computing high-quality lower bounds and an improved branching strategy. For the ILP, we engineer several variants of row generation. We evaluate both methods for quasi-threshold editing on a large set of protein similarity graphs. For most instances, our optimizations speed up the FPT algorithm by one to three orders of magnitude. The running time of the ILP, that we solve using Gurobi, becomes only slightly faster. With all optimizations, the FPT algorithm is slightly faster than the ILP, even when listing all solutions. Additionally, we show that for almost all graphs, solutions of the previously proposed quasi-threshold editing heuristic QTM are close to optimal.

BibTeX - Entry

@InProceedings{gottesbren_et_al:LIPIcs:2020:12084,
  author =	{Lars Gottesb{\"u}ren and Michael Hamann and Philipp Schoch and Ben Strasser and Dorothea Wagner and Sven Z{\"u}hlsdorf},
  title =	{{Engineering Exact Quasi-Threshold Editing}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12084},
  URN =		{urn:nbn:de:0030-drops-120849},
  doi =		{10.4230/LIPIcs.SEA.2020.10},
  annote =	{Keywords: Edge Editing, Integer Linear Programming, FPT algorithm, Quasi-Threshold Editing}
}

Keywords: Edge Editing, Integer Linear Programming, FPT algorithm, Quasi-Threshold Editing
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: Implementation: https://github.com/kit-algo/fpt-editing

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI