All reports by Author Tomas Feder:

__
TR12-013
| 15th February 2012
__

Tomas Feder, Carlos Subi#### Packing Edge-Disjoint Triangles in Given Graphs

__
TR08-087
| 31st July 2008
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

__
TR07-063
| 2nd July 2007
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

__
TR06-160
| 17th December 2006
__

Tomas Feder, Phokion G. Kolaitis#### Closures and dichotomies for quantified constraints

__
TR06-156
| 7th December 2006
__

Tomas Feder, Rajeev Motwani#### Finding large cycles in Hamiltonian graphs

__
TR06-041
| 6th March 2006
__

Tomas Feder, Rajeev Motwani, An Zhu#### k-connected spanning subgraphs of low degree

__
TR06-040
| 6th March 2006
__

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu#### Channel assignment in wireless networks and classification of minimum graph homomorphism

__
TR06-021
| 10th February 2006
__

Tomas Feder#### Constraint satisfaction: a personal perspective

__
TR06-016
| 1st February 2006
__

Tomas Feder, Carlos Subi#### Partition into $k$-vertex subgraphs of $k$-partite graphs

__
TR06-015
| 1st February 2006
__

Tomas Feder, Carlos Subi#### On Barnette's conjecture

__
TR05-016
| 13th January 2005
__

Tomas Feder, Daniel Ford#### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

__
TR05-005
| 20th December 2004
__

Tomas Feder#### Constraint Satisfaction on Finite Groups with Near Subgroups

Tomas Feder, Carlos Subi

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

Tomas Feder, Carlos Subi

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

Tomas Feder, Carlos Subi

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

Tomas Feder, Phokion G. Kolaitis

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

Tomas Feder, Rajeev Motwani

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

Tomas Feder, Rajeev Motwani, An Zhu

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

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

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

Tomas Feder

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

Tomas Feder, Carlos Subi

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

Tomas Feder, Carlos Subi

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

Tomas Feder, Daniel Ford

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

Tomas Feder

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