Integer Decompositions for Independent Local Quotas on Forests

Let F be a finite forest. At each vertex v, choose a subset S_v of its neighbors and an integer interval [l_v,u_v]. We consider independent sets T for which l_v <= |T intersect S_v| <= u_v whenever v is not in T. Their convex hull is described by vertex bounds, edge inequalities and the perspective inequalities l_v(1-x_v) <= x(S_v) <= u_v(1-x_v). We give a constructive integer decomposition for every integer point in every positive integral dilation. The decomposition uses at most 3|V(F)|-1 distinct admissible sets, with integer multiplicities, and can be computed in time polynomial in the binary input size. The proof combines compressed circular star schedules with integer matching along tree separators. Exact Python diagnostics and source files accompany the manuscript. The ordinary forest-kernel description is a known specialization. This is a complete theorem for the stated forest quota class, not a characterization of kernel polytopes of arbitrary digraphs or closure of the entire AMR-029-0066 source programme. Unrefereed preprint; absolute novelty is not certified. Developed with AI assistance; the author is responsible for the claims.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-24
DOI
https://doi.org/10.5281/zenodo.23609820
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Integer Decompositions for Independent Local Quotas on Forests

Alper Ferudun
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Integer Decompositions for Independent Local Quotas on Forests

Alper Ferudun
preprint en

Abstract

Let F be a finite forest. At each vertex v, choose a subset S_v of its neighbors and an integer interval [l_v,u_v]. We consider independent sets T for which l_v <= |T intersect S_v| <= u_v whenever v is not in T. Their convex hull is described by vertex bounds, edge inequalities and the perspective inequalities l_v(1-x_v) <= x(S_v) <= u_v(1-x_v). We give a constructive integer decomposition for every integer point in every positive integral dilation. The decomposition uses at most 3|V(F)|-1 distinct admissible sets, with integer multiplicities, and can be computed in time polynomial in the binary input size. The proof combines compressed circular star schedules with integer matching along tree separators. Exact Python diagnostics and source files accompany the manuscript. The ordinary forest-kernel description is a known specialization. This is a complete theorem for the stated forest quota class, not a characterization of kernel polytopes of arbitrary digraphs or closure of the entire AMR-029-0066 source programme. Unrefereed preprint; absolute novelty is not certified. Developed with AI assistance; the author is responsible for the claims.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Integer Decompositions for Independent Local Quotas on Forests — Alper Ferudun · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS