10
$\begingroup$

There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems often become much harder over 3-uniform hypergraphs than over 2-uniform graphs? What are the root difficulties?

One issue is that we don't, as of yet, have a satisfactory understanding of spectral hypergraph theory. Please feel free to shed more light on this issue. But I'm also looking for other reasons which make hypergraphs more difficult objects.

Improve this question
$\endgroup$
6
  • $\begingroup$ I wonder to what extent this is related to related to the recent discussion about the change in complexity of geometric problems going from 2D to 3D (cstheory.stackexchange.com/questions/5251/…). The reason I say this is that you can associate edges in a 2-uniform graph with locations on a 2D lattice, while a 3-uniform hypergraph would then have hyperedges corresponding to locations in a 3d lattice. $\endgroup$
    – Joe Fitzsimons
    Mar 21, 2011 at 16:29
  • $\begingroup$ @Joe Fitzsimons: good point. But concepts and techniques which are natural in the (hyper)graph setting, such as subgraphs, colorings, partitionings, etc., may not be that natural in the geometric setting. Also, I agree with you in that there's a "two-to-three" transition in many areas. $\endgroup$
    – arnab
    Mar 21, 2011 at 16:36
  • 2
    $\begingroup$ Your question is hard since a satisfactory answer would resolve the P vs NP problem. Note that perfect matching is easy for 2-uniform graphs while it is hard for 3-uniform hypergraphs. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 21, 2011 at 18:53
  • $\begingroup$ Is hypergraph a well defined concept? (For one thing this site spellchecker doesn't know about it:-) Is it a relation of fixed or variable arity? $\endgroup$
    – Tegiri Nenashi
    Mar 22, 2011 at 20:37
  • $\begingroup$ Ok, after visiting wikipedia, I see that it is not actually a relation, but a family of sets. Does mainstream mathematics takes this "hypergraph" concept seriously? $\endgroup$
    – Tegiri Nenashi
    Mar 22, 2011 at 20:41

4 Answers 4

Reset to default
8
$\begingroup$

In this question I understand "difficulty" refers not to "difficult to compute," but to "difficult to study."

Graph problems are easier (at least for me) to study since some concepts happen to be equivalent. In other words, if you want to generalize questions for graphs to those for hypergraphs, you need to pay attention to the "right" generalization so that the desired consequence can be obtained.

For example, consider a tree. For graphs, a graph is a tree if it is connected and contains no cycle. This is equivalent to being connected and having n-1 edges (where n is the number of vertices), and also equivalent to containing no cycle and having n-1 edges. However, for 3-uniform hypergraphs, let's say a 3-uniform hypergraph is a tree if it is connected and contains no cycle. But, this is not equivalent to being connected and having n-1 hyperedges, nor to containing no cycle and having n-1 hyperedges.

I've heard a main difficulty to prove the regularity lemma for uniform hypergraphs was to come up with the right definitions of regularity and related concepts.

When you want to consider "spectral hypergraph theory," you may try to look into tensors, or into homology if you see a k-uniform hypergraph as a (k-1)-dimensional simplicial complex, from which linear algebra naturally arises. I don't know which is the "right" generalization for your purpose, or it's possible that neither is right.

Improve this answer
$\endgroup$
7
$\begingroup$

I think this is in large part due to Lawler's "mystical power of twoness" (the observation that many parameterized problems are in P for param=2 and NP-complete for param≥3). A graph is a thing that connects 2-tuples of vertices, and a hypergraph is a thing that connects k-tuples of vertices for k≥3.

So, e.g., 2-SAT is in P, and is essentially a graph problem, whereas 3-SAT is a problem on 3-uniform hypergraphs and is NP-complete.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ To be more precise, I meant to ask if one can identify some fundamental reasons for why graph-theoretic techniques break down. For example, we don't really have linear-algebraic methods for hypergraphs because tensor rank is not well-understood (e.g., it's NP-hard to compute). $\endgroup$
    – arnab
    Mar 21, 2011 at 21:23
  • 1
    $\begingroup$ The intent of my answer wasn't so much "these problems are hard for computers to solve" but rather that there is a strong correlation between P/NPC and having/not having nice mathematical characterizations. So the problems get harder to study in tandem with their becoming NPC. $\endgroup$
    – David Eppstein
    Mar 22, 2011 at 1:09
  • 7
    $\begingroup$ In this contex, the recently posted question cstheory.stackexchange.com/questions/14950/… is quite interesting: Recognizing line graphs of 2-hypergraphs, i.e., line graphs of (multi)graphs, is in P, whereas recognizing line graphs of 3-hypergraphs seems to be an open problem. Note also that the characterization problem for 3-hypergraphs (by forbidden induced subgraphs) is still open, while line graphs of (multi)graphs admit several such characterizations. $\endgroup$
    – vb le
    Jan 12, 2013 at 11:53
5
$\begingroup$

Another reason would be that we have much more knowledge in binary relations than any other n-ary relations for n greater than 2.

Naturally we consider binary relations between objects, like adjacency, nonempty intersection, equivalence, etc. So we can define graphs in terms of binary relations, and even define graph based on some binary relation on another graph. (For example, line graphs, clique trees, tree decompositions...)

But as for other n-ary relations, we do not have much understanding. For example, it takes some time to come up with an interesting ternary relation; (Okay, partially due to my ignorance) properties are weaker and tools are much lesser in the study of ternary relations. (How do we define symmetric or transitive ternary relations? Both of them are among the most important relations one can study.)

But still I don't know why this happens between binary and ternary relations. Maybe as turkistany said this question is hard and may be related to the understanding of P/NP problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ [Cylindric and polyadic algebras notwithstanding] there is no compelling algebra for n-ary relations. The debate can be even lowered to the level when one argue positional vs. named perspective to relation attributes. $\endgroup$
    – Tegiri Nenashi
    Mar 22, 2011 at 20:31
2
$\begingroup$

I was first going to answer the wrong question : "which example of problems are much harder in hypergraphs than in graphs". I was particularly impressed by the difference in dealing with the maximum matching problem in graphs, and the same with hypergraphs (a set of pairwise disjoint edges), which very easily can model coloring, max independent set, max clique...

Then I noticed it was not your question : "what are the root difficulties between the two ?".

Well, to that one I would answer that up to now I haven't seen much common points between graphs and hypergraphs. Except the name itself. And the fact that a lot of people are trying to "extend" the results from the first to the other.

I had the occasion to flip the pages of Berge's "Hypergraphs" and Bollobas' "Set systems" : they contain many tasty results, and the ones I found the most interesting had few to say about graphs. For instance Baranyai's theorem (there is a nice proof in Jukna's book).

I don't know much of them but I am thinking about a hypergraph problem right now and all I can say about it is that I don't feel any graph lurking anywhere around. Perhaps we think of them as "difficult" because we are just trying to study them with the wrong tools. I don't expect the graph problems I'm working on to vanish immediately by using number theory (even though it happens sometimes).

Oh, and something else. They are perhaps harder to study because they are combinatorially much.... more ?!

"try them all and see when it works" is sometimes a good idea for graphs, but with hypergraphs one it quickly humbled by the numbers. :-)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.