The treewidth of 2-section of hypergraphs

The treewidth of a graph is an important invariant in structural and algorithmic graph theory. The concept of treewidth was originally introduced by Bertelé and Brioschi [2] under the name of dimension. It was later rediscovered by Halin [7] in 1976 and by Robertson and Seymour [13] in 1984. Now it has been studied by many other authors (see for example [5]-[12]). Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms, since many NP-complete problems can be solved in polynomial time on graphs of bounded treewidth [3]. The relation between the treewidth and other graph parameters has been explored in a number of papers (see [10] for a recent survey). In [11], Harvey and Wood studied the treewidth of line graphs. They proved sharp lower bounds of the treewidth of the line graph of a graph $G$ in terms of both the minimum degree and the average degree of $G$. Motivated by their work, in this paper, we study the treewidth of $2$-section of linear hypergraphs.

A hypergraph is a pair $H=(V,F)$, where $V$ is a finite set of vertices and $F$ is a family of subsets of $V$ such that for any $f\in F$, $f\neq\emptyset$ and $V=\cup_{f\in F}f$. The size of $H$ is the cardinality of $F$. A simple hypergraph is a hypergraph $H$ such that if $f\subseteq g$, then $f=g$, where $f,g\in F$. If $|f|=1$, we call $f$ a loop. In this paper, we just consider simple and no loop hypergraphs. The rank and anti-rank of $H$ is defined as $r(H)=\max\limits_{f\in F}|f|$ and $s(H)=\min\limits_{f\in F}|f|$, respectively. If $r(H)=s(H)=2$, then $H$ is a graph. For any $v\in V$, denote $F(v)=\{f\in F|v\in f\}$. Then the degree of $v$, denoted by $deg(v)$, is $|F(v)|$. The maximum and minimum degree of $H$ will be denoted by $\Delta=\max_{v\in V}deg(v)$ and $\delta=\min_{v\in V}deg(v)$, respectively. If $\delta=\Delta=k$, then we call the hypergraph $k$-regular. The average rank of $H$ is defined as $l(H)=\sum_{f\in F}|f|/|F|$. A hypergraph $H$ is called linear if $|f\cap g|\leq 1$ for any $f,g\in F$ with $f\not=g$.

Let $H=(V,F)$ be a hypergraph (or graph), where $V=\{v_{1},\ldots,v_{n}\}$ and $F=\{f_{1},f_{2},\ldots,f_{m}\}$. The dual of $H$, denoted by $H^{*}=(V^{*},F^{*})$, is a hypergraph whose vertices $u_{1},u_{2},\ldots,u_{m}$ correspond to the edges of $H$ and with edges $g_{i}=\{u_{j}|v_{i}\in f_{j}\}$, $1\leq i\leq n$. The line graph of a (hyper)graph $H$, denoted by $L(H)$ is a graph whose vertices $w_{1},w_{2},\ldots,w_{m}$ correspond to the edges of $H$ and with edges $w_{i}w_{j}$ if $f_{i}\cap f_{j}\neq\emptyset$. Terminology and notation concerning hypergraph not defined here can be found in [1]. Now we give the definitions of treewidth. Let $T$ be a tree. We will use $T$ to denote the vertex set of $T$ for short.

In order to cite the definition of a generalized hypertree decomposition of a hypergraph which was given in [4], we introduce the definition of the 2-section of a hypergraph.

Now we give a new definition of decomposition of a hypergraph which is called a supertree decomposition of a hypergraph.

By Definition 1.4, if $(T,(B_{t})_{t\in T},(\lambda_{t})_{t\in T})$ is a supertree decomposition of $H$, then $(T,(\lambda_{t})_{t\in T})$ is a tree decomposition of $L(H)$. When $(T,(\lambda_{t})_{t\in T})$ is a tree decomposition of $L(H)$, we let $B_{t}=\cup_{f\in\lambda_{t}}f$. Then $(T,(B_{t})_{t\in T},(\lambda_{t})_{t\in T})$ is a supertree decomposition of $H$. So we have $stw(H)=tw(L(H))+1$.

From the Definition 1.2, we can get the following lemma.

By the definitions of line graph and the dual, we can easily get the following lemma.

Let $H$ be a hypergraph. There are two elementary lower bounds on treewidth of $[H]_{2}$. First,

since the vertices in a hyperedge form a clique in $[H]_{2}$. Second, given a minimum width tree decomposition of $[H]_{2}$, replace each vertex with all the hyperedges containing the vertex to obtain a supertree decomposition of $H$. It follows that

We prove the following lower bound on $tw([H]_{2})$ in terms of the minimum degree $\delta$, maximum degree $\Delta$ and average rank $l(H)$ of a linear hypergraph $H$.

In [11], Harvey and Wood showed that for every graph $G$, $tw(L(G))>\frac{1}{8}d(G)^{2}+\frac{3}{4}d(G)-2$, where $d(G)$ is the average degree of $G$. Let $H$ be a 2-regular linear hypergraph of order $n$ and size $m$. By Lemma 1.1, $[H]_{2}\cong L(H^{*})$. Note that $d(H^{*})=\frac{2n}{m}=l(H)$. By Theorem 1.1, $tw(L(H^{*}))=tw([H]_{2})>\frac{1}{8}d(H^{*})^{2}+\frac{3}{4}d(H^{*})-2$, just as the result in [11].

We also prove two lower bounds on $tw([H]_{2})$ in terms of the anti-rank $s(H)$ based on different condition of minimum degree of the given hypergraph $H$.

In [11], Harvey and Wood showed that for every graph $G$ with minimum degree $\delta(G)$,

Let $H$ be a 2-regular linear hypergraph. By Lemma 1.1, $[H]_{2}\cong L(H^{*})$. Then $tw(L(H^{*}))$ $=tw([H]_{2})$. Note that $\delta(H^{*})=s(H)$. Thus we can obtain the same result as that in [11] by Theorem 1.3. Now we consider upper bounds on $tw([H]_{2})$. It is easy to show that

To see this, we consider a minimum width supertree decomposition of $H$, and replace each bag $\lambda_{t}$ by the vertices that are incident to an hyperedge of $\lambda_{t}$. This creates a tree decomposition of $[H]_{2}$, where each bag contains at most $r(H)stw(H)$ vertices. In Section 5, we improve this bound as follows.

In [11], Harvey and Wood showed that for every graph $G$, $tw(L(G))\leq\frac{2}{3}(tw(G)+1)\Delta(G)+\frac{1}{3}tw(G)^{2}+\frac{1}{3}\Delta(G)-1$. Let $H$ be a 2-regular linear hypergraph. Recall that $stw(H)=tw(L(H))+1$. By Lemmas 1.1 and 1.2, $[H]_{2}\cong L(H^{*})$ and $H^{*}\cong L(H)$. Then $tw(H^{*})=stw(H)-1$. Note that $\Delta(H^{*})=r(H)$. By Theorem 1.4, $tw(L(H^{*}))=tw([H]_{2})\leq\frac{2}{3}(tw(H^{*})+1)\Delta(H^{*})+\frac{1}{3}tw(H^{*})^{2}+\frac{1}{3}\Delta(H^{*})-1$, just the same as that in [11].

The rest of this paper is organized as follows. In Section 2, some properties of tree decompositions of 2-section of hypergraphs are given. The proof of Theorem 1.1 is given in Section 3. In Section 4, we will prove Theorems 1.2 and 1.3. In Section 5, we prove Theorem 1.4. Section 6 concludes this paper.

In this section, we first give some properties of tree decompositions of 2-section of hypergraphs which will be used in next sections.

Let $H=(V,F)$ be a hypergraph. For any $v\in V$, recall that $F(v)=\{f\in F|v\in f\}$. Let $(T,(B_{t})_{t\in T})$ be a tree decomposition of $[H]_{2}$. For $u,v\in T$, we use $Path(u,v)$ to denote the path in $T$ connecting $u$ and $v$.

We call $b(f)$ the base node of $f$. From the proof of Lemma 2.1, we can construct a tree decomposition of $[H]_{2}$ so that we can assign a base node for each $f\in F$ and all the vertices in $f$ are placed in the corresponding bag $B_{b(f)}$. In fact, we can obtain a slightly stronger result that will be used to prove our theorems.

Given $(T,(B_{t})_{t\in T})$ and $b$ guaranteed by Lemma 2.1, we can also ensure that each base node is a leaf and that $b$ is a bijection between edges of $H$ and leaves of $T$. If $b(f)$ is not a leaf, then we add a leaf adjacent to $b(f)$ and let $b(f)$ be this leaf instead. If some leaf $t$ is the base node for several edges of $H$, then we add a leaf adjacent to $t$ for each edge assigned to $t$. Finally, if $t$ is a leaf that is not a base node, then delete $t$; this maintains the desired properties since a leaf is never an internal node of a subtree.

We can improve this further. Given a tree $T$, we can root it at a node and orient all edges away from the root. In such a tree, a leaf is a node with outdegree 0. Say a rooted tree is binary if every non-leaf node has outdegree 2. Given a tree decomposition, by the same way described in [11], we can root it and then modify the underlying tree so that each non-leaf node has outdegree 2. The above results give the following lemma.

By Lemma 2.2, we have the following lower bound on $tw([H]_{2})$ that is slightly stronger than (2).

In this section, we prove Theorem 1.1. Let $H=(V,F)$ be a hypergraph with size $m$. Let $V_{i}=\{v\in V(H)|deg(v)=i\}$ and $n_{i}=|V_{i}|$, where $i=\delta,\ldots,\Delta$. By the definition of average rank, $l(H)=(\delta n_{\delta}+\ldots+\Delta n_{\Delta})/m$. Given two sets $X,Y\subseteq F$. Let $\sigma^{j}_{i}(X)=\#\{v\in V_{i}|deg_{X}(v)=j\}$ and let $\sigma_{i}^{j,l}(X,Y)=\#\{v\in V_{i}|deg_{X}(v)=j\mbox{~{}and~{}}deg_{Y}(v)=l\}$, where $deg_{X}(v)=\#\{f|f\in F(v)\cap X\}$. We say a hypergraph $H$ is minimal if $l(H_{S})<l(H)$ for every nonempty proper subset $S$ of $F$, where

Firstly, we need some lemmas before we start bounding the tree width of $[H]_{2}$.

Let $(T,(B_{t})_{t\in T})$ be a tree decomposition of $[H]_{2}$ as guaranteed by Lemma 2.2. For each node $t$ of $T$, let $T_{t}$ denote the subtree of $T$ rooted at $t$ containing exactly $t$ and the descendants of $t$. And let $z(T_{t})$ be the set of edges of $H$ with the base nodes in $T_{t}$. (Recall all base nodes are leaves.)