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.STACS.2022.42
URN: urn:nbn:de:0030-drops-158525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15852/
Koana, Tomohiro ;
Komusiewicz, Christian ;
Nichterlein, André ;
Sommer, Frank
Covering Many (Or Few) Edges with k Vertices in Sparse Graphs
Abstract
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed α between zero and one we are given a graph and two numbers k ∈ ℕ and t ∈ ℚ. The task is to find a vertex subset S of exactly k vertices that has value at least (resp. at most for minimization) t. Here, the value of a vertex set computes as α times the number of edges with exactly one endpoint in S plus 1-α times the number of edges with both endpoints in S. These two problems generalize many prominent graph problems, such as Densest k-Subgraph, Sparsest k-Subgraph, Partial Vertex Cover, and Max (k,n-k)-Cut.
In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max (k,n-k)-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.
BibTeX - Entry
@InProceedings{koana_et_al:LIPIcs.STACS.2022.42,
author = {Koana, Tomohiro and Komusiewicz, Christian and Nichterlein, Andr\'{e} and Sommer, Frank},
title = {{Covering Many (Or Few) Edges with k Vertices in Sparse Graphs}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {42:1--42:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15852},
URN = {urn:nbn:de:0030-drops-158525},
doi = {10.4230/LIPIcs.STACS.2022.42},
annote = {Keywords: Parameterized Complexity, Kernelization, Partial Vertex Cover, Densest k-Subgraph, Max (k,n-k)-Cut, Degeneracy}
}
|
Keywords: |
|
Parameterized Complexity, Kernelization, Partial Vertex Cover, Densest k-Subgraph, Max (k,n-k)-Cut, Degeneracy |
|
Collection: |
|
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
09.03.2022 |
