Det minsta s-t skär problemet i grafer är ett av de mest grundläggande problemen i kombinatorisk optimering, och graf skär underliggande algoritmer i diskret matematik, teoretisk datavetenskap, drift forskning och datavetenskap. Medan grafer är en standardmodell för parvisa relationer, ger hypergrafer flexibilitet att modellera multi-way relationer, och är nu en standardmodell för komplexa data och system. Men när man generaliserar från grafer till hypergrafer är begreppet "klippt hyperedge" mindre tydligt, eftersom en hyperedge noder kan delas på flera sätt. Här utvecklar vi en ram för hypergraf nedskärningar genom att överväga problemet med att separera två terminala noder i en hypergraf på ett sätt som minimerar en summa straff vid split hyperedges. I vår uppsättning, olika sätt att dela samma hyperedge har olika straff, och straffet kodas av vad vi kallar en delning funktion. Vårt ramverk öppnar ett rikt utrymme på grundval av hypergraf nedskärningar. Vi identifierar först en naturlig klass av kardinality-baserade hyperedge delning funktioner som endast beror på antalet noder på varje sida av split. I detta fall visar vi att den allmänna hypergraph s-t skär problemet kan reduceras till en dragbar graf s-t skär problem om och endast om delningsfunktionerna är submodulära. Vi identifierar också ett brett system av icke-submodulära delningsfunktioner för vilka problemet är NP-hård. Vi analyserar också förlängningar till multiway nedskärningar med minst tre terminal noder och identifiera en naturlig klass av delning funktioner för vilka problemet kan minskas på ett approximation-bevarande sätt till node-viktade multiway skär problem i grafer, återigen föremål för en submodularitet egenskap. Slutligen redogör vi för flera öppna frågor om allmänna hypergrafnedskärningsproblem.
En mer omfattande översikt över generaliserade hypergraph cut funktioner ingår i det senaste arbetet av en av författarna REF.
Hypergraph Cuts with General Splitting Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}