Egres:Rough problems
We have integers [math]c_{ij}[/math] (i=1,...,n, j=1,...,n). Decide if there are permutations [math]\pi_i[/math] (i=1,...,n) and [math]\sigma_j[/math] (j=1,...,n) such that [math]\pi_i(j)+\sigma_j(i) \leq c_{ij}[/math] for every i,j. Papjuli
When does a 3-hypergraph have 2 (or 3) head-disjoint strongly connected orientations? Berkri
Let D=(V,A) be a digraph and F a laminar family of bi-sets on V. Is it true that the incidence matrix Q is always totally unimodular where the rows of Q correspond to the members of F, the columns of Q to the edges of D and an entry of Q corresponding to bi-set [math]Z \in F[/math] and edge [math]e \in A[/math] is 1 if e covers Z. Note that the corresponding statement for a laminar family of subsets is known to be true. Berkri
Find a circuit of minimum size in a hypergraphic matroid. Jani, Király Csaba
Given a graph G=(V,E), find a node set U of minimum size such that [math]G+K_U[/math] is k-partition-connected.
Is it true that if a digraph D is the union of k arc-disjoint arborescences, and v is a node of out-degree at most k, then D can be partitioned into k arborescences such that the arcs leaving v are in different arborescences?
Let G=(V,E) be an undirected graph. A d-dimensional vector flow on G is an orientation of G together with a d-dimensional unit-length vector f(e) for every edge e, such that the sum of the vectors on the incoming arcs minus the sum of the vectors on the outgoing arcs is zero. (Note that if there is a vector flow then there is one for each orientation). Is it true that every 2-edge-connected graph has a 3-dimensional vector flow? Papjuli
Complexity of deciding kernel-perfectness.
Is it in P whether a given perfect graph has a kernel-perfect orientation which satisfies given degree-constraints?
Oda's question: are all smooth polytopes integrally closed? See [1]
Integrality gap of bidirectional relaxation for Steiner tree
