Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulticritera Cuts and Size-Constrained $k$-cuts in Hypergraphs
73
0
0.0
(
0
)
Added by
Calvin Beideman
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We address counting and optimization variants of multicriteria global min-cut and size-constrained min-$k$-cut in hypergraphs. 1. For an $r$-rank $n$-vertex hypergraph endowed with $t$ hyperedge-cost functions, we show that the number of multiobjective min-cuts is $O(r2^{tr}n^{3t-1})$. In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi, Mahjoub, McCormick, and Queyranne (Math Programming, 2015). In addition, we give randomized algorithms to enumerate all multiobjective min-cuts and all pareto-optimal cuts in strongly polynomial-time. 2. We also address node-budgeted multiobjective min-cuts: For an $n$-vertex hypergraph endowed with $t$ vertex-weight functions, we show that the number of node-budgeted multiobjective min-cuts is $O(r2^{r}n^{t+2})$, where $r$ is the rank of the hypergraph, and the number of node-budgeted $b$-multiobjective min-cuts for a fixed budget-vector $b$ is $O(n^2)$. 3. We show that min-$k$-cut in hypergraphs subject to constant lower bounds on part sizes is solvable in polynomial-time for constant $k$, thus resolving an open problem posed by Queyranne. Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger (SODA, 1993). Our techniques illustrate the versatility of the random contraction approach to address counting and algorithmic problems concerning multiobjective min-cuts and size-constrained $k$-cuts in hypergraphs.
rate research
Read More
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on $n$ vertices up to a $1+epsilon$ error must use $Omega(nlog n/epsilon^2)$ bits of space in the worst case, improving the $Omega(n/epsilon^2)$ bound of Andoni et al. and matching the best known upper bound achieved by spectral sparsifiers. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two $d-$regular graphs which approximate each others cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.
Cut problems form one of the most fundamental classes of problems in algorithmic graph theory. For instance, the minimum cut, the minimum $s$-$t$ cut, the minimum multiway cut, and the minimum $k$-way cut are some of the commonly encountered cut problems. Many of these problems have been extensively studied over several decades. In this paper, we initiate the algorithmic study of some cut problems in high dimensions. The first problem we study, namely, Topological Hitting Set (THS), is defined as follows: Given a nontrivial $r$-cycle $zeta$ in a simplicial complex $mathsf{K}$, find a set $mathcal{S}$ of $r$-dimensional simplices of minimum cardinality so that $mathcal{S}$ meets every cycle homologous to $zeta$. Our main result is that this problem admits a polynomial-time solution on triangulations of closed surfaces. Interestingly, the optimal solution is given in terms of the cocycles of the surface. For general complexes, we show that THS is W[1]-hard with respect to the solution size $k$. On the positive side, we show that THS admits an FPT algorithm with respect to $k+d$, where $d$ is the maximum degree of the Hasse graph of the complex $mathsf{K}$. We also define a problem called Boundary Nontrivialization (BNT): Given a bounding $r$-cycle $zeta$ in a simplicial complex $mathsf{K}$, find a set $mathcal{S}$ of $(r+1)$-dimensional simplices of minimum cardinality so that the removal of $mathcal{S}$ from $mathsf{K}$ makes $zeta$ non-bounding. We show that BNT is W[1]-hard with respect to the solution size as the parameter, and has an $O(log n)$-approximation FPT algorithm for $(r+1)$-dimensional complexes with the $(r+1)$-th Betti number $beta_{r+1}$ as the parameter. Finally, we provide randomized (approximation) FPT algorithms for the global variants of THS and BNT.
We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By viewing flows and cuts topologically in terms of the simplicial (co)boundary operator we can state these problems as linear programs and show that they are dual to one another. Unlike graphs, complexes with integral capacity constraints may have fractional max-flows. We show that computing a maximum integral flow is NP-hard. Moreover, we give a combinatorial definition of a simplicial cut that seems more natural in the context of optimization problems and show that computing such a cut is NP-hard. However, we provide conditions on the simplicial complex for when the cut found by the linear program is a combinatorial cut. For $d$-dimensional simplicial complexes embedded into $mathbb{R}^{d+1}$ we provide algorithms operating on the dual graph: computing a maximum flow is dual to computing a shortest path and computing a minimum cut is dual to computing a minimum cost circulation. Finally, we investigate the Ford-Fulkerson algorithm on simplicial complexes, prove its correctness, and provide a heuristic which guarantees it to halt.
Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K subset V$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U, K-U $ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^{k}}$ for every graph with $k$ terminals. The best known lower bound on the size of a mimicking network is linear in the number of terminals. More precisely, the best known lower bound is $k+1$ for graphs with $k$ terminals (Chaudhuri et al. 2000). In this work, we improve both the upper and lower bounds reducing the doubly-exponential gap between them to a single-exponential gap. Specifically, we obtain the following upper and lower bounds on mimicking networks: 1) Given a graph $G$, we exhibit a construction of mimicking network with at most $(|K|-1)$th Dedekind number ($approx 2^{{(k-1)} choose {lfloor {{(k-1)}/2} rfloor}}$) of vertices (independent of size of $V$). Furthermore, we show that the construction is optimal among all {it restricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. 2) There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{frac{k-1}{2}}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.
We consider the genus-one curves which arise in the cuts of the sunrise and in the elliptic double-box Feynman integrals. We compute and compare invariants of these curves in a number of ways, including Feynman parametrization, lightcone and Baikov (in full and loop-by-loop variants). We find that the same geometry for the genus-one curves arises in all cases, which lends support to the idea that there exists an invariant notion of genus-one geometry, independent on the way it is computed. We further indicate how to interpret some previous results which found that these curves are related by isogenies instead.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
