Author name cluster

Tomás Masarík

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

STOC Conference 2024 Conference Paper

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

Peter Gartland
Daniel Lokshtanov
Tomás Masarík
Marcin Pilipczuk
Michal Pilipczuk
Pawel Rzazewski

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H -free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F -free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let S t , t , t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G , one can in polynomial time find either an induced S t , t , t in G , or a balanced separator consisting of O (log| V ( G )|) vertex neighborhoods in G , or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G . This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O (log| V ( G )|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Details

SODA Conference 2024 Conference Paper

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

Jesse Campion Loth
Kevin Halasz
Tomás Masarík
Bojan Mohar
Robert Sámal

A random 2-cell embedding of a connected graph G in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a random variable. Random embeddings of two particular graph classes - those of a bouquet of n loops and those of n parallel edges connecting two vertices - have been extensively studied and are well-understood. However, little is known about more general graphs despite their important connections with central problems in mainstream mathematics and in theoretical physics (see [Lando & Zvonkin, Graphs on surfaces and their applications, Springer 2004]). There are also tight connections with problems in computing (random generation, approximation algorithms). The results of this paper, in particular, explain why Monte Carlo methods (see, e. g. , [Gross & Tucker, Local maxima in graded graphs of imbeddings, Ann. NY Acad. Sci 1979] and [Gross & Rieper, Local extrema in genus stratified graphs, JGT 1991]) cannot work for approximating the minimum genus of graphs. In his breakthrough work ([Stahl, Permutation-partition pairs, JCTB 1991] and a series of other papers), Stahl developed the foundation of “random topological graph theory”. Most of his results have been unsurpassed until today. In our work, we analyze the expected number of faces of random embeddings (equivalently, the average genus) of a graph G. It was very recently shown [Campion Loth & Mohar, Expected number of faces in a random embedding of any graph is at most linear, CPC 2023] that for any graph G, the expected number of faces is at most linear. We show that the actual expected number of faces F(G) is almost always much smaller. In particular, we prove the following results: (1) ½ ln n - 2 < 𝔼 [F (K n )] ≤ 3. 65 ln n+ o(1). This substantially improves Stahl's n + ln n upper bound for this case. (2) For random graphs G(n, p) (p = p(n)), we have. (3) For random models B(n, Δ) containing only graphs, whose maximum degree is at most Δ, we obtain stronger bounds by showing that the expected number of faces is Θ(ln n ). * The full version of our paper available on arXiv https: //arxiv. org/abs/2211. 01032.

Details

SODA Conference 2023 Conference Paper

A tight quasi-polynomial bound for Global Label Min-Cut

Lars Jaffke
Paloma T. Lima
Tomás Masarík
Marcin Pilipczuk
Uéverton S. Souza

We study a generalization of the classic GLOBAL MIN-CUT problem, called GLOBAL LABEL MIN-CUT (or sometimes GLOBAL HEDGE MIN-CUT): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the st-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized n O(log OPT) -time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P”. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time ( np ) o(log n /(log log n )2 ) would contradict the Randomized Exponential Time Hypothesis, where n is the number of vertices, and p is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the SUBGRAPH ISOMORPHISM problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters. * This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (LJ, TM, MP, US) and from the Research Council of Norway (LJ).

Details

SODA Conference 2023 Conference Paper

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Meike Hatzel
Lars Jaffke
Paloma T. Lima
Tomás Masarík
Marcin Pilipczuk
Roohani Sharma
Manuel Sorge

We show fixed-parameter tractability of the DIRECTED MULTICUT problem with three terminal pairs (with a randomized algorithm). In this problem we are given a directed graph G, three pairs of vertices (called terminals ) ( s 1, t 1 ), ( s 2, t 2 ), ( s 3, t 3 ), and an integer k and we want to find a set of at most k non-terminal vertices in G that intersect all s 1 t 1 -paths, all s 2 t 2 -paths, and all s 3 t 3 -paths. The parameterized complexity of this problem has been open since Chitnis, Hajiaghayi, and Marx proved fixed-parameter tractability of the two-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of the four-terminal-pairs case at SODA 2016. On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced. * The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07425. The research leading to the results presented in this paper was partially carried out during the Parameterized Algorithms Retreat of the University of Warsaw, PARUW 2022, held in Bedlewo in April 2022. This research is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (TM, MP) and 648527 (MH), from the Alexander von Humboldt Foundation (MS), from the Research Council of Norway (LJ), and by the Federal Ministry of Education and Research (BMBF) and by a fellowship within the IFI programme of the German Academic Exchange Service (DAAD). (MH).

Details

SODA Conference 2021 Conference Paper

Optimal Discretization is Fixed-parameter Tractable

Stefan Kratsch
Tomás Masarík
Irene Muzi
Marcin Pilipczuk
Manuel Sorge

Given two disjoint sets W 1 and W 2 of points in the plane, the O ptimal D iscretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W 1 from W 2, that is, in every region into which the lines partition the plane there are either only points of W 1, or only points of W 2, or the region is empty. Equivalently, O ptimal D iscretization can be phrased as a task of discretizing continuous variables: We would like to discretize the range of x -coordinates and the range of y -coordinates into as few segments as possible, maintaining that no pair of points from W 1 × W 2 are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time, where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.

Details

MFCS Conference 2020 Conference Paper

U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited

Jan Kratochvíl
Tomás Masarík
Jana Masaríková

Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs - a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs and demonstrate the advantages of this generalized model by providing a subexponential-time algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomial-time algorithm for certain subclasses of mixed unit interval graphs. We point out a substantial mistake in the proof of the polynomiality of the MaxCut problem on unit interval graphs by Boyaci, Ekim, and Shalom (2017). Hence, the time complexity of this problem on unit interval graphs remains open. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs.

Details

MFCS Conference 2019 Conference Paper

Parameterized Complexity of Fair Vertex Evaluation Problems

Dusan Knop
Tomás Masarík
Tomás Toufar

A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula. In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i. e. , the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.

Details