U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

The {\it nucleon} is introduced as a new allocation concept for

non-negative cooperative n-person transferable utility games.

The nucleon may be viewed as the multiplicative analogue of

Schmeidler's nucleolus.

It is shown that the nucleon of (not necessarily bipartite) matching

games ...
more >>>

Eric Allender, Klaus Reinhardt

We show that the perfect matching problem is in the

complexity class SPL (in the nonuniform setting).

This provides a better upper bound on the complexity of the

matching problem, as well as providing motivation for studying

the complexity class SPL.

Using similar ...
more >>>

Elad Hazan, Shmuel Safra, Oded Schwartz

We study bounded degree graph problems, mainly the problem of

k-Dimensional Matching \emph{(k-DM)}, namely, the problem of

finding a maximal matching in a k-partite k-uniform balanced

hyper-graph. We prove that k-DM cannot be efficiently approximated

to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.

This ...
more >>>

Janka Chlebíková, Miroslav Chlebik

We study small degree graph problems such as Maximum Independent Set

and Minimum Node Cover and improve approximation lower bounds for

them and for a number of related problems, like Max-B-Set Packing,

Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.

For example, we prove NP-hardness factor of 95/94

more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

Aayush Ojha, Raghunath Tewari

Recently, perfect matching in bounded planar cutwidth bipartite graphs

$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that

the problem is in AC$^0$.

In this paper, we disprove their conjecture by showing that the problem is

not in AC$^0[p^{\alpha}]$ for every prime $p$. ...
more >>>

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>