An Extension of 3-Dimensional Matching

MARCELO MYDLARZ

París

Conferencia; 26th Conference of European Chapter on Combinatorial Optimization (ECCO XXVI); 2013

Consider the following problem (which can be easily shown to be a special case of 3-DIMENSIONAL MATCHING):    given a set $T$ of ordered triples and an integer $t$,    decide whether there is a subset $M$ of $T$ such that    $|M|=t$ and such that no two triples in $M$ agree in two coordinates.An application is presented, as well as some structural properties ofthe problem. We will infer that for $k \ge 3$ and $p<k$ the corresponding problem with $k$-tuples and $p$ coordinatesproblem is \np-complete.