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.IPEC.2020.17
URN: urn:nbn:de:0030-drops-133206
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13320/
Go to the corresponding LIPIcs Volume Portal

Feldmann, Andreas Emil ; Issac, Davis ; Rai, Ashutosh

Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem

pdf-format:
LIPIcs-IPEC-2020-17.pdf (0.6 MB)

Abstract

We develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with n vertices and integer edge weights is given together with an integer k, and the aim is to find k cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into k cliques. It was shown that ECP admits a kernel with k² vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of 2^?(k²)n^O(1) [Issac, 2019]. For WECP we develop a compression (to a slightly more general problem) with 4^k vertices, and an algorithm with runtime 2^?(k^(3/2)w^(1/2)log(k/w))n^O(1), where w is the maximum edge weight. The latter in particular improves the runtime for ECP to 2^?(k^(3/2)log k)n^O(1).

BibTeX - Entry

@InProceedings{feldmann_et_al:LIPIcs:2020:13320,
  author =	{Andreas Emil Feldmann and Davis Issac and Ashutosh Rai},
  title =	{{Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13320},
  URN =		{urn:nbn:de:0030-drops-133206},
  doi =		{10.4230/LIPIcs.IPEC.2020.17},
  annote =	{Keywords: Edge Clique Partition, fixed-parameter tractability, kernelization}
}

Keywords: Edge Clique Partition, fixed-parameter tractability, kernelization
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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