Trichotomous Votes Election with Graph Constraint
Fengbo Wang, Aizhong Zhou, Jianliang Xu · 2023
We study the winner determination problem for the trichotomous votes committee election, which is accompany with a graph. Each vertex in the graph coresponds to a given candidate. The edges between vertices are shown as the relationships between candidates. In this paper, we extend the dichotomous votes to trichotomous votes committee elections with the graph constraints, such as: connection, fixed-size, or complete subgraph. It is trivial that we require the members of the committee to be familiar each other, or formulate a fixed-sized committee. That is, the chosen candidates are forming a complete sub-graph in the given graph, or a fixed-sized subset of vertices. From the viewpoint of classical and parameterized complexity, we find out intractable and tractable results.