×

Tree-related widths of graphs and hypergraphs. (English) Zbl 1162.05032

A hypergraph pair is a pair \((G,H)\) where \(G\) and \(H\) are hypergraphs on the same set of vertices. Author extends the definitions of hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. Syst. Sci. 64, No. 3, 579–627 (2002; Zbl 1052.68025)] and generalized hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. Syst. Sci. 66, No. 4, 775–808 (2003; Zbl 1054.68044)] from hypergraphs to hypergraph pairs. She shows that for constant \(k\) the problem of deciding whether a hypergraph pair has generalized hypertree-width \(\leq k\), is equivalent to the hypergraph sandwich problem (HSP) [A. Lustig and O. Shmueli, J. Algorithms 30, No. 2, 400–422 (1999; Zbl 0923.68095)]. It was recently proved in [G. Gottlob, Z. Miklas and T. Schwentick, Proceedings of the Symposium on Principles of Database Systems (PODS07)] that the HSP is NP-complete. For constant \(k\) there is a polynomial time algorithm that decides whether a given hypergraph pair has hypertree-width \(\leq k\). (For hypertree-width of hypergraphs, this was shown in [1].) It follows that the HSP is solvable in polynomial time for inputs \((G,H)\) satisfying: ghw\((G,H)\leq 1\) if and only if hw\((G,H)\leq 1\).
Besides this practical interest, hypergraph pairs serve as a tool for giving a common proof for the game theoretic characterizations of tree-width [P. D. Seymour and R. Thomas, J. Comb. Theory, Ser. B 58, No. 1, 22–33 (1993; Zbl 0795.05110)] and hypertree-width [2]. The author proves that monotone robber and \(k\)-marshals game on \((G,H)\) has a winning strategy if and only if hypertree-width of hypergraph pair \((G,H)\) is \(\leq k\).
Furthermore, they enable us to show a compactness property of generalized hypertree-width for a large class of hypergraphs, the hypergraphs with finite character. Finally, author presents two examples showing that neither hypertree-width of hypergraph pairs nor hypertree-width of hypergraphs has the compactness property.

MSC:

05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI Link