Source author record

Arkadiusz Socała

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Artificial Intelligence Computer Science and Game Theory math.CO Multiagent Systems

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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].

preprint2016arXiv

On the fine-grained complexity of rainbow coloring

The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\ge 2$ , there is no algorithm for Rainbow k-Coloring running in time $2^{o(n^{3/2})}$ , unless ETH fails. Motivated by this negative result we consider two parameterized variants of the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is FPT when parameterized by $|S|$ . We also study Maximum Rainbow k-Coloring problem, where we are additionally given an integer $q$ and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $k\ge 2$ (thus proving that the problem is FPT), extending the result of Ananth et al. [FSTTCS 2011].

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.

preprint2015arXiv

Linear kernels for outbranching problems in sparse digraphs

In the $k$ -Leaf Out-Branching and $k$ -Internal Out-Branching problems we are given a directed graph $D$ with a designated root $r$ and a nonnegative integer $k$ . The question is to determine the existence of an outbranching rooted at $r$ that has at least $k$ leaves, or at least $k$ internal vertices, respectively. Both these problems were intensively studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $O(k^2)$ vertices are known on general graphs. In this work we show that $k$ -Leaf Out-Branching admits a kernel with $O(k)$ vertices on $\mathcal{H}$ -minor-free graphs, for any fixed family of graphs $\mathcal{H}$ , whereas $k$ -Internal Out-Branching admits a kernel with $O(k)$ vertices on any graph class of bounded expansion.

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)}$ .

preprint2014arXiv

Assigning channels via the meet-in-the-middle approach

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $\ell$ -bounded Channel Assignment (when the edge weights are bounded by $\ell$ ) running in time $O^*((2\sqrt{\ell+1})^n)$ . This is the first algorithm which breaks the $(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether Channel Assignment admits a $O(c^n)$ -time algorithm, for a constant $c$ independent of $\ell$ . We consider a similar question for Generalized T-Coloring, a CSP problem that generalizes \CA. We show that Generalized T-Coloring does not admit a $2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$ -time algorithm, where $r$ is the size of the instance.

preprint2013arXiv

Beyond the Shannon's Bound

Let $G=(V,E)$ be a multigraph of maximum degree $Δ$ . The edges of $G$ can be colored with at most $\frac{3}{2}Δ$ colors by Shannon's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $Δ$ colors. Shannon's Theorem gives a bound of $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor}|E|$ . However, for $Δ=3$ , Kamiński and Kowalik [SWAT'10] showed that there is a 3-edge-colorable subgraph of size at least $\frac{7}{9}|E|$ , unless $G$ has a connected component isomorphic to $K_3+e$ (a $K_3$ with an arbitrary edge doubled). Here we extend this line of research by showing that $G$ has a $Δ$ -edge colorable subgraph with at least $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor-1}|E|$ edges, unless $Δ$ is even and $G$ contains $\fracΔ{2}K_3$ or $Δ$ is odd and $G$ contains $\frac{Δ-1}{2}K_3+e$ . Moreover, the subgraph and its coloring can be found in polynomial time. Our results have applications in approximation algorithms for the Maximum $k$ -Edge-Colorable Subgraph problem, where given a graph $G$ (without any bound on its maximum degree or other restrictions) one has to find a $k$ -edge-colorable subgraph with maximum number of edges. In particular, for every even $k \ge 4$ we obtain a $\frac{2k+2}{3k+2}$ -approximation and for every odd $k\ge 5$ we get a $\frac{2k+1}{3k}$ -approximation. When $4\le k \le 13$ this improves over earlier algorithms due to Feige et al. [APPROX'02]

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.

Arkadiusz Socała

Research overview

Is this your work?

7 publications

Approximation and Parameterized Complexity of Minimax Approval Voting

On the fine-grained complexity of rainbow coloring

Tight Lower Bounds on Graph Embedding Problems

Linear kernels for outbranching problems in sparse digraphs

The Hardness of Subgraph Isomorphism

Assigning channels via the meet-in-the-middle approach

Beyond the Shannon's Bound

See the researcher in context

Building this map preview