BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Marek Cygan

Marek Cygan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityDiscrete MathematicsArtificial IntelligenceMachine Learningmath.COComputer Science and Game TheoryComputer VisionMultiagent Systems

Catalog footprint

What is connected

46works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

46 published item(s)

preprint2022arXiv

n-CPS: Generalising Cross Pseudo Supervision to n Networks for Semi-Supervised Semantic Segmentation

We present n-CPS - a generalisation of the recent state-of-the-art cross pseudo supervision (CPS) approach for the task of semi-supervised semantic segmentation. In n-CPS, there are n simultaneously trained subnetworks that learn from each other through one-hot encoding perturbation and consistency regularisation. We also show that ensembling techniques applied to subnetworks outputs can significantly improve the performance. To the best of our knowledge, n-CPS paired with CutMix outperforms CPS and sets the new state-of-the-art for Pascal VOC 2012 with (1/16, 1/8, 1/4, and 1/2 supervised regimes) and Cityscapes (1/16 supervised).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

One Simple Trick to Fix Your Bayesian Neural Network

One of the most popular estimation methods in Bayesian neural networks (BNN) is mean-field variational inference (MFVI). In this work, we show that neural networks with ReLU activation function induce posteriors, that are hard to fit with MFVI. We provide a theoretical justification for this phenomenon, study it empirically, and report the results of a series of experiments to investigate the effect of activation function on the calibration of BNNs. We find that using Leaky ReLU activations leads to more Gaussian-like weight posteriors and achieves a lower expected calibration error (ECE) than its ReLU-based counterpart.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

We show that Set Cover on instances with $N$ elements cannot be approximated within $(1-γ)\ln N$-factor in time exp($N^{γ-δ})$, for any $0 < γ< 1$ and any $δ> 0$, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan et al.\ (IPL, 2009) of $(1-γ)\ln N$-factor in time $exp(O(N^γ))$. The lower bound is obtained by extracting a standalone reduction from Label Cover to Set Cover from the work of Moshkovitz (Theory of Computing, 2015), and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set Cover. We give a $(1-γ)\ln N$-approximation algorithm for these problems that runs in $exp(\tilde{O}(N^γ))$ time, for any $1/2 \le γ< 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximation and Parameterized Complexity of Minimax Approval Voting

We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance $d$ from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time $\mathcal{O}^\star(2^{o(d\log d)})$, unless the Exponential Time Hypothesis (ETH) fails. This means that the $\mathcal{O}^\star(d^{2d})$ algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time $\mathcal{O}^\star(\left({3}/ε\right)^{2d})$, which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time $n^{\mathcal{O}(1/ε^2 \cdot \log(1/ε))} \cdot \mathrm{poly}(m)$, almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Designing FPT algorithms for cut problems using randomized contractions

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for the Unique Label Cover problem and new FPT algorithms with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. More precisely, we show the following: - We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2^{O(k^2\log |Σ|)}n^4\log n deterministic time (even in the stronger, vertex-deletion variant) where k is the number of unsatisfied edges and |Σ| is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by O(\sqrt{\log n}) to optimality, which improves over the trivial O(1) upper bound. - We prove that the Steiner Cut problem can be solved in 2^{O(k^2\log k)}n^4\log n deterministic time and \tilde{O}(2^{O(k^2\log k)}n^2) randomized time where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup (FOCS'11). - We show how to combine considering `cut' and `uncut' constraints at the same time. More precisely, we define a robust problem Node Multiway Cut-Uncut that can serve as an abstraction of introducing uncut constraints, and show that it admits an algorithm running in 2^{O(k^2\log k)}n^4\log n deterministic time where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our technique is that, unlike important separators, it can handle real weights.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tight Lower Bounds on Graph Embedding Problems

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph $G$ to graph $H$ cannot be done in time $|V(H)|^{o(|V(G)|)}$. We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of $|V(H)|^{o(|V(H)|)}$-time algorithm deciding if graph $G$ is a subgraph of $H$. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Algorithmic Complexity of Power Law Networks

It was experimentally observed that the majority of real-world networks follow power law degree distribution. The aim of this paper is to study the algorithmic complexity of such "typical" networks. The contribution of this work is twofold. First, we define a deterministic condition for checking whether a graph has a power law degree distribution and experimentally validate it on real-world networks. This definition allows us to derive interesting properties of power law networks. We observe that for exponents of the degree distribution in the range $[1,2]$ such networks exhibit double power law phenomenon that was observed for several real-world networks. Our observation indicates that this phenomenon could be explained by just pure graph theoretical properties. The second aim of our work is to give a novel theoretical explanation why many algorithms run faster on real-world data than what is predicted by algorithmic worst-case analysis. We show how to exploit the power law degree distribution to design faster algorithms for a number of classical P-time problems including transitive closure, maximum matching, determinant, PageRank and matrix inverse. Moreover, we deal with the problems of counting triangles and finding maximum clique. Previously, it has been only shown that these problems can be solved very efficiently on power law graphs when these graphs are random, e.g., drawn at random from some distribution. However, it is unclear how to relate such a theoretical analysis to real-world graphs, which are fixed. Instead of that, we show that the randomness assumption can be replaced with a simple condition on the degrees of adjacent vertices, which can be used to obtain similar results. As a result, in some range of power law exponents, we are able to solve the maximum clique problem in polynomial time, although in general power law networks the problem is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Kernelization lower bound for Permutation Pattern Matching

A permutation $π$ contains a permutation $σ$ as a pattern if it contains a subsequence of length $|σ|$ whose elements are in the same relative order as in the permutation $σ$. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption $\mbox{NP} \not\subseteq \mbox{co-NP}/\mbox{poly}$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds for approximation schemes for Closest String

In the Closest String problem one is given a family $\mathcal S$ of equal-length strings over some fixed alphabet, and the task is to find a string $y$ that minimizes the maximum Hamming distance between $y$ and a string from $\mathcal S$. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [Li et al., J. ACM'02], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS for Closest String is in fact unlikely, as it would imply that $\mathrm{FPT}=\mathrm{W}[1]$, a highly unexpected collapse in the hierarchy of parameterized complexity classes. Our proof also shows that the existence of a PTAS for Closest String with running time $f(\varepsilon)\cdot n^{o(1/\varepsilon)}$, for any computable function $f$, would contradict the Exponential Time Hypothesis.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection. To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangement problem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Polynomial kernelization for removing induced claws and diamonds

A graph is called (claw,diamond)-free if it contains neither a claw (a $K_{1,3}$) nor a diamond (a $K_4$ with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-free graphs can be characterized as line graphs of triangle-free graphs, or as linear dominoes, i.e., graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique. In this paper we consider the parameterized complexity of the (claw,diamond)-free Edge Deletion problem, where given a graph $G$ and a parameter $k$, the question is whether one can remove at most $k$ edges from $G$ to obtain a (claw,diamond)-free graph. Our main result is that this problem admits a polynomial kernel. We complement this finding by proving that, even on instances with maximum degree $6$, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{O(1)}$ unless the Exponential Time Hypothesis fail

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Hardness of Subgraph Isomorphism

Subgraph Isomorphism is a very basic graph problem, where given two graphs $G$ and $H$ one is to check whether $G$ is a subgraph of $H$. Despite its simple definition, the Subgraph Isomorphism problem turns out to be very broad, as it generalizes problems such as Clique, $r$-Coloring, Hamiltonicity, Set Packing and Bandwidth. However, for all of the mentioned problems $2^{\mathcal{O}(n)}$ time algorithms exist, so a natural and frequently asked question in the past was whether there exists a $2^{\mathcal{O}(n)}$ time algorithm for Subgraph Isomorphism. In the monograph of Fomin and Kratsch [Springer'10] this question is highlighted as an open problem, among few others. Our main result is a reduction from 3-SAT, producing a subexponential number of sublinear instances of the Subgraph Isomorphism problem. In particular, our reduction implies a $2^{Ω(n \sqrt{\log n})}$ lower bound for Subgraph Isomorphism under the Exponential Time Hypothesis. This shows that there exist classes of graphs that are strictly harder to embed than cliques or Hamiltonian cycles. The core of our reduction consists of two steps. First, we preprocess and pack variables and clauses of a 3-SAT formula into groups of logarithmic size. However, the grouping is not arbitrary, since as a result we obtain only a limited interaction between the groups. In the second step, we overcome the technical hardness of encoding evaluations as permutations by a simple, yet fruitful scheme of guessing the sizes of preimages of an arbitrary mapping, reducing the case of arbitrary mapping to bijections. In fact, when applying this step to a recent independent result of Fomin et al.[arXiv:1502.05447 (2015)], who showed hardness of Graph Homomorphism, we can transfer their hardness result to Subgraph Isomorphism, implying a nearly tight lower bound of $2^{Ω(n \log n / \log \log n)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximating Upper Degree-Constrained Partial Orientations

In the Upper Degree-Constrained Partial Orientation problem we are given an undirected graph $G=(V,E)$, together with two degree constraint functions $d^-,d^+ : V \to \mathbb{N}$. The goal is to orient as many edges as possible, in such a way that for each vertex $v \in V$ the number of arcs entering $v$ is at most $d^-(v)$, whereas the number of arcs leaving $v$ is at most $d^+(v)$. This problem was introduced by Gabow [SODA'06], who proved it to be MAXSNP-hard (and thus APX-hard). In the same paper Gabow presented an LP-based iterative rounding $4/3$-approximation algorithm. Since the problem in question is a special case of the classic 3-Dimensional Matching, which in turn is a special case of the $k$-Set Packing problem, it is reasonable to ask whether recent improvements in approximation algorithms for the latter two problems [Cygan, FOCS'13; Sviridenko & Ward, ICALP'13] allow for an improved approximation for Upper Degree-Constrained Partial Orientation. We follow this line of reasoning and present a polynomial-time local search algorithm with approximation ratio $5/4+\varepsilon$. Our algorithm uses a combination of two types of rules: improving sets of bounded pathwidth from the recent $4/3+\varepsilon$-approximation algorithm for 3-Set Packing [Cygan, FOCS'13], and a simple rule tailor-made for the setting of partial orientations. In particular, we exploit the fact that one can check in polynomial time whether it is possible to orient all the edges of a given graph [Gyárfás & Frank, Combinatorics'76].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Constant Factor Approximation for Capacitated k-Center with Outliers

The $k$-center problem is a classic facility location problem, where given an edge-weighted graph $G = (V,E)$ one is to find a subset of $k$ vertices $S$, such that each vertex in $V$ is "close" to some vertex in $S$. The approximation status of this basic problem is well understood, as a simple 2-approximation algorithm is known to be tight. Consequently different extensions were studied. In the capacitated version of the problem each vertex is assigned a capacity, which is a strict upper bound on the number of clients a facility can serve, when located at this vertex. A constant factor approximation for the capacitated $k$-center was obtained last year by Cygan, Hajiaghayi and Khuller [FOCS'12], which was recently improved to a 9-approximation by An, Bhaskara and Svensson [arXiv'13]. In a different generalization of the problem some clients (denoted as outliers) may be disregarded. Here we are additionally given an integer $p$ and the goal is to serve exactly $p$ clients, which the algorithm is free to choose. In 2001 Charikar et al. [SODA'01] presented a 3-approximation for the $k$-center problem with outliers. In this paper we consider a common generalization of the two extensions previously studied separately, i.e. we work with the capacitated $k$-center with outliers. We present the first constant factor approximation algorithm with approximation ratio of 25 even for the case of non-uniform hard capacities.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable

Given a graph $G$ and an integer $k$, the Feedback Vertex Set (FVS) problem asks if there is a vertex set $T$ of size at most $k$ that hits all cycles in the graph. The fixed-parameter tractability status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08) showed that it is FPT by giving a $4^{k}k!n^{O(1)}$ time algorithm. In the subset versions of this problems, we are given an additional subset $S$ of vertices (resp., edges) and we want to hit all cycles passing through a vertex of $S$ (resp. an edge of $S$). Recently, the Subset Feedback Vertex Set in undirected graphs was shown to be FPT by Cygan et al. (ICALP '11) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that Subset Feedback Vertex Set in directed graphs can be solved in time $2^{O(k^3)}n^{O(1)}$. By our result, we complete the picture for feedback vertex set problems and their subset versions in undirected and directed graphs. Besides proving the fixed-parameter tractability of Directed Subset Feedback Vertex Set, we reformulate the random sampling of important separators technique in an abstract way that can be used for a general family of transversal problems. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from $2^{2^{O(k)}}$ to $2^{O(k^2)}$ in the parameter dependence of the Directed Multiway Cut algorithm of Chitnis et al. (SODA '12).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hitting forbidden subgraphs in graphs of bounded treewidth

We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph $H$ and an input graph $G$, the task is to find a set $X \subseteq V(G)$ of minimum size that hits all subgraphs of $G$ isomorphic to $H$. In the colorful variant of the problem, each vertex of $G$ is precolored with some color from $V(H)$ and we require to hit only $H$-subgraphs with matching colors. Standard techniques shows that for every fixed $H$, the problem is fixed-parameter tractable parameterized by the treewidth of $G$; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of $G$ is tightly governed by $μ(H)$, the maximum size of a minimal vertex separator in $H$. That is, we show for every fixed $H$ that, on a graph of treewidth $t$, the colorful problem can be solved in time $2^{\mathcal{O}(t^{μ(H)})}\cdot|V(G)|$, but cannot be solved in time $2^{o(t^{μ(H)})}\cdot |V(G)|^{O(1)}$, assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H-Subgraph Hitting is much richer.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Minimum Bisection is fixed parameter tractable

In the classic Minimum Bisection problem we are given as input a graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $O(2^{O(k^{3})}n^3 \log^3 n)$. This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most $k$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fast branching algorithm for Cluster Vertex Deletion

In the family of clustering problems, we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hueffner et al. [Theory Comput. Syst. 2010] initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant O(2^k * k^9 + n * m)-time fixed-parameter algorithm, parameterized by the solution size. In our work, we pick up this line of research and present an O(1.9102^k * (n + m))-time branching algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Faster exponential-time algorithms in graphs of bounded average degree

We first show that the Traveling Salesman Problem in an n-vertex graph with average degree bounded by d can be solved in O*(2^{(1-\eps_d)n}) time and exponential space for a constant \eps_d depending only on d, where the O*-notation suppresses factors polynomial in the input size. Thus, we generalize the recent results of Bjorklund et al. [TALG 2012] on graphs of bounded degree. Then, we move to the problem of counting perfect matchings in a graph. We first present a simple algorithm for counting perfect matchings in an n-vertex graph in O*(2^{n/2}) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Bjorklund [SODA 2012], but relies on inclusion-exclusion principle instead of algebraic transformations. Building upon this result, we show that the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in O*(2^{(1-\eps_{2d})n/2}) time and exponential space, where \eps_{2d} is the constant obtained by us for the Traveling Salesman Problem in graphs of average degree at most 2d. Moreover we obtain a simple algorithm that counts the number of perfect matchings in an n-vertex bipartite graph of average degree at most d in O*(2^{(1-1/(3.55d))n/2}) time, improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved approximation for 3-dimensional matching via bounded pathwidth local search

One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-Set Packing is the well known 3-Dimensional Matching problem. Both problems belong to the Karp`s list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-Set Packing is (k + eps)/2 and goes back to the work of Hurkens and Schrijver [SIDMA`89], which gives (1.5 + eps)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of the paper is a new approach to local search for k-Set Packing where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c^r poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k + 1 + eps)/3-approximation algorithm, improving the best known approximation ratio for k-Set Packing. In particular we improve the approximation ratio for 3-Dimensional Matching from 3/2 + eps to 4/3 + eps.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Pairwise Spanners

Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ in $G$, then they are at distance at most $f(d)$ in $H$. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the $u$-$v$ distance only for pairs $(u,v)$ in a given set $\cP \subseteq V\times V$. Such $\cP$-spanners were studied before [Coppersmith,Elkin'05] only in the special case that $f(\cdot)$ is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same $\cP$) and of the best known spanners (with the same $f(\cdot)$). In more detail, for arbitrary $\cP$, we show that there exists a $\mathcal{P}$-spanner of size $O(n(|\cP|\log n)^{1/4})$ with $f(d)=d+4\log n$. Alternatively, for any $\eps>0$, there exists a $\cP$-spanner of size $O(n|\cP|^{1/4}\sqrt{\frac{\log n}{\eps}})$ with $f(d)=(1+\eps)d+4$. We also consider the relevant special case that there is a critical set of nodes $S\subseteq V$, and we wish to approximate either the distances within nodes in $S$ or from nodes in $S$ to any other node. We show that there exists an $(S\times S)$-spanner of size $O(n\sqrt{|S|})$ with $f(d)=d+2$, and an $(S\times V)$-spanner of size $O(n\sqrt{|S|\log n})$ with $f(d)=d+2\log n$. All the mentioned pairwise spanners can be constructed in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable

Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time n^{O(k)}. We give an algorithm with running time 2^{2^{O(k^2)}} n^{O(1)} for the problem, that is, we show the fixed-parameter tractability of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

In this paper we consider kernelization for problems on d-degenerate graphs, i.e. graphs such that any subgraph contains a vertex of degree at most $d$. This graph class generalizes many classes of graphs for which effective kernelization is known to exist, e.g. planar graphs, H-minor free graphs, and H-topological-minor free graphs. We show that for several natural problems on d-degenerate graphs the best known kernelization upper bounds are essentially tight.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this paper, we introduce a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the usage of Baur-Strassen's theorem and of Strojohann's determinant algorithm. It allows us to give new and simple solutions to the following problems: * Finding Shortest Cycles -- We give a simple \tilde{O}(Wn^ω) time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with non-negative weights) this matches the time bounds obtained in 2011 by Roditty and Vassilevska-Williams. On the other hand, no algorithm working in \tilde{O}(Wn^ω) time was previously known for undirected graphs with negative weights. Furthermore our algorithm for a given directed or undirected graph detects whether it contains a negative weight cycle within the same running time. * Computing Diameter and Radius -- We give a simple \tilde{O}(Wn^ω) time algorithm for computing a diameter and radius of an undirected or directed graphs. To the best of our knowledge no algorithm with this running time was known for undirected graphs with negative weights. * Finding Minimum Weight Perfect Matchings -- We present an \tilde{O}(Wn^ω) time algorithm for finding minimum weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski in 2006, who presented such an algorithm but only in the case of bipartite graphs. In order to solve minimum weight perfect matching problem we develop a novel combinatorial interpretation of the dual solution which sheds new light on this problem. Such a combinatorial interpretation was not know previously, and is of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Deterministic parameterized connected vertex cover

In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contains at least one end-point of each edge and moreover X induces a connected subgraph. For this problem we present a deterministic algorithm running in O(2^k n^O(1)) time and polynomial space, improving over previously best O(2.4882^k n^O(1)) deterministic algorithm and O(2^k n^O(1)) randomized algorithm. Furthermore, when usage of exponential space is allowed, we present an O(2^k k(n+m)) time algorithm that solves a more general variant with arbitrary real weights. Finally, we show that in O(2k k(n + m)) time and O(2^k k) space one can count the number of connected vertex covers of size at most k, which can not be improved to O((2 - eps)^k nO(1)) for any eps > 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC'12].

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fast Hamiltonicity checking via bases of perfect matchings

For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H_t: We first show that H_t has rank at most 2^{t/2-1} over GF(2) via an appropriate factorization that explicitly provides families of matchings X_t forming bases for H_t. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X_t induce permutation matrices within H_t. Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that for every ε>0 this cannot be improved to (2+\sqrt{2}-ε)^{pw}n^{O(1)} time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of a (2-ε)^n time algorithm for CNF-Sat.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Known algorithms for EDGE CLIQUE COVER are probably optimal

In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on k-element universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2^k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent ECC instance (G,k) with k = O(log n) and |V(G)| = O(n + m). Consequently, there is no 2^{2^{o(k)}}poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. To the best of our knowledge, these are the first results for a natural, fixed-parameter tractable problem, and proving that a doubly-exponential dependency on the parameter is essentially necessary.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

LP Rounding for k-Centers with Non-uniform Hard Capacities

In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, so that we respect the capacity constraints on centers. The objective is to minimize the maximum distance a node has to travel to get to its assigned center. This problem is NP-hard, even when centers have no capacity restrictions and optimal factor 2 approximation algorithms are known. With capacities, when all centers have identical capacities, a 6 approximation is known with no better lower bounds than for the infinite capacity version. While many generalizations and variations of this problem have been studied extensively, no progress was made on the capacitated version for a general capacity function. We develop the first constant factor approximation algorithm for this problem. Our algorithm uses an LP rounding approach to solve this problem, and works for the case of non-uniform hard capacities, when multiple copies of a node may not be chosen and can be extended to the case when there is a hard bound on the number of copies of a node that may be selected. In addition we establish a lower bound on the integrality gap of 7(5) for non-uniform (uniform) hard capacities. In addition we prove that if there is a (3-eps)-factor approximation for this problem then P=NP. Finally, for non-uniform soft capacities we present a much simpler 11-approximation algorithm, which we find as one more evidence that hard capacities are much harder to deal with.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On fixed-parameter algorithms for Split Vertex Deletion

In the Split Vertex Deletion problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study fixed-parameter algorithms for Split Vertex Deletion parameterized by k: we show that, up to a factor quasipolynomial in k and polynomial in n, the Split Vertex Deletion problem can be solved in the same time as the well-studied Vertex Cover problem. Plugging the currently best fixed-parameter algorithm for Vertex Cover due to Chen et al. [TCS 2010], we obtain an algorithm that solves Split Vertex Deletion in time O(1.2738^k * k^O(log k) + n^O(1)). To achieve our goal, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n^O(log n) containing partitions of V(G) into two parts, such for any two disjoint subsets X_C, X_I of V(G) where G[X_C] is a clique and G[X_I] is an independent set, there is a partition in P which contains all vertices of X_C on one side and all vertices of X_I on the other.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Scheduling partially ordered jobs faster than 2^n

In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sitting closer to friends than enemies, revisited

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space R^l in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into R^1 can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this particular case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve the traveling salesman problem or count the number of Hamiltonian cycles. The rank-based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the matrix tree theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Steiner Forest Orientation Problems

We consider connectivity problems with orientation constraints. Given a directed graph $D$ and a collection of ordered node pairs $P$ let $P[D]=\{(u,v) \in P: D {contains a} uv{-path}}$. In the {\sf Steiner Forest Orientation} problem we are given an undirected graph $G=(V,E)$ with edge-costs and a set $P \subseteq V \times V$ of ordered node pairs. The goal is to find a minimum-cost subgraph $H$ of $G$ and an orientation $D$ of $H$ such that $P[D]=P$. We give a 4-approximation algorithm for this problem. In the {\sf Maximum Pairs Orientation} problem we are given a graph $G$ and a multi-collection of ordered node pairs $P$ on $V$. The goal is to find an orientation $D$ of $G$ such that $|P[D]|$ is maximum. Generalizing the result of Arkin and Hassin [DAM'02] for $|P|=2$, we will show that for a mixed graph $G$ (that may have both directed and undirected edges), one can decide in $n^{O(|P|)}$ time whether $G$ has an orientation $D$ with $P[D]=P$ (for undirected graphs this problem admits a polynomial time algorithm for any $P$, but it is NP-complete on mixed graphs). For undirected graphs, we will show that one can decide whether $G$ admits an orientation $D$ with $|P[D]| \geq k$ in $O(n+m)+2^{O(k\cdot \log \log k)}$ time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [AMB'11]. We also show that {\sf Maximum Pairs Orientation} admits ratio $O(\log |P|/\log\log |P|)$, which is better than the ratio $O(\log n/\log\log n)$ of Gamzu et al. [WABI'10] when $|P|<n$. Finally, we show that the following node-connectivity problem can be solved in polynomial time: given a graph $G=(V,E)$ with edge-costs, $s,t \in V$, and an integer $\ell$, find a min-cost subgraph $H$ of $G$ with an orientation $D$ such that $D$ contains $\ell$ internally-disjoint $st$-paths, and $\ell$ internally-disjoint $ts$-paths.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximation Algorithms for Union and Intersection Covering Problems

In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an edge-weighted graph. Here nodes and edges represent requests and items, respectively. In this paper, we initiate the study of a new family of multi-layer covering problems. Each such problem consists of a collection of h distinct instances of a standard covering problem (layers), with the constraint that all layers share the same set of requests. We identify two main subfamilies of these problems: - in a union multi-layer problem, a request is satisfied if it is satisfied in at least one layer; - in an intersection multi-layer problem, a request is satisfied if it is satisfied in all layers. To see some natural applications, consider both generalizations of k-MST. Union k-MST can model a problem where we are asked to connect a set of users to at least one of two communication networks, e.g., a wireless and a wired network. On the other hand, intersection k-MST can formalize the problem of connecting a subset of users to both electricity and water. We present a number of hardness and approximation results for union and intersection versions of several standard optimization problems: MST, Steiner tree, set cover, facility location, TSP, and their partial covering variants.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Channel Assignment via Fast Zeta Transform

We show an O*((l+1)^n)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)-time algorithm by Kral, as well as algorithms for important special cases, like L(2,1)-labelling. For the latter problem, our algorithm works in O*(3^n) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Clique cover and graph separation: New incompressibility results

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. Although a framework for proving kernelization lower bounds has been discovered in 2008 and successfully applied multiple times over the last three years, establishing kernelization complexity of many important problems remains open. In this paper we show that, unless NP is a subset of coNP/poly and the polynomial hierarchy collapses up to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter: - EDGE CLIQUE COVER, parameterized by the number of cliques, - DIRECTED EDGE/VERTEX MULTIWAY CUT, parameterized by the size of the cutset, even in the case of two terminals, - EDGE/VERTEX MULTICUT, parameterized by the size of the cutset, and - k-WAY CUT, parameterized by the size of the cutset. The existence of a polynomial kernelization for EDGE CLIQUE COVER was a seasoned veteran in open problem sessions. Furthermore, our results complement very recent developments in designing parameterized algorithms for cut problems by Marx and Razgon [STOC'11], Bousquet et al. [STOC'11], Kawarabayashi and Thorup [FOCS'11] and Chitnis et al. [SODA'12].

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Dominating Set is Fixed Parameter Tractable in Claw-free Graphs

We show that the dominating set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K(1,3)), the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k^2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of dominating set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of dominating set is the class of K(i,j)-free graphs, which exclude, for some fixed i,j, the complete bipartite graph K(i,j) as a subgraph. For i,i >= 2, the class of claw-free graphs and any class of K(i,j)-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of dominating set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the dominating set problem hard. More precisely, we show that for any t ?>= 4, the dominating set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K(1,t) as an induced subgraph. Our arguments also imply that the related connected dominating set and dominating clique problems are W[2]-hard in these graph classes. Finally, we show that for any t, the clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On group feedback vertex set parameterized by the size of the cutset

We study the parameterized complexity of a robust generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem; we are given a graph G with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of G that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal. Completing the results of Guillemot [Discr. Opt. 2011], we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a polynomial-time oracle.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Multiway Cut parameterized above lower bounds

In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove them to be fixed-parameter tractable. Our results imply O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Parameterized Complexity of Firefighting Revisited

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be permanently placed on an unburned vertex and the fire spreads to its neighborhood in the graph in so far no firefighters are protecting those vertices. The goal is to let as few vertices burn as possible. This problem is known to be NP-complete, even when restricted to bipartite graphs or to trees of maximum degree three. Initial study showed the Firefighter problem to be fixed-parameter tractable on trees in various parameterizations. We complete these results by showing that the problem is in FPT on general graphs when parameterized by the number of burned vertices, but has no polynomial kernel on trees, resolving an open problem. Conversely, we show that the problem is W[1]-hard when parameterized by the number of unburned vertices, even on bipartite graphs. For both parameterizations, we additionally give refined algorithms on trees, improving on the running times of the known algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Solving connectivity problems parameterized by treewidth in single exponential time

For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Subset feedback vertex set is fixed parameter tractable

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent kernelization and fixed-parameter algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (SUBSET-FVS in short) where an instance comes additionally with a set S ? V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis SUBSET-FVS was studied from the approximation algorithms perspective by Even et al. [SICOMP'00, SIDMA'00]. The question whether the SUBSET-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by |S|. Next we present an algorithm which reduces the given instance to 2^k n^O(1) instances with the size of S bounded by O(k^3), using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two facts allow us to give a 2^O(k log k) n^O(1) time algorithm solving the Subset Feedback Vertex Set problem, proving that it is indeed fixed-parameter tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Bandwidth and Distortion Revisited

In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363^n) time and polynomial space. For BANDWIDTH, this improves O^*(10^n) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c^n) time we are aware of. As a byproduct, we enhance the O(5^{n+o(n)})-time and O^*(2^n)-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383^n) time and space.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fast Approximation in Subspaces by Doubling Metric Decomposition

In this paper we propose and study a new complexity model for approximation algorithms. The main motivation are practical problems over large data sets that need to be solved many times for different scenarios, e.g., many multicast trees that need to be constructed for different groups of users. In our model we allow a preprocessing phase, when some information of the input graph $G=(V,E)$ is stored in a limited size data structure. Next, the data structure enables processing queries of the form ``solve problem A for an input $S\subseteq V$''. We consider problems like {\sc Steiner Forest}, {\sc Facility Location}, {\sc $k$-Median}, {\sc $k$-Center} and {\sc TSP} in the case when the graph induces a doubling metric. Our main results are data structures of near-linear size that are able to answer queries in time close to linear in $|S|$. This improves over typical worst case reuniting time of approximation algorithms in the classical setting which is $Ω(|E|)$ independently of the query size. In most cases, our approximation guarantees are arbitrarily close to those in the classical setting. Additionally, we present the first fully dynamic algorithm for the Steiner tree problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)

One of the driving problems in the CSP area is the Dichotomy Conjecture, formulated in 1993 by Feder and Vardi [STOC'93], stating that for any fixed relational structure G the Constraint Satisfaction Problem CSP(G) is either NP--complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in the recent years is the LIST MATRIX PARTITION problem. In 2004 Cameron et al. [SODA'04] classified almost all LIST MATRIX PARTITION variants for matrices of size at most four. The only case which resisted the classification became known as the STUBBORN PROBLEM. In this paper we show a result which enables us to finish the classification - thus solving a problem which resisted attacks for the last six years. Our approach is based on a combinatorial problem known to be at least as hard as the STUBBORN PROBLEM - the 3-COMPATIBLE COLOURING problem. In this problem we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. The tractability of the 3-COMPATIBLE COLOURING problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] - a quasipolynomial algorithm with a n^O(log n / log log n) time complexity. In this paper we present a polynomial-time algorithm for the 3-COMPATIBLE COLOURING problem and consequently we prove a dichotomy for the k-COMPATIBLE COLOURING problem.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

A Planar Linear Arboricity Conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. stated the Linear Arboricity Conjecture (LAC), that the linear arboricity of any simple graph of maximum degree $Δ$ is either $\lceil \tfracΔ{2} \rceil$ or $\lceil \tfrac{Δ+1}{2} \rceil$. In [J. L. Wu. On the linear arboricity of planar graphs. J. Graph Theory, 31:129-134, 1999] and [J. L. Wu and Y. W. Wu. The linear arboricity of planar graphs of maximum degree seven is four. J. Graph Theory, 58(3):210-220, 2008.] it was proven that LAC holds for all planar graphs. LAC implies that for $Δ$ odd, ${\rm la}(G)=\big \lceil \tfracΔ{2} \big \rceil$. We conjecture that for planar graphs this equality is true also for any even $Δ\ge 6$. In this paper we show that it is true for any even $Δ\ge 10$, leaving open only the cases $Δ=6, 8$. We present also an O(n log n)-time algorithm for partitioning a planar graph into max{la(G),5} linear forests, which is optimal when $Δ\ge 9$.

0 citations0 reviewsNo code linkedOpen access