Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParameterized Orientable Deletion
119
0
0.0
(
0
)
Added by
Ioannis Katsikarelis
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A graph is $d$-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most $d$. $d$-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph $G=(V,E)$, delete the minimum number of vertices to make $G$ $d$-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and $log n$-inapproximable with respect to $k$, the number of deleted vertices. This closes the gap in the problems approximability. - We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by $d+k$, but W-hard for each of the parameters $d,k$ separately. - We show that, under the SETH, for all $d,epsilon$, the problem does not admit a $(d+2-epsilon)^{tw}$, algorithm where $tw$ is the graphs treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. - We show that the problem is W-hard parameterized by the input graphs clique-width. Complementing this, we provide an algorithm running in time $d^{O(dcdot cw)}$, showing that the problem is FPT by $d+cw$, and improving the previously best known algorithm for this case.
rate research
Read More
Finding cliques in random graphs and the closely related planted clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = Theta(sqrt(n)). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving a lower bound for the problem in the sum-of-squares (or Lasserre) hierarchy, the most powerful class of semi-definite programming algorithms we know of: r rounds of the sum-of-squares hierarchy can only solve the planted clique for t > sqrt(n)/(C log n)^(r^2). Previously, no nontrivial lower bounds were known. Our proof is formulated as a degree lower bound in the Positivstellensatz algebraic proof system, which is equivalent to the sum-of-squares hierarchy. The heart of our (average-case) lower bound is a proof that a certain random matrix derived from the input graph is (with high probability) positive semidefinite. Two ingredients play an important role in this proof. The first is the classical theory of association schemes, applied to the average and variance of that random matrix. The second is a new large deviation inequality for matrix-valued polynomials. Our new tail estimate seems to be of independent interest and may find other applications, as it generalizes both the estimates on real-valued polynomials and on sums of independent random matrices.
We prove super-polynomial lower bounds on the size of linear programming relaxations for approximati
We develop a new framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. The idea is to $textit{edit}$ a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then $textit{lift}$ the solution to apply to the original graph. We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many well-studied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, ($ell$-)Dominating Set, Edge ($ell$-)Dominating Set, and Connected Dominating Set. To enable this framework, we develop new editing algorithms that find the approximately-fewest edits required to bring a given graph into one of several important graph classes (in some cases, also approximating the target parameter of the family). For bounded degeneracy, we obtain a bicriteria $(4,4)$-approximation which also extends to a smoother bicriteria trade-off. For bounded treewidth, we obtain a bicriteria $(O(log^{1.5} n), O(sqrt{log w}))$-approximation, and for bounded pathwidth, we obtain a bicriteria $(O(log^{1.5} n), O(sqrt{log w} cdot log n))$-approximation. For treedepth $2$ (also related to bounded expansion), we obtain a $4$-approximation. We also prove complementary hardness-of-approximation results assuming $mathrm{P} eq mathrm{NP}$: in particular, these problems are all log-factor inapproximable, except the last which is not approximable below some constant factor ($2$ assuming UGC).
Let $G = (V,w)$ be a weighted undirected graph with $m$ edges. The cut dimension of $G$ is the dimension of the span of the characteristic vectors of the minimum cuts of $G$, viewed as vectors in ${0,1}^m$. For every $n ge 2$ we show that the cut dimension of an $n$-vertex graph is at most $2n-3$, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al. cite{GPRW20}, who show that the maximum cut dimension of an $n$-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on $n$-vertex graphs. For every $nge 2$, Graur et al. exhibit a graph on $n$ vertices with cut dimension at least $3n/2 -2$, giving the first lower bound larger than $n$ on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of emph{linear} queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector $x in mathbb{R}^{binom{n}{2}}$ and receives the answer $w^T x$. Our results thus show a lower bound of $2n-3$ on the number of linear queries needed by a deterministic algorithm to solve minimum cut on $n$-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the $ell_1$-approximate cut dimension. The $ell_1$-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on $n=3k+1$ vertices with $ell_1$-approximate cut dimension $2n-2$, showing that it can be strictly larger than the cut dimension.
Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most $k$ vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including {sc Vertex Cover}, {sc Feedback Vertex Set}, {sc Odd Cycle Transveral}, {sc Cluster Vertex Deletion}, and {sc Perfect Deletion}. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is {it fixed-parameter tractable} (FPT) is elusive, it has long been known that if the graph class is characterized by a {it finite} set of forbidden graphs, then the problem is FPT. In this paper, we initiate a study of a natural variation of the problem of deletion to {it scattered graph classes} where we need to delete at most $k$ vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem is fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the finite classes is known to be FPT and the properties that a graph belongs to each of the classes is expressible in CMSO logic. When each graph class has a finite forbidden set, we give a faster FPT algorithm using the well-known techniques of iterative compression and important separators.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
