Abstract
In the general AntiFactor problem, a graph G and, for every vertex v of G, a set X_v ⊆ ℕ of forbidden degrees is given. The task is to find a set S of edges such that the degree of v in S is not in the set X_v. Standard techniques (dynamic programming plus fast convolution) can be used to show that if M is the largest forbidden degree, then the problem can be solved in time (M+2)^{tw}⋅n^{O(1)} if a tree decomposition of width tw is given. However, significantly faster algorithms are possible if the sets X_v are sparse: our main algorithmic result shows that if every vertex has at most x forbidden degrees (we call this special case AntiFactor_x), then the problem can be solved in time (x+1)^{O(tw)}⋅n^{O(1)}. That is, AntiFactor_x is fixedparameter tractable parameterized by treewidth tw and the maximum number x of excluded degrees.
Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor₁ is already #W[1]hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set X, we denote by XAntiFactor the special case where every vertex v has the same set X_v = X of forbidden degrees. We show the following lower bound for every fixed set X: if there is an ε > 0 such that #XAntiFactor can be solved in time (max X+2ε)^{tw}⋅n^{O(1)} given a tree decomposition of width tw, then the Counting Strong ExponentialTime Hypothesis (#SETH) fails.
BibTeX  Entry
@InProceedings{marx_et_al:LIPIcs.IPEC.2022.22,
author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp},
title = {{AntiFactor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard)}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {22:122:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17378},
URN = {urn:nbn:de:0030drops173780},
doi = {10.4230/LIPIcs.IPEC.2022.22},
annote = {Keywords: AntiFactor, General Factor, Treewidth, Representative Sets, SETH}
}
Keywords: 

AntiFactor, General Factor, Treewidth, Representative Sets, SETH 
Collection: 

17th International Symposium on Parameterized and Exact Computation (IPEC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 