Given a graph $G$, we consider the problem of finding the largest set
of edge-disjoint triangles contained in $G$. We show that even the
simpler case of decomposing the edges of
a sparse split graph $G$ into edge-disjoint triangles
is NP-complete. We show next that the case of a general ... more >>>

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>

We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ... more >>>

Quantified constraint satisfaction is the generalization of
constraint satisfaction that allows for both universal and existential
quantifiers over constrained variables, instead
of just existential quantifiers.
We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>

We show how to find in Hamiltonian graphs a cycle of length
$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general
result in which we show that if $G$ has maximum degree $d$ and has a
cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),
then ... more >>>

We consider the problem of finding a $k$-vertex ($k$-edge)
connected spanning subgraph $K$ of a given $n$-vertex graph $G$
while minimizing the maximum degree $d$ in $K$. We give a
polynomial time algorithm for fixed $k$ that achieves an $O(\log
n)$-approximation. The only known previous polynomial algorithms
achieved degree $d+1$ ... more >>>

We study the problem of assigning different communication channels to
acces points in a wireless Local Area Network. Each access point will
be assigned a specific radio frequency channel. Since channels with
similar frequencies interfere, it is desirable to assign far apart
channels (frequencies) to nearby access points. Our goal ... more >>>

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

The $H$-matching problem asks to partition the vertices of an input graph $G$
into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$
isomorphic to $H$. The $H$-matching problem has been classified as polynomial
or NP-complete depending on whether $k\leq 2$ or not. We consider a variant
more >>>

Barnette's conjecture is the statement that every 3-connected cubic
planar bipartite graph is Hamiltonian. Goodey showed that the conjecture
holds when all faces of the graph have either 4 or 6 sides. We
generalize Goodey's result by showing that when the faces of such a
graph are 3-colored, with adjacent ... more >>>

Matroid intersection has a known polynomial time algorithm using an
oracle. We generalize this result to delta-matroids that do not have
equality as a restriction, and give a polynomial time algorithm for
delta-matroid intersection on delta-matroids without equality using an
oracle. We note that when equality is present, delta-matroid intersection
more >>>

Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>