ﻻ يوجد ملخص باللغة العربية
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.
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 polynom
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
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 dim
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 p