Search

We consider the problem of matching people to jobs, where each person ranks a subset of jobs in an order of preference, possibly involving ties. There are several notions of optimality about how to best match each person to a job; in particular, popularity is a natural and appealing notion of optimality. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph $G = ({\mathcal{A}}\cup{\mathcal{J}},E)$ where ${\mathcal{A}}$ is the set of people and ${\mathcal{J}}$ is the set of jobs, and a list $\langle c_1,\ldots,c_{|{\mathcal{J}}|}\rangle$ denoting upper bounds on the capacities of each job, does there exist $(x_1,\ldots,x_{|{\mathcal{J}}|})$ such that setting the capacity of i-th job to x i , where 1 ≤ x i ≤ c i , for each i, enables the resulting graph to admit a popular matching. In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c i is 1 or 2.

The max-coloring problem is to compute a legal coloring of the vertices of a graph G=(V,E) with vertex weights w such that $\sum_{i=1}^{k}\max_{v\in C_{i}}w(v_{i})$ is minimized, where C 1,?,C k are the various color classes. For general graphs, max-coloring is as hard as the classical vertex coloring problem, a special case of the former where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring skinny trees, a broad class of trees that includes paths and spiders. For these graphs, we show that max-coloring can be solved in time O(|V|+time for sorting the vertex weights). When vertex weights are real numbers, we show a matching lower bound of ?(|V|log?|V|) in the algebraic computation tree model.