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.ICALP.2021.95
URN: urn:nbn:de:0030-drops-141647
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14164/
Marx, Dániel ;
Sankar, Govind S. ;
Schepper, Philipp
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Abstract
In the General Factor problem, we are given an undirected graph G and for each vertex v ∈ V(G) a finite set B_v of non-negative integers. The task is to decide if there is a subset S ⊆ E(G) such that deg_S(v) ∈ B_v for all vertices v of G. Define the max-gap of a finite integer set B to be the largest d ≥ 0 such that there is an a ≥ 0 with [a,a+d+1] ∩ B = {a,a+d+1}. Cornuéjols showed in 1988 that if the max-gap of all sets B_v is at most 1, then the decision version of General Factor is polynomial-time solvable. This result was extended 2018 by Dudycz and Paluch for the optimization (i.e. minimization and maximization) versions. We present a general algorithm counting the number of solutions of a certain size in time #2 (M+1)^{tw}^{?(1)}, given a tree decomposition of width tw, where M is the maximum integer over all B_v. By using convolution techniques from van Rooij (2020), we improve upon the previous (M+1)^{3tw}^?(1) time algorithm by Arulselvan et al. from 2018.
We prove that this algorithm is essentially optimal for all cases that are not trivial or polynomial time solvable for the decision, minimization or maximization versions. Our lower bounds show that such an improvement is not even possible for B-Factor, which is General Factor on graphs where all sets B_v agree with the fixed set B. We show that for every fixed B where the problem is NP-hard, our (max B+1)^tw^?(1) algorithm cannot be significantly improved: assuming the Strong Exponential Time Hypothesis (SETH), no algorithm can solve B-Factor in time (max B+1-ε)^tw^?(1) for any ε > 0. We extend this bound to the counting version of B-Factor for arbitrary, non-trivial sets B, assuming #SETH.
We also investigate the parameterization of the problem by cutwidth. Unlike for treewidth, having a larger set B does not appear to make the problem harder: we give a 2^cutw^?(1) algorithm for any B and provide a matching lower bound that this is optimal for the NP-hard cases.
BibTeX - Entry
@InProceedings{marx_et_al:LIPIcs.ICALP.2021.95,
author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp},
title = {{Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {95:1--95:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14164},
URN = {urn:nbn:de:0030-drops-141647},
doi = {10.4230/LIPIcs.ICALP.2021.95},
annote = {Keywords: General Factor, General Matching, Treewidth, Cutwidth}
}
|
Keywords: |
|
General Factor, General Matching, Treewidth, Cutwidth |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
