Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
124
0
0.0
(
0
)
Added by
Pawe{\\l} Rz\\k{a}\\.zewski
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For graphs $G$ and $H$, we say that $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Already in the early 1980s Alekseev observed that if $H$ is connected, then the textsc{Max Weight Independent Set} problem (MWIS) remains textsc{NP}-hard in $H$-free graphs, unless $H$ is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in $H$-free graphs, where $H$ is any fixed path. If $H$ is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw $H$, MWIS is polynomial-time solvable in $H$-free graphs of bounded degree.
rate research
Read More
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. In this paper, we design several reduction rules and a fast exact algorithm for the maximum weighted independent set problem, and use the measure-and-conquer technique to analyze the running time bound of the algorithm. Our algorithm works on general weighted graphs and it has a good running time bound on sparse graphs. If the graph has an average degree at most 3, our algorithm runs in $O^*(1.1443^n)$ time and polynomial space, improving previous running time bounds for the problem in cubic graphs using polynomial space.
Given a graph $G=(V,E)$ with two distinguished vertices $s,tin V$ and an integer $L$, an {em $L$-bounded flow} is a flow between $s$ and $t$ that can be decomposed into paths of length at most $L$. In the {em maximum $L$-bounded flow problem} the task is to find a maximum $L$-bounded flow between a given pair of vertices in the input graph. The problem can be solved in polynomial time using linear programming. However, as far as we know, no polynomial-time combinatorial algorithm for the $L$-bounded flow is known. The only attempt, that we are aware of, to describe a combinatorial algorithm for the maximum $L$-bounded flow problem was done by Koubek and v{R}i ha in 1981. Unfortunately, their paper contains substantional flaws and the algorithm does not work; in the first part of this paper, we describe these problems. In the second part of this paper we describe a combinatorial algorithm based on the exponential length method that finds a $(1+epsilon)$-approximation of the maximum $L$-bounded flow in time $O(epsilon^{-2}m^2 Llog L)$ where $m$ is the number of edges in the graph. Moreover, we show that this approach works even for the NP-hard generalization of the maximum $L$-bounded flow problem in which each edge has a length.
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density $alpha_c(Delta)$ and provide (i) for $alpha < alpha_c(Delta)$ randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most $alpha n$ in $n$-vertex graphs of maximum degree $Delta$; and (ii) a proof that unless NP=RP, no such algorithms exist for $alpha>alpha_c(Delta)$. The critical density is the occupancy fraction of hard core model on the clique $K_{Delta+1}$ at the uniqueness threshold on the infinite $Delta$-regular tree, giving $alpha_c(Delta)simfrac{e}{1+e}frac{1}{Delta}$ as $Deltatoinfty$.
Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured that (i) $f_G(n,n-1)=n-1$ for all graphs $Ginmathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $tge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $tgefrac{1}{3}n^2+frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2pmod{t}$ for any $1le ile n-1$. We also show that a collection of 2-jump independent $n$-sets $mathcal{F}$ of $C_t$ with $|mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $Ginmathcal{D}(2)$ with $c_e(G)le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.
We study the problem of computing the maximum likelihood estimator (MLE) of multivariate log-concave densities. Our main result is the first computationally efficient algorithm for this problem. In more detail, we give an algorithm that, on input a set of $n$ points in $mathbb{R}^d$ and an accuracy parameter $epsilon>0$, it runs in time $text{poly}(n, d, 1/epsilon)$, and outputs a log-concave density that with high probability maximizes the log-likelihood up to an additive $epsilon$. Our approach relies on a natural convex optimization formulation of the underlying problem that can be efficiently solved by a projected stochastic subgradient method. The main challenge lies in showing that a stochastic subgradient of our objective function can be efficiently approximated. To achieve this, we rely on structural results on approximation of log-concave densities and leverage classical algorithmic tools on volume approximation of convex bodies and uniform sampling from convex sets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
