Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast exact algorithms for some connectivity problems parametrized by clique-width
157
0
0.0
(
0
)
Added by
Benjamin Bergougnoux
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}cdot n$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a $2^{O(k)}cdot n$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(kcdot log(k))}cdot n^{O(1)}$ or worse.
rate research
Read More
Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $max{c^top x colon A x = b,, x in mathbb{Z}^n_{geq 0}}$, where all the entries of $A,b,c$ are integer, parameterized by the number of rows of $A$ and $|A|_{max}$. This class of problems is known under the name of ILP problems in the standard form, adding the word bounded if $x leq u$, for some integer vector $u$. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form $$max{c^top x colon b_l leq A x leq b_r,, x in mathbb{Z}^n},$$ where $b_l$ and $b_r$ are integer vectors. We assume that the integer matrix $A$ has the rank $n$, $(n + m)$ rows, $n$ columns, and parameterize the problem by $m$ and $Delta(A)$, where $Delta(A)$ is the maximum of $n times n$ sub-determinants of $A$, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving $m$ and $Delta(A)$, but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of $m in {0,1}$. By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems.
We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson 09]}, and provides one more example of trade-offs in the supercritical regime above worst case recently identified by [Razborov 16]. We obtain our results by using Razborovs new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom 08].
Seeses conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore a number of known examples of the former category and establish that grids of unbounded size can indeed be interpreted in them.
Butman, Hermelin, Lewenstein, and Rawitz proved that Clique in t-interval graphs is NP-hard for t >= 3. We strengthen this result to show that Clique in 3-track interval graphs is APX-hard.
In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials calF = {P_1,...,P_m} to a new collection calF so that the polynomials in calF are pseudorandom. These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from calF to calF is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection calF. In particular, when the field is of high characteristic, in polynomial time, we can refine calF into calF where every nonzero linear combination of polynomials in calF has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -eta of P, for some eta depending on eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d-1. We give an efficient (randomized) algorithm to find this collection.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
