License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.46
URN: urn:nbn:de:0030-drops-185806
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18580/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Inamdar, Tanmay ;
Koana, Tomohiro
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Abstract
We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p and 0 ≤ α ≤ 1, the question is whether there is a set S ⊆ V of size k with a specified coverage function cov_α(S) at least p (or at most p for the minimization version). The coverage function cov_α(⋅) counts edges with exactly one endpoint in S with weight α and edges with both endpoints in S with weight 1 - α. α-FCGP generalizes a number of fundamental graph problems such as Densest k-Subgraph, Max k-Vertex Cover, and Max (k,n-k)-Cut.
A natural question in the study of α-FCGP is whether the algorithmic results known for its special cases, like Max k-Vertex Cover, could be extended to more general settings. One of the simple but powerful methods for obtaining parameterized approximation [Manurangsi, SOSA 2019] and subexponential algorithms [Fomin et al. IPL 2011] for Max k-Vertex Cover is based on the greedy vertex degree orderings. The main insight of our work is that the idea of greed vertex degree ordering could be used to design fixed-parameter approximation schemes (FPT-AS) for α > 0 and the subexponential-time algorithms for the problem on apex-minor free graphs for maximization with α > 1/3 and minimization with α < 1/3.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs.MFCS.2023.46,
author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Koana, Tomohiro},
title = {{FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {46:1--46:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18580},
URN = {urn:nbn:de:0030-drops-185806},
doi = {10.4230/LIPIcs.MFCS.2023.46},
annote = {Keywords: Partial Vertex Cover, Approximation Algorithms, Max Cut}
}
|
Keywords: |
|
Partial Vertex Cover, Approximation Algorithms, Max Cut |
|
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.08.2023 |
