Краткое содержание

arXiv:2512.17844v1 Тип объявления: новое Аннотация: Наш первый фокус — это задача о покрытии вершин в гиперграфах с ограниченной емкостью (C-PVC). В C-PVC нам дан гиперграф с емкостями на его вершинах и разбиением множества гиперребер на $\omega$ различные группы. Цель состоит в выборе минимального подмножества вершин, которое удовлетворяет двум основным условиям: (1) общее количество покрытых гиперребер в каждой группе соответствует заданному порогу, и (2) количество гиперребер, назначенных любой вершине, уважает ее ограничение по емкости. Покрытое гиперребро должно быть назначено выбранной вершине, принадлежащей этому гиперребру. Эта формулировка обобщает классическую задачу о покрытии вершин, частичное покрытие вершин и разбиение покрытия вершин. Мы исследуем две основные вариации: мягкое ограниченное (разрешены несколько копий одной вершины) и жесткое ограниченное (каждая вершина может быть выбрана не более одного раза). Пусть $f$ обозначает ранг гиперграфа. Наши основные вклады: $(i)$ алгоритм с гарантией $(f+1)$.