Katarzyna Paluch
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Katarzyna Paluch has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
Dimitrios Michail
Max-Planck-Institut für Informatik, Saarbrücken, Germany
4 shared publicationsKurt Mehlhorn
Max-Planck-Institut für Informatik, Saarbrücken, Germany
4 shared publications- Szymon Dudycz
University of Wrocław
4 shared publications Telikepalli Kavitha
Indian Institute of Science, Bangalore, India
4 shared publications- Mateusz Wasylkiewicz
Institute of Computer Science University of Wrocław Poland
2 shared publications Adam Kunysz
1 shared publication
Latest Publications
- Open Access
Clique-free t-matchings in degree-bounded graphs
We consider problems of finding a maximum size/weight $t$-matching without forbidden subgraphs in an undirected graph $G$ with the maximum degree bounded by $t+1$, where $t$ is an integer greater than $2$. Depending on the variant forbidden subgraphs denote certain subsets of $t$-regular complete partite subgraphs of $G$. A graph is complete partite if there exists a partition of its vertex set such that every pair of vertices from different sets is connected by an edge and vertices from the same set form an independent set. A clique $K_t$ and a bipartite clique $K_{t,t}$ are examples of complete partite graphs. These problems are natural generalizations of the triangle-free and square-free $2$-matching problems in subcubic graphs. In the weighted setting we assume that the weights of edges of $G$ are vertex-induced on every forbidden subgraph. We present simple and fast combinatorial algorithms for these problems. The presented algorithms are the first ones for the weighted versions, and for the unweighted ones, are faster than those known previously. Our approach relies on the use of gadgets with so-called half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints.Open AccessClique-free t-matchings in degree-bounded graphs
We consider problems of finding a maximum size/weight $t$-matching without forbidden subgraphs in an undirected graph $G$ with the maximum degree bounded by $t+1$, where $t$ is an integer greater than $2$. Depending on the variant forbidden subgraphs denote certain subsets of $t$-regular complete partite subgraphs of $G$. A graph is complete partite if there exists a partition of its vertex set such that every pair of vertices from different sets is connected by an edge and vertices from the same set form an independent set. A clique $K_t$ and a bipartite clique $K_{t,t}$ are examples of complete partite graphs. These problems are natural generalizations of the triangle-free and square-free $2$-matching problems in subcubic graphs. In the weighted setting we assume that the weights of edges of $G$ are vertex-induced on every forbidden subgraph. We present simple and fast combinatorial algorithms for these problems. The presented algorithms are the first ones for the weighted versions, and for the unweighted ones, are faster than those known previously. Our approach relies on the use of gadgets with so-called half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints. - 1 October 2021
- Published by Elsevier in Information Processing Letters
- Vol. 171
A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges
- 1 October 2021
- Published by Elsevier in Information Processing Letters
- Vol. 171
A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges
- Open Access
Optimal General Matchings
Given a graph $G=(V,E)$ and for each vertex $v \in V$ a subset $B(v)$ of the set $\{0,1,\ldots, d_G(v)\}$ a $B$-matching of $G$ is any set $F \subseteq E$ such that $d_F(v) \in B(v)$ for each vertex $v$. The general matching problem asks the existence of a $B$-matching in a given graph. A set $B(v)$ is said to have a {\em gap of length} $p$ if there exists a number $k \in B(v)$ such that $k+1, \ldots, k+p \notin B(v)$ and $k+p+1 \in B(v)$. Without any restrictions the general matching problem is NP-complete. However, if no set $B(v)$ contains a gap of length greater than $1$, then the problem can be solved in polynomial time and Cornuejols \cite{Cor} presented an algorithm for finding a $B$-matching, if it exists. In this paper we consider a version of the general matching problem, in which we are interested in finding a $B$-matching having a maximum (or minimum) number of edges. We present the first polynomial time algorithm for the maximum weight $B$-matching for the case when no set $B(v)$ contains a gap of length greater than $1$.Open AccessOptimal General Matchings
Given a graph $G=(V,E)$ and for each vertex $v \in V$ a subset $B(v)$ of the set $\{0,1,\ldots, d_G(v)\}$ a $B$-matching of $G$ is any set $F \subseteq E$ such that $d_F(v) \in B(v)$ for each vertex $v$. The general matching problem asks the existence of a $B$-matching in a given graph. A set $B(v)$ is said to have a {\em gap of length} $p$ if there exists a number $k \in B(v)$ such that $k+1, \ldots, k+p \notin B(v)$ and $k+p+1 \in B(v)$. Without any restrictions the general matching problem is NP-complete. However, if no set $B(v)$ contains a gap of length greater than $1$, then the problem can be solved in polynomial time and Cornuejols \cite{Cor} presented an algorithm for finding a $B$-matching, if it exists. In this paper we consider a version of the general matching problem, in which we are interested in finding a $B$-matching having a maximum (or minimum) number of edges. We present the first polynomial time algorithm for the maximum weight $B$-matching for the case when no set $B(v)$ contains a gap of length greater than $1$. - Open Access
New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. In this paper we give a fast combinatorial $\frac{7}{10}$-approximation algorithm for Max ATSP. It is based on techniques of {\em eliminating} and {\em diluting} problematic subgraphs with the aid of {\it half-edges} and a method of edge coloring. (A {\it half-edge} of edge $(u,v)$ is informally speaking "either a head or a tail of $(u,v)$".) A novel technique of {\em diluting} a problematic subgraph $S$ consists in a seeming reduction of its weight, which allows its better handling. The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of $\frac 23$, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a result by Mucha, which states that an $\alpha$-approximation algorithm for Max ATSP implies a $(2+\frac{11(1-\alpha)}{9-2\alpha})$-approximation algorithm for the shortest superstring problem (SSP), we obtain also a $(2 \frac{33}{76} \approx 2,434)$-approximation algorithm for SSP, beating the previously best known (having an approximation factor equal to $2 \frac{11}{23} \approx 2,4782$.)Open AccessNew Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. In this paper we give a fast combinatorial $\frac{7}{10}$-approximation algorithm for Max ATSP. It is based on techniques of {\em eliminating} and {\em diluting} problematic subgraphs with the aid of {\it half-edges} and a method of edge coloring. (A {\it half-edge} of edge $(u,v)$ is informally speaking "either a head or a tail of $(u,v)$".) A novel technique of {\em diluting} a problematic subgraph $S$ consists in a seeming reduction of its weight, which allows its better handling. The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of $\frac 23$, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a result by Mucha, which states that an $\alpha$-approximation algorithm for Max ATSP implies a $(2+\frac{11(1-\alpha)}{9-2\alpha})$-approximation algorithm for the shortest superstring problem (SSP), we obtain also a $(2 \frac{33}{76} \approx 2,434)$-approximation algorithm for SSP, beating the previously best known (having an approximation factor equal to $2 \frac{11}{23} \approx 2,4782$.) - 29 June 2018
- Published by Springer Nature
- p. 316-327
Manipulation Strategies for the Rank-Maximal Matching Problem
- 29 June 2018
- Published by Springer Nature
- p. 316-327
Manipulation Strategies for the Rank-Maximal Matching Problem
- 4 November 2017
- Published by Springer Nature in Theory of Computing Systems
- Vol. 62 (2) , 319-336
Maximum ATSP with Weights Zero and One via Half-Edges
- 4 November 2017
- Published by Springer Nature in Theory of Computing Systems
- Vol. 62 (2) , 319-336
Maximum ATSP with Weights Zero and One via Half-Edges
- 24 May 2017
- Published by Springer Nature
- p. 173-185
A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- 24 May 2017
- Published by Springer Nature
- p. 173-185
A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- Open AccessA $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman ProblemIn the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. We present a fast combinatorial $\frac 45$ - approximation algorithm for Max TSP. The previous best approximation for this problem was $\frac 79$. The new algorithm is based on a novel technique of eliminating difficult subgraphs via half-edges, a new method of edge coloring and a technique of exchanging edges. A half-edge of edge $e=(u,v)$ is informally speaking "a half of $e$ containing either $u$ or $v$".Open AccessA $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman ProblemIn the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. We present a fast combinatorial $\frac 45$ - approximation algorithm for Max TSP. The previous best approximation for this problem was $\frac 79$. The new algorithm is based on a novel technique of eliminating difficult subgraphs via half-edges, a new method of edge coloring and a technique of exchanging edges. A half-edge of edge $e=(u,v)$ is informally speaking "a half of $e$ containing either $u$ or $v$".
- 21 December 2015
- Published by Society for Industrial & Applied Mathematics (SIAM)
Characterisation of Strongly Stable Matchings
An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph G = (A ∪ B, E), with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge (x, y) ∊ E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present a characterisation of the set of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving [7]. It has previously been shown that strongly stable matchings form a distributive lattice [8] and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with O(m) elements representing all strongly stable matchings, where m denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in O(nm2) time and the other in O(nm) time, where n denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.
- 21 December 2015
- Published by Society for Industrial & Applied Mathematics (SIAM)
Characterisation of Strongly Stable Matchings
An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph G = (A ∪ B, E), with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge (x, y) ∊ E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present a characterisation of the set of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving [7]. It has previously been shown that strongly stable matchings form a distributive lattice [8] and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with O(m) elements representing all strongly stable matchings, where m denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in O(nm2) time and the other in O(nm) time, where n denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.