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 >>>