Parameterized Algorithms for Graph Problems and Computational Social Choice.

Abstract: Graph algorithms and computational social choice study the existence and computation of solutions subject to combinatorial constraints. This talk introduces NP-hardness and parameterized complexity, then examines how graph structure, solution size, and the number of agents or voters affect tractability.
We begin with graph problems. In path packing, we find a given number of pairwise vertex-disjoint paths of a fixed length, with endpoints in a terminal set and internal vertices outside that set. For connectivity-preserving paths, we ask a short path between two terminals such that deleting its vertices, or deleting only its edges, leaves a connected graph. In constrained graph partitioning, we delete a bounded number of edges to obtain a fixed number of connected components, each belonging to a chosen graph class. We discuss parameterized algorithms and hardness results for these problems.
Interpreting vertices as indivisible goods extends graph partitioning to allocation among agents with nonnegative additive valuations. Conflict-free allocation requires every bundle to be an independent set, with utility thresholds and possible bounds on bundle size. Connected allocation requires every bundle to induce a connected subgraph, and we maximize either the sum or the minimum of the agents’ utilities. Without graph constraints, we study approximate envy-freeness, proportionality, and maximin-share guarantees under exact-feasibility promises.
Restricting each agent to at most one item gives a bipartite matching representation. For house allocation, we study allocations that are simultaneously envy-free and Pareto optimal. With two item types, such as houses and schools, each agent may receive one item of each type, and fairness defined on the combined bundle. Unfortunately, unlike the single type instance, it turns out to be NP-hard for two types. On the other hand, matchings can also define feasible outcomes for collective choice: each voter reports a preferred matching, and we look for a matching satisfying approval or utility-threshold requirements, with weighted variants incorporating social welfare.