FCT 2021
23rd
International Symposium on
Fundamentals of Computation Theory
September 12-15, 2021, Athens, Greece (virtually)
23rd
International Symposium on
Fundamentals of Computation Theory
September 12-15, 2021, Athens, Greece (virtually)
| 13:30-14:00 | Welcome |
| 14:00-16:30 | Tutorial
David Richerby |
| 16:30-17:00 | Break |
| 17:00-18:30 | Young Researchers' Forum (informal meeting)
|
| 18:30-19:30 | Social Meeting |
| 11:30-12:00 | Welcome - Opening |
| 12:00-13:00 | Plenary Talk I (chair: Aris Pagourtzis)
Nobuko Yoshida |
| 13:00-13:15 | Break |
| 13:15-14:15 | Session 1 [Logic, Languages, Complexity] (chair: Nikos Tzevelekos)
Bharat Adsul, Saptarshi Sarkar and A V Sreejith
Abstract:
We contribute to the refined understanding of the language-logic-algebra
interplay in the context of first-order properties of countable
words. We establish decidable algebraic characterizations of FO[1] --
one variable fragment of FO as well as boolean closure of existential
fragment of FO via a strengthening of Simon's theorem about piecewise
testable languages. We propose a new extension of FO which admits infinitary
quantifiers to reason about the inherent infinitary properties of countable
words. We provide very natural and hierarchical block-product based
characterization of the new extension. We also explicate its role
in view of other natural and classical logical systems such as WMSO and
FO[cut] - an extension of FO where quantification over Dedekind-cuts is
allowed. We rule out the possibility of a finite-basis for
a block-product based characterization of these logical systems.
Finally, we report simple but novel algebraic characterizations of one
variable fragments of the hierarchies of the new proposed extension of FO.
Miroslav Chodil and Antonin Kucera
Abstract:
We give a sufficient condition under which every finite-satisfiable formula of a given PCTL fragment has a model with at most doubly exponential number of states (consequently, the finite satisfiability problem for the fragment is
in 2-EXPSPACE). The condition is semantic and it is based on enforcing a form of ``progress'' in non-bottom SCCs contributing to the satisfaction of a given PCTL formula. We show that the condition is satisfied by PCTL fragments
beyond the reach of existing methods.
Hermann Gruber, Markus Holzer and Simon Wolfsteiner
Abstract:
Finite languages lie at the heart of literally every regular
expression. Therefore, we investigate the approximation complexity
of minimizing regular expressions without Kleene star, or,
equivalently, regular expressions describing finite languages.
On the side of approximation hardness, given such an expression of
size~$s$, we prove that it is impossible to approximate the minimum
size required by an equivalent regular expression within a factor of
$O\left(\frac{s}{(\log s)^{\delta}}\right)$ if the running time is
bounded by a quasipolynomial function depending on $\delta$, for
every $\delta>1$, unless the exponential time hypothesis (ETH)
fails. For approximation ratio $O(s^{1-\delta})$, we prove an
exponential-time lower bound depending on $\delta$, assuming ETH.
The lower bounds apply to alphabets of constant size.
On the algorithmic side, we show that the problem can be
approximated in polynomial time within $O(\frac{s\log\log s}{\log
s})$, with~$s$ being the size of the given regular expression.
For constant alphabet size, the bound improves to $O(\frac{s}{\log
s})$. Finally, we devise a familiy of superpolynomial
approximation algorithms with approximation ratios matching the
lower bounds, while the running times are just above the lower
bounds excluded by the exponential time hypothesis.
|
| 14:15-14:30 | Break |
| 14:30-15:30 | Session 2 [Automata and Complexity] (chair: Stefan Hoffmann)
Henning Fernau and Kshitij Gajjar
Abstract:
A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most
papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of
computational complexity. Note that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O(log n) time. Thus, limiting the size of the vertex labels upper bounds the
space complexity of storing the graph.
We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it such that the size of each vertex label is at most O(n^2d). This enables us to store the graph using O(m log
n) bits of memory. For sparse graphs (graphs with O(n) edges), this matches the trivial lower bound of Omega(n log n). Since planar graphs and forests have constant degeneracy, our result implies an upper bound of O(n^2) on their
label size. The previously best known upper bound on the label size of general graphs with the minimum number of isolated vertices was O(4^n), due to Kratochvil, Miller & Nguyen. Furthermore, their proof was existential whereas our
labelling can be constructed in polynomial time.
Peter Leupold and Sebastian Maneth
Abstract:
It is well known that for a regular tree language, it is decidable whether or not it can be recognized by a deterministic top-down tree automaton (DTA). However, the computational complexity of this problem has not been studied. We
show that for a given deterministic bottom-up tree automaton it can be decided in quadratic time whether or not its language can be recognized by a DTA. Since there are finite tree languages that cannot be recognized by DTAs, we also
consider finite unions of DTAs and show that also here, definability within deterministic bottom-up tree automata is decidable in quadratic time.
Markus Lohrey
Abstract:
We study the computational complexity of the word problem in HNN-extension of groups.
HNN-extension are a fundamental construction in geometric and combinatorial group theory.
We show that the word problem for an ascending HNN-extension of a group H is logspace
reducible to the so-called compressed word problem for H. The main result of the paper
shows that the word problem for an HNN-extension of a hyperbolic group H, where the
associated subgroups are cyclic, can be solved in polynomial time. This result can be easily
extended to fundamental groups of graphs of groups, where all vertex nodes are hyperbolic
and all edge groups are cyclic.
|
| 15:30-16:30 | Long Break |
| 16:30-17:50 | Session 3 [Automata, Complexity, Formal Methods] (chair: David Richerby)
Jin-Yi Cai, Austen Fan and Yin Liu
Abstract:
We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form Holant(f | =_3), where f is any integer-valued ternary symmetric constraint function on
Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of f. The constraint function can take both positive and negative values, allowing for cancellations. In addition, we
discover a new phenomenon: there is a set F with the property that for every f in F the problem Holant(f |=_3) is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic
transformation by [1 1 \\ 1 -1] to FKT together with an independent global argument.
Vrunda Dave, Taylor Dohmen, Shankara Narayanan Krishna, Ashutosh Trivedi
Abstract:
Regular model checking is an exploration technique for infinite
state systems where state spaces are represented as regular languages and
transition relations are expressed using rational relations over infinite (or finite) strings. We extend the regular model checking paradigm to permit the use of more powerful transition relations: the class of regular relations, of
which the rational relations are a strict subset. We use the language of monadic second-order logic (\mso{}) on infinite strings to specify such relations and adopt streaming string transducers (\sst{}s) as a suitable computational
model. We introduce nondeterministic \sst{}s over infinite strings (\wnsst{}s) and show that they precisely capture the relations definable in \mso{}. We further explore theoretical properties of \wnsst{}s required to effectively
carry out regular model checking. In particular, we establish that the regular type checking problem for \wnsst{}s is decidable in \pspace{}. Since the post-image of a regular language under a regular relation may not be regular (or
even context-free), approaches that iteratively compute the image can not be effectively carried out in this setting. Instead, we utilize the fact that regular relations are closed under composition, which, together with our
decidability result, provides a foundation for regular model checking with regular relations.
S. Raja and G. V. Sumukha Bharadwaj
Abstract:
In this paper, we study the computational complexity of the commutative determinant polynomial computed by a class of set-multilinear circuits which we call regular set-multilinear circuits. Regular set-multilinear circuits are
commutative circuits with a restriction on the order in which they can compute polynomials. A regular set-multilinear circuit can be seen as the commutative analogue of the ordered circuit defined by Hrubes, Wigderson and Yehudayoff
[HWY10]. We show that if the commutative determinant polynomial has a small representation in the sum of constantly many regular set-multilinear circuits, then the commutative permanent polynomial also has a small arithmetic circuit.
Stefan Hoffmann
Abstract:
The constrained synchronization problem asks for a synchronizing word of a given input automaton contained in a a regular set of constraints. It could be viewed as a special case of synchronization of a discrete event system under
supervisory control. Here, we study the computational complexity of the constrained synchronization problem for the class of sparse regular constraint languages. We give a new characterization of sparse regular sets, which equal the
bounded regular sets and give a full classification of the computational complexity of the constrained synchronization problem for strictly bounded regular languages. In addition, we derive a polynomial time decision procedure for the
complexity of the constrained synchronization problem, given a constraint automaton recognizing a strictly bounded regular language as input. Then, we introduce strongly self-synchronizing codes and investigate the constrained
synchronization problem for bounded languages induced by these codes. With our previous result, we deduce a full classification for these languages as well. In both cases, depending on the constraint language, our problem becomes
$NP$-complete or polynomial time solvable.
|
| 17:50-18:00 | Break |
| 18:00-19:00 | Plenary Talk II (chair: Stathis Zachos)
Constantinos Daskalakis |
| 19:15-20:15 |
Social Programme
The Athenian Acropolis through the Ages (19:30-20:15)
Abstract:
The Acropolis is one of the most famous Greek landmarks and one of the most historic locations of Athens.
It is the place where the first traces of human habitation in Athens (6 millenia ago) have been found. By Mycaenean times (13th century BCE) the small Neolithic settlement of the 3rd millenium BCE had evolved into a strong citadel. A few centuries later, in the Geometric Era, the Acropolis became a sanctuary and its transformation into a religious centre began. The first monumental temples were built in the 6th century; after the Persian Wars, the Acropolis began to gradually take the form we know today. Its masterpieces (like the Parthenon and the Propylaea) are considered the best examples of Greek architecture. The Acropolis changed through the ages, mirroring the history of Athens. During the Middle Ages, its temples were turned into churches, whereas the hill became a castle. Due to its strategic position, its monuments suffered the impact of various conflicts, until the Greek War of Independence; their marks are visible to this day. The Acropolis of Athens is the city’s symbol. It is also a place enriched by the happy convergence of art, history and mythology. Bio:
Aristotle Koskinas studied classical archaeology at the University of Ioannina, Greece. He specialized in the study of architectural terracottas (rooftiles). For several years he participated in various excavations conducted by
the Greek Ministry of Culture. He took part in the surface survey project conducted in Western Achaia by the Center for Greek and Roman Studies of the National Research Foundation, as well as in the Sicyon surface survey conducted
by the University of Thessaly. He published material from both projects.
In 2003 he graduated from the Greek School of Tourist Guides and has since been working as a guide. He specialises in organising thematic and/or educational tours for interested parties, such as universities, historic societies
etc. He has been working closely with several universities, such as the universities of Princeton, Missouri, Longwood, et.al.
He is also an accomplished narrator, and is a regular participant (by invitation of the National Archaeological Museum and the Greek Narration Festival) to participate in their yearly narration events. He lectures on Greek history and archaeology, while continuing to study and publish material from excavations of the Ministry of Culture. His other interests lay in the field of military history and conflict archaeology and he has been involved in historical reenactment events. Professional blog |
| 12:00-13:00 | Plenary Talk III (chair: Dimitris Fotakis)
Daniel Marx |
| 13:00-13:15 | Break |
| 13:15-14:15 | Session 4 [Parameterized Complexity and Algorithms] (chair: Henning Fernau)
Lukas Behrendt, Katrin Casel, Tobias Friedrich, J. A. Gregor Lagodzinski, Alexander Löser and Marcus Wilhelm
Abstract:
We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances in the given
instance which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the
parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric
edges in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable,
we present experimental results which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.
David Eppstein, Siddharth Gupta and Haleh Havvaei
Abstract:
We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $\Pi$ and an integer parameter $k$, the
general problem $P(G,\Pi,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $\Pi$. This problem, $P(G,\Pi,k)$ has been proved to be NPC by Lewis and Yannakakis. The parameterized complexity of
this problem is shown to be WO-complete by Khot and Raman, if $\Pi$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is WO-complete on general
graphs when $\Pi$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes.
Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes.
In particular, we show that:
Jelle Oostveen and Erik Jan van Leeuwen
Abstract:
Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work
of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower
bounds for the problems of Pi-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the
memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.
|
| 14:15-14:30 | Break |
| 14:30-15:30 | Session 5 [Multiagent Systems] (chair: Tomasz Radzik)
Joseph Livesey and Dominik Wojtczak
Abstract:
Gossip protocols are programs that can be used by a group of agents to synchronize what they know. Namely, assuming each agent holds a secret, the goal of a protocol is to reach a situation in which all agents know all secrets.
Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. In this paper, we solve open problems regarding one of the simplest classes of gossip protocols: propositional gossip protocols,
in which whether an agent wants to make a call depends only on his currently known set of secrets. Specifically, we show that all correct propositional gossip protocols, i.e., ones that always terminate in a situation where all agents
know all secrets, require the communication graph to be complete and at least 2n-3 calls to be made in the worst case. We also show that checking correctness of a given propositional gossip protocol is a coNP-complete problem. Finally
we report on implementing such a check with model checker nuXmv.
Kyrill Winkler, Ulrich Schmid and Thomas Nowak
Abstract:
We introduce a novel two-step approach for developing a distributed consensus
algorithm, which does not require the designer to identify and exploit
intricacies of the underlying system model explicitly.
In a first step, which is done off-line only once, labels representing valid decision
values (valencies) are assigned to suitable prefixes of all possible runs.
The challenge here is to assign them consistently for indistinguishable runs.
The second step consists in deploying a simple generic distributed consensus algorithm,
which just uses the pre-computed labeling. If it observes that all runs that may lead
to a local state that is indistinguishable from the current local state have
the same label, it decides on this label, otherwise it has to keep on checking.
We demonstate the power of our approach by developing a new and asymptotically
optimal algorithm for eventually stabilizing message adversaries for arbitrary
system sizes.
Kristoffer Arnsfelt Hansen and Troels Bjerre Lund
Abstract:
We study the computational complexity of computing or approximating a
quasi-proper equilibrium for a given finite extensive form game of
perfect recall. We show that the task of computing a symbolic
quasi-proper equilibrium is PPAD-complete for two-player games. For
the case of zero-sum games we obtain a polynomial time algorithm based
on Linear Programming. For general n-player games we show that
computing an approximation of a quasi-proper equilibrium is
FIXPₐ-complete. Towards our results for two-player games we devise a
new perturbation of the strategy space of an extensive form game which
in particular gives a new proof of existence of quasi-proper
equilibria for general n-player games.
|
| 15:30-16:30 | Long Break |
| 16:30-17:50 | Session 6 [Graph (Algorithms) I] (chair: Ralf Klasing)
Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis and Giulia Punzi
Abstract:
Given a directed multigraph G=(V,E), with |V|=n nodes and |E|=m edges, and an integer z, we are asked to assess whether the number #ET(G) of node-distinct Eulerian trails of G is at least z; two trails are called node-distinct if
their node sequences are different. This problem has been formalized by Bernardini et al.~[ALENEX 2020] as it is the core computational problem in several string processing applications. It can be solved in O(n^{\omega}) arithmetic
operations by applying the well-known BEST theorem, where \omega<2.373 denotes the matrix multiplication exponent. The algorithmic challenge is: Can we solve this problem faster for certain values of m and z? Namely, we want to design
a combinatorial algorithm for assessing whether #ET(G)>= z, which does not resort to the BEST theorem and has a predictably bounded cost as a function of m and z. We address this challenge by providing an algorithm requiring O(m
min{z, #ET(G)}) time. This bound is time-optimal for z=O(1) or for #ET(G)=O(1). The impact of our result on real-world graphs is striking: a simple implementation of our algorithm takes tens of seconds to assess #ET(G) >= z, whereas
a highly-optimized implementation of the BEST theorem requires more than 12 hours.
Nicolas Bousquet and Alice Joffard
Abstract:
We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph $G=(V,E)$ and two dominating sets $D_s$ and $D_t$ of $G$, in determining if there exists a sequence $S=\langle
D_1:=D_s,...,D_{\ell}:=D_t\rangle$ of dominating sets of $G$ such that for any two consecutive dominating sets $D_r$ and $D_{r+1}$ with $r \le t$, $D_{r+1}=(D_r\setminus u) \cup v$, where $uv\in E$.
In a recent paper, Bonamy et al. studied this problem and raised the following questions: what is the complexity of this problem on circular arc graphs? On circle graphs? In this paper, we answer both questions by proving that the
problem is polynomial on circular-arc graphs and PSPACE-complete on circle graphs.
Allen Ibiapina and Ana Silva
Abstract:
A temporal graph G is a graph that changes with time. More specifically, it is a pair (G, λ) where G is a graph and λ is a function on the edges of G that describes when each edge e ∈ E(G) is active. Given vertices s,t ∈ V(G), a
temporal s,t-path is a path in G that traverses edges in non-decreasing time; and if s,t are non-adjacent, then a vertex temporal s,t-cut is a subset S ⊆ V(G) whose removal destroys all temporal s,t-paths.
It is known that Menger’s Theorem does not hold on this context, i.e., that the maximum number of vertex disjoint temporal s,t-paths is not necessarilly equal to the minimum size of a vertex temporal s,t-cut. In a seminal paper,
Kempe, Kleinberg and Kumar (STOC’2000) defined a graph G to be Mengerian if equality holds on (G, λ) for every function λ. They then proved that, if each edge is allowed to be active only once in (G, λ), then G is Mengerian if and
only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We also provide a polynomial time
recognition algorithm.
Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul and Jan Arne Telle
Abstract:
The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for trees.
Motivated by a correspondence with Dasgupta's objective for hierarchical clustering we consider the total rather than maximum depth of vertices as an alternative objective for minimization. For vertex partition trees this leads to a
new parameter
with a natural interpretation as a measure of robustness against vertex removal.
As tools for the study of this family of parameters we show that they have similar recursive expressions and prove a binary tree rotation lemma. The new parameter is related to trivially perfect graph completion and therefore
intractable like the other three are known to be. We give polynomial-time algorithms for both total-depth variants
on caterpillars and on trees with a bounded number of leaf neighbors. For general trees, we obtain a 2-approximation algorithm.
|
| 17:50-18:00 | Break |
| 18:00-19:00 | Business Meeting |
| 19:15-20:00 | Social Programme |
| 12:00-13:00 | Plenary Talk IV (chair: Evripidis Bampis)
Claire Mathieu |
| 13:00-13:15 | Break |
| 13:15-14:35 | Session 7 [Graph (Algorithms) II] (chair: Thanasis Lianeas)
Sanjana Dey, Anil Maheshwari and Subhas Nandy
Abstract:
In the minimum consistent subset (MCS) problem, a connected simple undirected graph $G=(V, E)$ is given whose each node is colored by one of the colors
$\{c_1,c_2,\ldots, c_k\}$; the objective is to compute a subset ${\cal C}
\subseteq V$ such that for each node $v \in V$, one of its nearest neighbors in
${\cal C}$ (with respect to the hop-distance) is of the same color as of $v$. The decision version of the MCS problem is NP-complete even for planar graphs. We
propose a polynomial-time algorithm when the graph $G$ is a bichromatic tree.
Christophe Crespelle
Abstract:
We present an algorithm for computing a minimal editing of an arbitrary graph G into a cograph, i.e. a set of edits (additions and deletions of edges) that turns G into a cograph and that is minimal for inclusion. Our algorithm runs
in linear time in the size of the input graph, that is O(n+m) time where n and m are the number of vertices and the number of edges of G, respectively.
Max Bender, Jacob Gilbert, Kirk Pruhs
Abstract:
Motivated by demand-responsive parking pricing systems
we consider posted-price algorithms for the online metrical matching problem. Our main result is a poly-log competitive
posted-price algorithm in the case that the metric space is a spider.
Jesper Jansson and Wing Lik Lee
Abstract:
The rooted triplet distance measures the structural dissimilarity between two
rooted phylogenetic trees (unordered trees with distinct leaf labels and no
outdegree-1 nodes) having the same leaf label set.
It is defined as the number of 3-subsets of the leaf label set that induce two
different subtrees in the two trees.
The fastest currently known algorithm for computing the rooted triplet distance
was designed by Brodal et al. (SODA 2013).
It runs in O(n log n) time, where n is the number of leaf labels in the input
trees, and a long-standing open question is whether this is optimal or not.
In this paper, we present two new o(n log n)-time algorithms for the special
case of caterpillars (rooted phylogenetic trees in which every node has at most
one non-leaf child), thus breaking the O(n log n)-time bound for a fundamental
class of trees.
Our first algorithm makes use of a dynamic rank-select data structure by Raman
et al. (WADS 2001) and runs in O(n log n / loglog n) time.
Our second algorithm relies on an efficient algorithm for orthogonal range
counting invented by Chan and Patrascu (SODA 2010) and runs in O(n sqrt{log n})
time.
|
| 14:35-15:15 | Long Break |
| 15:15-16:15 | Session 8 [Complexity and Randomness] (chair: Nikos Leonardos)
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Michaela Seifrtová
Abstract:
The notion of graph covers is a discretization of covering spaces introduced
and deeply studied in topology. In discrete mathematics and theoretical
computer science, they have attained a lot of attention from both the
structural and complexity perspectives. Nonetheless, disconnected graphs were
usually omitted from the considerations with the explanation that it is
sufficient to understand coverings of the connected components of the target
graph by components of the source one. However, different (but equivalent)
versions of the definition of covers of connected graphs generalize to
nonequivalent definitions of disconnected graphs. The aim of this paper is to
summarize this issue and to compare three different approaches to covers of
disconnected graphs: 1) locally bijective homomorphisms, 2) globally
surjective locally bijective homomorphisms (which we call \emph{surjective covers}), and
3) locally bijective homomorphisms which cover every vertex the same number
of times (which we call \emph{equitable covers}). The standpoint of our comparison is
the complexity of deciding if an input graph covers a fixed target graph. We
show that both surjective and equitable covers satisfy what certainly is a natural and
welcome property: covering a disconnected graph is polynomial time decidable
if such it is for every connected component of the graph, and it is
NP-complete if it is NP-complete for at least one of its components. Despite
of this, we argue that the third variant, equitable covers, is the right one,
when considering covers of colored (multi)graphs. Moreover, the complexity of
surjective and equitable covers differ from the fixed parameter complexity point of
view. We conclude the paper by a complete characterization of the complexity
of covering 2-vertex colored multigraphs with semi-edges. We present the
results in the utmost generality and strength. In accord with the current
trends we consider (multi)graphs with semi-edges, and, on the other hand, we aim at proving the NP-completeness results for simple input graphs.
Piotr Borowiecki, Dariusz Dereniowski and Dorota Osula
Abstract:
The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph $G$. We introduce a bicriteria generalization in which additionally the \emph{width} of the elimination tree needs to be
bounded by some input integer $b$. We are interested in the case when $G$ is the line graph of a tree, proving that the problem is $\NP$-hard and obtaining a polynomial-time additive $2b$-approximation algorithm. This particular class
of graphs received significant attention, mainly due to a number of potential applications, e.g. in parallel assembly of modular products, or parallel query processing in relational databases, as well as purely combinatorial
applications, e.g. searching in tree-like partial orders (which generalizes binary search on sorted data).
Maciej Skorski
Abstract:
This paper analyzes in detail the concentration properties of the collision estimator inspired by the birthday-paradox.
|
| 16:15-16:30 | Break |
| 16:30-18:00 | Session 9 [Best Papers]
Best Student Paper I
Abstract:
Let $\Pi$ be a hereditary graph class. The problem of deletion to $\Pi$, takes as input a graph $G$ and asks for a minimum number (or a fixed integer $k$) of vertices to be deleted from $G$ so that the resulting graph belongs to
$\Pi$. This is a well-studied problem in paradigms including approximation and parameterized complexity. This problem, for example, covers {\sc vertex cover}, {\sc feedback vertex set}, {\sc cluster vertex deletion}, {\sc perfect
deletion} to name a few. The study of this problem in parameterized complexity has resulted in several powerful algorithmic techniques including iterative compression and important separators.
It has long been known that the problem is fixed-parameter tractable (FPT) as long as $\Pi$ has a finite forbidden set. When $\Pi$ has an infinite forbidden set (for example, when $\Pi$ is the class of forests or perfect graphs), both
hardness and FPT results are known for specific graph classes.
Recently (IPEC 2020, arxiv.org/abs/2105.04660), the study of a natural extension of the problem was initiated. In that problem, we are given a finite set of hereditary graph classes, and the input is an undirected graph. The goal is
to determine
whether $k$ vertices can be deleted from the given graph, so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem has been shown to be
FPT as long as the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph class can be expressible in the counting monodic second order (CMSO) logic.
While this was shown using some black box theorems, faster algorithms were shown when each of the hereditary graph classes has a finite forbidden set.
In this paper, we do a deep dive on pairs of specific graph classes ($\Pi_1, \Pi_2$) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. We design
two general algorithms for pairs of graph classes (possibly having infinite forbidden sets) satisfying certain conditions on their forbidden sets. Our first general method covers pairs of graph classes including (Interval, Trees),
(Proper Interval, Trees) and (Chordal, Bipartite Permutation) and the second covers (Clique, Planar) and (Clique, Bounded Treewidth) for ($\Pi_1$, $\Pi_2$).
Our algorithms make non-trivial use of the branching technique and as black box, FPT algorithms for deletion to individual graph classes.
Best Student Paper II
Abstract:
Removing all connections between two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s,z)-separation problem is well-known to be polynomial solvable and
serves as an important primitive in many applications related to network connectivity.
We study the NP-hard temporal (s,z)-separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle this problem by restricting the layers (i.e., graphs
characterized by edges that are present at a certain point in time) to specific graph classes.
We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general
the problem remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over
time".
Best Paper
Abstract:
Baumeister et al. [7] introduced the possible winner with uncertain weights problem which, given a weighted election with the weights of some voters as yet unspecified, asks whether one can assign weights to these voters such that a
distinguished candidate wins. Solving all questions they specifically left open for nonnegative integer weights, we show that two variants of this problem for 3-approval and four variants for plurality with runoff can be solved
efficiently. In addition, we study variants of this problem for Borda, k-veto, and veto with runoff in terms of their computational complexity. Finally, we also prove that the problem of constructive control by adding voters in
succinct representation belongs to P for plurality with runoff and veto with runoff.
|
| 18:00-18:30 | Closing-Farewell |
