Complexity of C-FAS for paths and matchings

Problem 4.4 · arXiv:2402.10782

arXiv Problem high confidence— first stated 2026-01-23

Authors: Pierre Aboulker, Guillaume Aubian, Raul Lopes

Status open high confidence

Problem 4.4 asks whether the C-FAS Problem is tractable when C is the set of all paths or the set of matchings (graphs with maximum degree at most 1), motivated by the NP-completeness established for forests (Theorem 1.1). No follow-up paper resolving either question was found in the indexed literature as of May 2026. The problem remains open for both cases.

Reviewer notes. No follow-up found. The C-FAS Problem for C = paths and C = matchings (max degree 1) is posed as an open problem in the paper following the NP-completeness proof for forests. The paper (v3, January 2026) is recent; absence of follow-up in the indexed literature suggests the problem remains open. Pierre Aboulker's DBLP page lists no subsequent paper on this topic.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. What is the complexity of the $\mathcal{C}$-FAS Problem when $\mathcal{C}$ is the set of all paths? when $\mathcal{C}$ is the set of graphs with maximum degree $1$?

Context

Following the NP-completeness of the $\mathcal{C}$-FAS Problem for forests (Theorem 1.1), it is natural to ask for which classes $\mathcal{C}$ the problem is in P. Paths and matchings (graphs with maximum degree at most 1) are two natural candidates for tractable cases.

Source paper

Finding forest-orderings of tournaments is NP-complete
Pierre Aboulker, Guillaume Aubian, Raul Lopes · 2026-01-23
https://arxiv.org/abs/2402.10782