Generalized Graph Packing Problems Parameterized by Treewidth

Let $H$ be a fixed graph and $c\ge 1$ be an integer. Given a graph $G$, a subgraph $Z$ of $G$ is called a copy of $H$ if $Z$ is isomorphic to $H$. Moreover, if $Z$ is a copy of $H$ in $G$, we say that $Z$ covers $v$ if $v\in V(Z)$.

Observe that when $c$ is equal to $1$, two copies of $H$ are not allowed to have any common vertices. Therefore, in this case, the notions of $(c,H)\text{-single-packing}$ and $(c,H)\text{-multi-packing}$ coincide, and we write $H\text{-packing}$ to simpify the notation. We define $H\text{-partition}$ in a similar way. The first problem we introduce, $\text{Generalized Graph Packing}(H)$, asks the maximum size of an $H\text{-packing}$ in $G$.

$\text{Generalized Graph Packing}(H)$ Input: A graph $G$ Output: The size of a largest $H\text{-packing}$ in $G$.

For a fixed $H$, we show that $\text{Generalized Graph Packing}(H)$ can be solved in time $2^{𝒪\left(w\cdot \log w\right)}\cdot n^{𝒪\left(1\right)}$ for graphs of treewidth $w$.

Then, we define partitioning problems in which each vertex of $G$ must be covered the same number of times. For an arbitrary graph $H$, we let $c=1$ which results in vertex disjoint copies of $H$.

$\text{Generalized Graph Partitioning}(H)$ Input: A graph $G$ Question: Is there an $H\text{-packing}$ of $G$ such that each vertex is covered exactly once?

Observe that $\text{Generalized Graph Partitioning}(H)$ is a special case of the problem $\text{Generalized Graph Packing}(H)$, which implies an algorithm with running time $2^{𝒪\left(w\cdot \log w\right)}\cdot n^{𝒪\left(1\right)}$ for the $\text{Generalized Graph Partitioning}(H)$ problem on graphs of treewidth $w$. We show that this running time cannot be improved for many choices of $H$.

When $H$ is a clique, we consider the more general problem in which a vertex $v\in V(G)$ can be covered more than once, at most $c$ times for some $c\ge 1$. Therefore, we distinguish between two variants of the problem: one where each clique can be selected at most once, and another without restriction. The $\text{Multi-Clique Packing}(c,d)$ problem asks the maximum size of a $(c,K_d)\text{-multi-packing}$ in $G$.

$\text{Multi-Clique Packing}(c,d)$ Input: A graph $G$ Output: The size of a largest $(c,K_d)\text{-multi-packing}$ in $G$.

Similar to the $\text{Multi-Clique Packing}(c,d)$ problem, the $\text{Single-Clique Packing}(c,d)$ problem asks the maximum size of a $(c,K_d)\text{-single-packing}$ in $G$.

$\text{Single-Clique Packing}(c,d)$ Input: A graph $G$ Output: The size of a largest $(c,K_d)\text{-single-packing}$ in $G$.

In the full version of the paper we show that $\text{Single-Clique Packing}(c,d)$ admits a single-exponential time algorithm where the same algorithmic result also applies to $\text{Multi-Clique Packing}(c,d)$ with slight modifications.

Moreover, we define partitioning problems where $H$ is a clique.

$\text{Multi-Clique Partitioning}(c,d)$ Input: A graph $G$ Question: Is there a $(c,K_d)\text{-multi-partition}$ of $G$?

$\text{Single-Clique Partitioning}(c,d)$ Input: A graph $G$ Question: Is there a $(c,K_d)\text{-single-partition}$ of $G$?

Similarly, we prove that this running time is optimal up to polynomial factors in the size of the input graph.

Finally, we show that the lower bound result in Theorem 5 can also be transferred similarly.

A graph $H$ is $k$-connected if for each $A\subseteq V(H)$ such that $|A|=k-1$ it holds that $H\setminus A$ is connected. A graph is also called biconnected if it is $2$-connected, and a block is a maximal $2$-connected component of $H$. Similarly, a graph $H$ is called a block graph if every block of $H$ is a clique.

A vertex $v$ of a connected graph $H$ is a cutvertex if $G\setminus v$ is disconnected. In this paper, we refer to both the blocks of a graph and the nodes of the corresponding block tree interchangeably, with a slight abuse of notation. While formally distinct, we find it convenient to treat them as equivalent entities for the sake of clarity and brevity. For a vertex $h\in V(H)$ and a block $B\in {ℬ}_H$ , we write $h\in B$ if $h\in V(B)$.

We use the Iverson bracket $⟦P⟧$, which is defined to be $1$ if the proposition $P$ is true and $0$ otherwise.

In this paper, we derive our lower bounds via reductions from well-studied base problems whose intractability is established under standard complexity hypotheses. Each reduction makes use of compact, purpose-built gadgets – small graphs whose behavior can be precisely engineered. Embedding these gadgets into our constructions yields intuitive, transparent proofs that highlight the underlying ideas without excessive technical overhead.

More formally, we define a gadget $G$ as a graph with designated portal vertices $\{p_1,\mathrm{\dots },p_{\mathrm{\ell }}\}\subseteq V(G)$, where the vertices $\mathrm{int}\left(G\right)≔\left(G\setminus \{p_1,\mathrm{\dots },p_{\mathrm{\ell }}\}\right)$ are called internal vertices. We say that a graph $E$ is an extension of a gadget $G$ if $E$ contains $G$ as an induced subgraph, where each internal vertex $v$ of $G$ satisfies

In other words, in an extension $E$, only the portal vertices of $G$ can have neighbors outside of $G$.

We also require gadgets to behave in a structured way. Whenever a copy of $H$ intersects the gadget, it must lie entirely within the gadget when connected to a larger graph. We formalize this in the following definition.

Next, we define the relation realized by a gadget.

We say a relation $R\subseteq {\{0,\mathrm{\dots },c\}}^{\mathrm{\ell }}$ is $(x,d)\text{-regular}$ for $d\ge 1$ and $0\le x\le d-1$ if for each $r\in R$, the weight of $r$ is equivalent to $xmodd$, i.e. $𝐰(r)≔\left({\sum }_{i\in [\mathrm{\ell }]}{r}_i\right)=xmodd$. Moreover, a relation $R$ has weight $X$ if $\left({\max }_{r\in R}𝐰(r)\right)=X$. Recall that a gadget is a small, engineered graph used to enforce specific behaviors in a reduction. We streamline the lower bound constructions by building general-purpose gadgets that can realize any relation. The descriptions of the gadgets are deferred to the full version of the paper. This way, we avoid repetitive constructions and keep the focus on the core ideas.

When $c\ge 1$, we require the relation to have more structure, i.e., the relation should be $(0,|H|)\text{-regular}$. However, this restriction can be easily handled in our lower bound constructions.

In this section, we give an overview of how the above-described gadgets are used to prove Theorem 6. Classically, when proving conditional lower bounds based on SETH, one needs to find a reduction from SAT. However, this usually involves carrying out repetitive, unnecessary work that is not specific to the problem one is working on. One of the strengths of the framework introduced by Lampis [7] is removing the need for such repetitive constructions.

The primal graph of a CSP instance $\psi$ is a graph $G$ that has a vertex for each variable of $\psi$, and there is an edge between $x,y\in V(G)$ if $x$ and $y$ appear together in a constraint. The pathwidth of the CSP instance $\psi$ is defined to be the pathwidth of its primal graph. Similarly, by path decomposition of $\psi$, we mean a path decomposition of the primal graph of $\psi$. The following lemma from [7] implies that we can assume the path decomposition to be nice.

The following conjecture from [7], called $\mathrm{𝐩𝐰}$-SETH, will form the basis of our hardness results.

Moreover, we have the following result from [7], which proves the equivalence of falsifying $\mathrm{𝐩𝐰}$-SETH and finding a faster algorithm for 2-CSP.

Motivated by Theorem 15, Section 3 presents a reduction from the $2$-CSP problem to the Single-Clique Partitioning(c,d) problem. The core idea is to encode each variable’s $B$ possible assignments using a set of vertices whose coverage count in a $(c,K_d)\text{-single-packing}$ represents the chosen value. We then introduce gadgets each enforcing a single constraint of the $2$-CSP instance via carefully specified relations so that only coverage patterns corresponding to satisfying assignments are possible. By designing these gadgets to interact locally, we ensure the pathwidth of the resulting instance increases by at most a constant, completing the reduction.

We now give a high-level description of the proof of Theorem 3. Let $H$ be a graph with at least $3$ vertices that is not a block graph. Next, we will describe the lower bound for the $\text{Generalized Graph Partitioning}(H)$ problem which is stated in Theorem 3. Recall that $\text{Generalized Graph Partitioning}(H)$ is solvable in slightly super-exponential time for any fixed graph $H$, i.e., there is an algorithm with running time ${𝒪}^{\ast }\left(2^{O(tw\cdot \log tw)}\right)$.¹¹1The $O^{\ast }(f(k))$ notation suppresses polynomial factors in the input size $n$; that is, $O^{\ast }(f(k))=O(f(k)\cdot n^c)$ for some constant $c$. We show that this running time is optimal under ETH, i.e. there exists no algorithm for $\text{Generalized Graph Partitioning}(H)$ with running time ${𝒪}^{\ast }\left(2^{o(tw\cdot \log (tw))}\right)$. To that end, we use an auxiliary problem for which such a lower bound was presented in [4]. Specifically, we define the $k\times k\text{ Permutation Independent Set}$ problem where given a graph $G$ on a vertex set $[k]\times [k]$, we ask whether there exists an independent set $X$ in $G$ that contains exactly one vertex from each row and each column.

$k\times k\text{ Permutation Independent Set}$ Input: A graph $G$ on the vertex set $[k]\times [k]$ Question: Is there an independent set $X$ of $G$ such that $X$ induces a permutation on $[k]\times [k]$?

The following hardness result was presented for the analogous $k\times k\text{ Permutation Clique}$ problem in [4] which translates easily to $k\times k\text{ Permutation Independent Set}$. Below we state it for $k\times k\text{ Permutation Independent Set}$.

To prove Theorem 3, we reduce the $k\times k\text{ Permutation Independent Set}$ problem to $\text{Generalized Graph Partitioning}(H)$. The construction relies on structural properties of $H$. Let $B$ be a block in $H$ with a minimum separator $S$ such that $B\setminus S$ has at least two connected components. Since $H$ contains a non-clique block, such $B$ and $S$ exist. We partition $S$ into two subsets, $U$ and $D$, and create $k$ copies of each. The construction in the proof of Theorem 3 ensures that any $|H|\text{-packing}$ includes $k$ copies of $H$, each covering exactly one copy of $U$ and one of $D$. This yields $k!=2^{𝒪\left(k\cdot \log k\right)}$ configurations, corresponding to all permutations of a set of size $k$. Additionally, for each edge $e$ in the $k\times k\text{ Permutation Independent Set}$ instance, we introduce a gadget to prevent $e$ from being included in the set of vertices induced by this permutation. Moreover, these gadgets are designed to preserve pathwidth by interacting only locally. The detailed proof of Theorem 3 is deferred to the full version of the paper.

Recall that a tree decomposition of a graph $G=(V,E)$ is a pair $(T,{\{X_t\}}_{t\in T})$, where $T$ is a tree whose every node $t$ is assigned a bag $X_t\subseteq V(G)$, satisfying the following properties:

1. 1.

   For every vertex $v\in V$, there exists at least one bag $X_t$ such that $v\in X_t$.

2. 2.

   For every edge $(u,v)\in E$, there exists a bag $X_t$ such that $\{u,v\}\subseteq X_t$.

3. 3.

   For every vertex $v\in V$, the set of nodes $\{t\in V(T)\mid v\in X_t\}$ induces a connected subtree of $T$.

The width of a tree decomposition is the size of its largest bag minus one, and the treewidth of $G$ is the minimum width over all possible tree decompositions of $G$. A nice tree decomposition is a rooted tree decomposition in which each node is one of the four types: leaf, introduce, forget or join. We refer the reader to [4] for more details.

The algorithmic results in Theorems 2 and 4 follow a fairly standard dynamic programming framework over tree decompositions. We define a suitable set of states for each bag in the decomposition, capturing the essential information needed to extend partial solutions. The main challenge of the approach lies in carefully designing these states and proving the correctness of the update rules that determine how states transition from one bag to the next. Usually what determines the running time is the state representation and transitions to the specific structural constraints of our problem.

In particular, the single-exponential algorithm for the $\text{Single-Clique Packing}(c,d)$ problem defines the state of a bag based on how many times each vertex in the bag is covered by a partial solution. This yields ${(c+1)}^{\mathrm{\ell }}$ states for a bag of size $\mathrm{\ell }$, naturally leading to a running time of ${(c+1)}^{tw}\cdot n^{𝒪\left(1\right)}$.

In contrast, the slightly superexponential algorithm for the $\text{Generalized Graph Packing}(H)$ problem requires keeping track of a partition of the bag, in which each part corresponds to a partial copy of $H$. This results in $𝒪({\mathrm{\ell }}^{\mathrm{\ell }})$ possible states for a bag of size $\mathrm{\ell }$, leading to an overall running time of $2^{𝒪(tw\cdot \log tw)}\cdot n^{𝒪(1)}$. The algorithms are presented in detail in the full version of the paper.

We first prove Theorem 5. To that end, intuitively, we show that a fast algorithm for the $\text{Multi-Clique Partitioning}(c,d)$ problem implies a fast algorithm for the $2$-CSP problem.