CISPA
Browse
cispa_all_3833.pdf (983.22 kB)

Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)

Download (983.22 kB)
conference contribution
posted on 2023-11-29, 18:23 authored by Dániel MarxDániel Marx, Govind Sankar, Philipp SchepperPhilipp Schepper
In the general AntiFactor problem, a graph $G$ and, for every vertex $v$ of $G$, a set $X_\subseteq \mathbb{N}$ of forbidden degrees is given. The task is to find a set $S$ of edges such that the degree of $v$ in $S$ is \emph{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 $O*((M+2)^k)$ if a tree decomposition of width $k$ 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 $O*((x+1)^{O(k)})$. That is, AntiFactor_x is fixed-parameter tractable parameterized by treewidth $k$ 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_1 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 X-AntiFactor 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 $\epsilon>0$ such that #X-AntiFactor can be solved in time $O*((\max X+2-\epsilon)^k)$ given a tree decomposition of width $k$, then the Counting Strong Exponential-Time Hypothesis (#SETH) fails.

History

Preferred Citation

Dániel Marx, Govind Sankar and Philipp Schepper. Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard). In: International Symposium on Parameterized and Exact Computation (IPEC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Symposium on Parameterized and Exact Computation (IPEC)

Legacy Posted Date

2022-10-13

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3833, title = "Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)", author = "Marx, Dániel and Sankar, Govind and Schepper, Philipp", booktitle="{International Symposium on Parameterized and Exact Computation (IPEC)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC