Source author record

Tomás Feder

Tomás Feder appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO Discrete Mathematics

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak-near-unanimity polymorphism $ϕ$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial time solvable? This gives a proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi [29]. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov [9] and Zhuk [46] in 2017. We have implemented our algorithm and show some experimental results.

preprint2015arXiv

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

We investigate the complexity of generalizations of colourings (acyclic colourings, $(k,\ell)$-colourings, homomorphisms, and matrix partitions), for the class of transitive digraphs. Even though transitive digraphs are nicely structured, many problems are intractable, and their complexity turns out to be difficult to classify. We present some motivational results and several open problems.

preprint2013arXiv

Matrix Partitions of Split Graphs

Matrix partition problems generalize a number of natural graph partition problems, and have been studied for several standard graph classes. We prove that each matrix partition problem has only finitely many minimal obstructions for split graphs. Previously such a result was only known for the class of cographs. (In particular, there are matrix partition problems which have infinitely many minimal chordal obstructions.) We provide (close) upper and lower bounds on the maximum size of a minimal split obstruction. This shows for the first time that some matrices have exponential-sized minimal obstructions of any kind (not necessarily split graphs). We also discuss matrix partitions for bipartite and co-bipartite graphs.

preprint2010arXiv

Dichotomy for tree-structured trigraph list homomorphism problems

Trigraph list homomorphism problems (also known as list matrix partition problems) have generated recent interest, partly because there are concrete problems that are not known to be polynomial time solvable or NP-complete. Thus while digraph list homomorphism problems enjoy dichotomy (each problem is NP-complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems. However, in this paper, we identify a large class of trigraphs for which list homomorphism problems do exhibit a dichotomy. They consist of trigraphs with a tree-like structure, and, in particular, include all trigraphs whose underlying graphs are trees. In fact, we show that for these tree-like trigraphs, the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. We also describe a few examples illustrating that our conditions defining tree-like trigraphs are not unnatural, as relaxing them may lead to harder problems.