Extracting densest sub-hypergraph with convex edge-weight functions

DOI10.1007/978-3-031-20350-3_25MaRDI QIDQ6111968zbMATH OpenFDO

Authors

Publication date 4 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.08340

zbMATH Keywords

convex function densest subgraph problem hypergraph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The densest subgraph problem (DSG) aiming at finding an induced subgraph such that the average edge-weights of the subgraph is maximized, is a well-studied problem. However, when the input graph is a hypergraph, the existing notion of DSG fails to capture the fact that a hyperedge partially belonging to an induced sub-hypergraph is also a part of the sub-hypergraph. To resolve the issue, we suggest a function

f_{e} : m a t h b b Z_{g e 0} i g h t a r r o w m a t h b b R_{g e 0}

to represent the partial edge-weight of a hyperedge

e

in the input hypergraph

m a t h c a l H = (V, m a t h c a l E, f)

and formulate a generalized densest sub-hypergraph problem (GDSH) as

m a x_{S s u b s e t e q V} f r a c s u m_{e i n m a t h c a l E} f_{e} (| e c a p S |) | S |

. We demonstrate that, when all the edge-weight functions are non-decreasing convex, GDSH can be solved in polynomial-time by the linear program-based algorithm, the network flow-based algorithm and the greedy

f r a c 1 r

-approximation algorithm where

r

is the rank of the input hypergraph. Finally, we investigate the computational tractability of GDSH where some edge-weight functions are non-convex.

Cites work

This page was built for publication: Extracting densest sub-hypergraph with convex edge-weight functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6111968)