Arrow Research search

Author name cluster

Tomás Feder

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

TCS Journal 2024 Journal Article

List homomorphisms to separable signed graphs

  • Jan Bok
  • Richard Brewster
  • Tomás Feder
  • Pavol Hell
  • Nikola Jedličková

The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [4] and reflexive signed graphs [25]. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic.

Details DOI

MFCS Conference 2020 Conference Paper

List Homomorphism Problems for Signed Graphs

  • Jan Bok
  • Richard C. Brewster
  • Tomás Feder
  • Pavol Hell
  • Nikola Jedlicková

We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G, σ), equipped with lists L(v) ⊆ V(H), v ∈ V(G), of allowed images, to a fixed target signed graph (H, π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v) = V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. Both versions (with lists or without lists) can be formulated as constraint satisfaction problems, and hence enjoy the algebraic dichotomy classification recently verified by Bulatov and Zhuk. By contrast, we seek a combinatorial classification for the list version, akin to the combinatorial classification for the version without lists completed by Brewster and Siggers. We illustrate the possible complications by classifying the complexity of the list homomorphism problem when H is a (reflexive or irreflexive) signed tree. It turns out that the problems are polynomial-time solvable for certain caterpillar-like trees, and are NP-complete otherwise. The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; those classifications are surprisingly complex.

Details

FOCS Conference 2006 Conference Paper

A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks

  • Tomás Feder
  • Adam Guetz
  • Milena Mihail
  • Amin Saberi

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs

Details

TCS Journal 2005 Journal Article

List matrix partitions of chordal graphs

  • Tomás Feder
  • Pavol Hell
  • Sulamita Klein
  • Loana Tito Nogueira
  • Fábio Protti

It is well known that a clique with k + 1 vertices is the only minimal obstruction to k -colourability of chordal graphs. A similar result is known for the existence of a cover by ℓ cliques. Both of these problems are in fact partition problems, restricted to chordal graphs. The first seeks partitions into k independent sets, and the second is equivalent to finding partitions into ℓ cliques. In an earlier paper we proved that a chordal graph can be partitioned into k independent sets and ℓ cliques if and only if it does not contain an induced disjoint union of ℓ + 1 cliques of size k + 1. (A linear time algorithm for finding such partitions can be derived from the proof.) In this paper we expand our focus and consider more general partitions of chordal graphs. For each symmetric matrix M over 0, 1, *, the M -partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix M. Moreover, the vertices of the input chordal graph can be equipped with lists, restricting the parts to which a vertex can be placed. Such (list) partitions generalize (list) colourings and (list) homomorphisms, and arise frequently in the theory of graph perfection. We show that many M -partition problems that are NP-complete in general become solvable in polynomial time for chordal graphs, even in the presence of lists. On the other hand, we show that there are M -partition problems (without lists) that remain NP-complete for chordal graphs. It is not known whether or not each list M -partition problem is NP-complete or polynomial, but it has been shown that each is NP-complete or quasi-polynomial ( n O ( log n ) ). For chordal graphs even this ‘quasi-dichotomy’ is not known, but we do identify large families of matrices M for which dichotomy, or at least quasi-dichotomy, holds. We also discuss forbidden subgraph characterizations of graphs admitting an M -partition. Such characterizations have recently been investigated for partitions of perfect graphs, and we focus on highlighting the improvements one can obtain for the class of chordal, rather than just perfect, graphs.

Details DOI

TCS Journal 2004 Journal Article

Combining request scheduling with web caching

  • Tomás Feder
  • Rajeev Motwani
  • Rina Panigrahy
  • Steve Seiden
  • Rob van Stee
  • An Zhu

We extend the classic paging model by allowing reordering of requests under the constraint that a request is delayed by no longer than a predetermined number of time steps. We first give a dynamic programming algorithm to solve the offline case. Then we give tight bounds on competitive ratios for the online case. For caches of size k, we obtain bounds of k+O(1) for deterministic algorithms and Θ(log k) for randomized algorithms. We also give bounds for the case where either the online or the offline algorithm can reorder the requests, but not both. Finally, we extend our analysis to the case where pages have different sizes.

Details DOI

TCS Journal 2004 Journal Article

Dichotomies for classes of homomorphism problems involving unary functions

  • Tomás Feder
  • Florent Madelaine
  • Iain A. Stewart

We study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. Amongst our results are the following. We establish a dichotomy result for the class of non-uniform constraint satisfaction problems over the signature consisting of one unary function symbol by showing that every such problem is either complete for L, via very restricted logical reductions, or trivial (depending upon whether the template function has a fixed point or not). We show that the class of non-uniform constraint satisfaction problems whose templates are structures over the signature λ 2 consisting of two unary function symbols reflects the full computational significance of the class of non-uniform constraint satisfaction problems over relational structures. We prove a dichotomy result for the class of non-uniform constraint satisfaction problems where the template is a λ 2-structure with the property that the two unary functions involved are the reverse of one another, in that every such problem is either solvable in polynomial-time or NP -complete. Finally, we extend some of our results to the situation where instances of non-uniform constraint satisfaction problems come equipped with lists of elements of the template structure which restrict the set of allowable homomorphisms.

Details DOI

TCS Journal 2001 Journal Article

Fanout limitations on constraint systems

  • Tomás Feder

We examine several families of constraint systems. Constraint satisfaction and network stability are well understood; network stability was introduced in an attempt to understand the role of fanout. We introduce two new families of constraint systems, in a new attempt to limit fanout. These two families are graph constraint satisfaction and bipartite constraint satisfaction. We obtain the following results: (1) an extension of Schaefer's classification argument for boolean satisfiability to boolean graph constraint satisfaction and bipartite constraint satisfaction, (2) a characterization of the graph constraint satisfaction problems that lack fanout in terms of a new problem, the generalized matroid parity problem, which gives rise to many new problems whose complexity is yet to be determined; in particular, the coindependent set problem is shown to be polynomial, and (3) generalized matroid intersection characterizes the lack of fanout in the bipartite case, with a family of matroid intersection problems as a special polynomially solvable subcase.

Details DOI

TCS Journal 2000 Journal Article

A sublinear parallel algorithm for stable matching

  • Tomás Feder
  • Nimrod Megiddo
  • Serge A. Plotkin

A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable matching can be found in O ∗( m ) time by a polynomial number of processors, where m is the total length of preference lists of individuals.

Details DOI

FOCS Conference 1991 Conference Paper

Amortized Communication Complexity (Preliminary Version)

  • Tomás Feder
  • Eyal Kushilevitz
  • Moni Naor

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i. e. the communication complexity of simultaneously computing f on l instances, divided by l is studied. The authors present, both in the deterministic and the randomized model, functions with communication complexity Theta (log n) and amortized communication complexity O(1). They also give a general lower bound on the amortized communication complexity of any function f in terms of its communication complexity C(f). >

Details

FOCS Conference 1989 Conference Paper

Multiparty Communication Complexity

  • Danny Dolev
  • Tomás Feder

A given Boolean function has its input distributed among many parties. The aim is to determine which parties to talk to and what information to exchange with each of them in order to evaluate the function while minimizing the total communication. It is shown that it is possible to obtain the Boolean answer deterministically with only a polynomial increase in communication with respect to the information lower bound given by the nondeterministic communication complexity of the function. >

Details

STOC Conference 1988 Conference Paper

Optimal Algorithms for Approximate Clustering

  • Tomás Feder
  • Daniel H. Greene

In a clustering problem, the aim is to partition a given set of n points in d -dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L 4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size. We show that one cannot approximate the optimal cluster size for a fixed number of clusters within a factor close to 2 in polynomial time, for two or more dimensions, unless P=NP. We also present an algorithm that achieves this factor of 2 in time Ο ( n log k ), and show that this running time is optimal in the algebraic decision tree model. For a fixed cluster size, on the other hand, we give a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1. Our approach is extended to provide approximation algorithms for the restricted centers, suppliers, and weighted suppliers problems that run in optimal Ο ( n log k ) time and achieve optimal or nearly optimal approximation bounds.

Details
v2026.09.13