Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
272 views

Hardness of 3-dimensional matching variant

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
6
votes
1answer
158 views

Intersection models for weakly chordal graphs?

Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :) Among the many known classes of perfect graphs, there ...
10
votes
4answers
289 views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

A planar graph is a graph which can be embedded in the plane, without having crossing edges. Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k. ...
5
votes
1answer
141 views

Best approximation for a HYPERGRAPH-MAXDICUT problem

Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
12
votes
4answers
677 views

hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
19
votes
2answers
3k views

Recognizing line graphs of hypergraphs

The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection. A hypergraph is an ...
5
votes
0answers
208 views

k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question ...
10
votes
4answers
535 views

What are the root difficulties in going from graphs to hypergraphs?

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 ...
11
votes
2answers
440 views

Are shift-chains two-colorable?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ...
8
votes
1answer
199 views

CSPs with unbounded fractional hypertree width

At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional ...
7
votes
1answer
410 views

Max-clique in line graph of hypergraph

Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
4
votes
0answers
209 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
10
votes
2answers
333 views

Consequences of lower bounds for $\epsilon$-nets on approximation

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
12
votes
1answer
330 views

Efficient algorithm for near-optimal edge-colourings of hypergraphs

Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring. Question. What efficient algorithms are ...
14
votes
5answers
550 views

“All-different hypergraph coloring” - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...