OASIS
发表于 2025-4-1 03:27:00
The Perfect Matching Cut Problem Revisited,nential Time Hypothesis, we show there is no .-time algorithm for . even when restricted to .-vertex bipartite graphs, and also show that . can be solved in . time by means of an exact branching algorithm.
neolith
发表于 2025-4-1 07:56:41
The Complexity of Gerrymandering over Graphs: Paths and Trees, (that is, worst-case hardness), in particular yield two complexity dichotomies for trees. For instance, the problem is polynomial-time solvable for two parties but becomes weakly NP-hard for three. Moreover, we show that the problem remains NP-hard even when the input graph is a path.
DOTE
发表于 2025-4-1 10:55:35
http://reply.papertrans.cn/39/3881/388038/388038_63.png
morale
发表于 2025-4-1 16:42:30
https://doi.org/10.1007/978-3-319-08714-6ractable algorithms for testing whether the .-elimination distance or .-treewidth of a graph is at most .. Along the way, we also provide such algorithms for all graph classes . defined by a finite set of forbidden induced subgraphs.