Paper Info
Title
A Monadic Second-Order Definition of the Structure of Convex Hypergraphs
Abstract
We consider finite hypergraphs with hyperedges defined as sets of vertices of unbounded cardinality. Each such hypergraph has a unique modular decomposition, which is a tree, the nodes of which correspond to certain subhypergraphs (induced by certain sets of vertices called strong modules) of the considered hypergraph. One can define this decomposition by monadic second-order (MS) logical formulas. Such a hypergraph is convex if the vertices are linearly ordered in such a way that the hyperedges form intervals. Our main result says that the unique linear order witnessing the convexity of a prime hypergraph (i.e., of one, the modular decomposition of which is trivial) can be defined in MS logic. As a consequence, we obtain that if a set of bipartite graphs that correspond (in the usual way) to convex hypergraphs has a decidable monadic second-order theory (which means that one can decide whether a given MS formula is satisfied in some graph of the set) then it has bounded clique-width. This yields a new case of validity of a conjecture which is still open.
Year
DOI
Venue
2002
10.1006/inco.2002.3130
Information and Computation
Keywords
Field
DocType
hypergraph
Discrete mathematics,Modular decomposition,Combinatorics,Vertex (geometry),Bipartite graph,Hypergraph,Constraint graph,Algorithm,Decidability,Clique-width,Monadic predicate calculus,Mathematics
Journal
Volume
Issue
ISSN
178
2
0890-5401
Citations 
PageRank 
References 
2
0.36
16
Authors
1
Name
Order
Citations
PageRank
Bruno Courcelle13418388.00