kth.sePublications
Change search
Refine search result
1 - 25 of 25
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Achilleos, Antonis
    et al.
    Lampis, Michael
    City University of New York.
    Mitsou, Valia
    Parameterized Modal Satisfiability2010In: ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, 2010, p. 369-380Conference paper (Refereed)
    Abstract [en]

    We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem’s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time’s dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.

  • 2. Achilleos, Antonis
    et al.
    Lampis, Michail
    City University of New York.
    Mitsou, Valia
    Parameterized Modal Satisfiability2012In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 64, no 1, p. 38-55Article in journal (Refereed)
    Abstract [en]

    We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem’s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time’s dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose pos- sible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.

    Download full text (pdf)
    fulltext
  • 3. Bampas, Evangelos
    et al.
    Kaouri, Georgia
    Lampis, Michael
    National Technical University of Athens.
    Pagourtzis, Aris
    Periodic Metro Scheduling2006Conference paper (Refereed)
    Abstract [en]

    We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{PMS}}) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks. We present exact algorithms for ({ extsc{PMS}}) in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem.

  • 4. Bar-Noy, Amotz
    et al.
    Cheilaris, Panagiotis
    Lampis, Michael
    Mitsou, Valia
    Zachos, Stathis
    Ordered Coloring for Grids and Related Graphs2011In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294Article in journal (Refereed)
    Abstract [en]

     We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) is related to conflict-free coloring and other traditional coloring problems. Such coloring problems can model (among others) efficient frequency assignments in cellular networks. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs. To the best of our knowledge, this is the first attempt to calculate exactly the ordered chromatic number of these graph families.

  • 5. Bar-Noy, Amotz
    et al.
    Cheilaris, Panagiotis
    Lampis, Michael
    Graduate Center, City University of New York, 365 5th Avenue, New York, NY 10016, USA.
    Mitsou, Valia
    Zachos, Stathis
    Ordered coloring of grids and related graphs2012In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 444, p. 40-51Article in journal (Refereed)
    Abstract [en]

    We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) has applications, among other areas, in efficient solving of sparse linear systems of equations and scheduling parallel assembly of products. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs.

  • 6. Bar-Noy, Amotz
    et al.
    Lampis, Michael
    Doctoral Program in Computer Science, Graduate Center, City University of New York, 365 5th Avenue, New York, NY, 10016, USA.
    Online Maximum Directed Cut2012In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 24, no 1, p. 52-64Article in journal (Refereed)
    Abstract [en]

    We investigate a natural online version of the well-known MAXIMUM DIRECTED CUT problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of 3 root 3/2 approximate to 2.5981. We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of 3 root 3/2 - epsilon for any epsilon > 0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MAXDICUT in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.

  • 7. Bar-Noy, Amotz
    et al.
    Lampis, Michael
    Online Maximum Directed Cut2009In: ALGORITHMS AND COMPUTATION, PROCEEDINGS / [ed] Dong, Y; Du, DZ; Ibarra, O, 2009, p. 1124-1133Conference paper (Refereed)
    Abstract [en]

    We investigate a natural online version of the well-known MAXIMUM DIRECTED CUT problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of 3 root 3/2 approximate to 2.5981. We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of 3 root 3/2 - epsilon for any epsilon > 0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MAXDICUT in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.

  • 8. Bar-Noy, Amotz
    et al.
    Panagiotis, Cheilaris
    Lampis, Michael
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mitsou, Valia
    Zachos, Stathis
    Ordered Coloring Grids and Related Graphs2009In: 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2009, 2009, p. 30-43Conference paper (Refereed)
    Abstract [en]

    We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) is related to conflict-free coloring and other traditional coloring problems. Such coloring problems can model (among others) efficient frequency assignments in cellular networks. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs. To the best of our knowledge, this is the first attempt to calculate exactly the ordered chromatic number of these graph families.

  • 9. Gajarský, J.
    et al.
    Lampis, Michael
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Ordyniak, S.
    Parameterized algorithms for modular-width2013In: Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Springer, 2013, p. 163-176Conference paper (Refereed)
    Abstract [en]

    It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILP and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the "price of generality" paid by clique-width.

  • 10. Gutin, Gregory
    et al.
    Kim, Eun Jung
    Lampis, Michael
    Mitsou, Valia
    Vertex Cover Problem Parameterized Above and Below Tight Bounds2011In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 48, no 2, p. 402-410Article in journal (Refereed)
    Abstract [en]

    We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan et al. in J. Comput. Syst. Sci. 75(2):137-153, 2009) are fixed-parameter tractable and two other parameterizations are W[1]-hard (one of them is, in fact, W[2]-hard).

  • 11.
    Lampis, Michael
    City University of New York.
    A kernel of order 2k-c log k for vertex cover2011In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 111, no 23-24, p. 1089-1091Article in journal (Refereed)
    Abstract [en]

    In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techniques can be extended to improve the produced kernel to order 2k - c log k, for any fixed constant c.

  • 12.
    Lampis, Michael
    Computer Science Department, Graduate Center, City University of New York, New York, NY, USA.
    Algorithmic Meta-theorems for Restrictions of Treewidth2012In: Algorithmica, ISSN 0178-4617, Vol. 64, p. 19-37Article in journal (Refereed)
    Abstract [en]

    Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees.

    We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number. We prove stronger algorithmic meta-theorems for these more restricted classes of graphs. More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.

  • 13.
    Lampis, Michael
    City University of New York.
    Algorithmic Meta-Theorems for Restrictions of Treewidth2010In: ALGORITHMS-ESA 2010 / [ed] DeBerg, M; Meyer, U, Springer Berlin/Heidelberg, 2010, p. 549-560Conference paper (Refereed)
    Abstract [en]

    Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees. We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number. We prove stronger algorithmic meta-theorems for these more restricted classes of graphs. More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.

  • 14.
    Lampis, Michael
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Local Improvement Gives Better Expanders2012Manuscript (preprint) (Other academic)
    Abstract [en]

    It has long been known that random regular graphs are with high probability good ex-panders. This was first established in the 1980s by Bollobás by directly calculating the probability thata set of vertices has small expansion and then applying the union bound. In this paper we improve on this analysis by relying on a simple high-level observation: if a graphcontains a set of vertices with small expansion then it must also contain such a set of vertices that islocally optimal, that is, a set whose expansion cannot be made smaller by exchanging a vertex fromthe set with one from the set’s complement. We show that the probability that a set of vertices satisfiesthis additional property is significantly smaller. Thus, after again applying the union bound, we obtainimproved lower bounds on the expansion of random ∆-regular graphs for∆≥4. In fact, the gains fromthis analysis increase as ∆ grows, a fact we explain by extending our technique to general ∆. Thus, inthe end we obtain an improvement not only for some small special cases but on the general asymptoticbound on the expansion of ∆-regular graphs given by Bollobás

  • 15.
    Lampis, Michael
    et al.
    National Technical University of Athens.
    Ginis, Kyriakos G.
    Papakyriakou, Michalis A.
    Papaspyrou, Nikolaos S.
    Quantum Data and Control Made Easier2008In: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, E-ISSN 1571-0661, Vol. 210, no C, p. 85-105Article in journal (Refereed)
    Abstract [en]

    In this paper we define nQML, a functional quantum programming language that follows the “quantum data and control” paradigm. In comparison to Altenkirch and Grattage's QML, the control constructs of nQML are simpler and can implement quantum algorithms more directly and naturally. We avoid the unnecessary complexities of a linear type system by using types that carry the address of qubits in the quantum state. We provide a denotational semantics over density matrices and unitary transformations, inspired by Selinger's semantics for QPL. Our semantics leads naturally to an interpreter for nQML, written in Haskell. We also explore the extension of nQML with polymorphic higher-order functions.

  • 16.
    Lampis, Michael
    et al.
    City University, New York.
    Ginis, Kyriakos G.
    Papaspyroy, Nikolaos S.
    Quantum Data and Control Made Easier2006In: Proceedings of the 4th International Workshop on Quantum Programming Languages, 2006, p. 73-87Conference paper (Refereed)
    Abstract [en]

    In this paper we define nQML, a functional quantum programming language that follows the ``quantum data and control'' paradigm. In comparison to Altenkirch and Grattage's QML, the control constructs of nQML are simpler and can implement quantum algorithms more directly and naturally. We avoid the unnecessary complexities of a linear type system by using types that carry the address of qubits in the quantum state. We provide a denotational semantics over density matrices and unitary transformations, inspired by Selinger's semantics for QPL. Our semantics leads naturally to an interpreter for nQML, written in Haskell.

  • 17.
    Lampis, Michael
    et al.
    University of New York.
    Kaouri, Georgia
    Mitsou, Valia
    On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures2011In: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 8, no 1, p. 129-138Article in journal (Refereed)
    Abstract [en]

    We place our focus on the gap between treewidth's success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically HAMILTONIAN CIRCUIT and MAX CUT, and the failure of its directed variants (directed treewidth (Johnson et al., 2001 [13]), DAG-width (Obdrzalek, 20061141) and Kelly-width (Hunter and Kreutzer, 2007[15]) to replicate it in the realm of digraphs. We answer the question of why this gap exists by giving two hardness results: we show that DIRECTED HAMILTONIAN CIRCUIT is W[2]-hard when the parameter is the width of the input graph, for any of these widths, and that MAX DI CUT remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Along the way, we extend our reduction for DIRECTED HAMILTONIAN CIRCUIT to show that the related MINIMUM LEAF OUTBRANCHING problem is also W[2]-hard when naturally parameterized by the number of leaves of the solution, even if the input graph has constant width. All our results also apply to directed pathwidth and cycle rank.

  • 18.
    Lampis, Michael
    et al.
    City University, New York.
    Kaouri, Georgia
    Mitsou, Valia
    On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures2008In: Algorithms And Computation, Proceedings, Springer Berlin/Heidelberg, 2008, p. 220-231Conference paper (Refereed)
    Abstract [en]

    We place our focus on the gap between treewidth’s success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically Hamiltonian CircuitandMax Cut , and the failure of its directed variants (directed tree-width [9], DAG-width [11] and kelly-width [8]) to replicate it in the realm of digraphs.We answer the question of why this gap exists by giving two hardness results: we show that Directed Hamiltonian CircuitisW [2]-hard when the parameter is the width of the input graph, for any of these widths, and that Max Di Cut remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Our results also apply to directed pathwidth. (Eligible for best student paper)

  • 19.
    Lampis, Michael
    et al.
    National Technical University of Athens.
    Mitsou, Valia
    The Ferry Cover Problem2009In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 44, no 2, p. 215-229Article in journal (Refereed)
    Abstract [en]

    In this paper we define and study a family of optimization problems called FERRY problems, which may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. We present the FERRY COVER problem (FC), where the objective is to determine the minimum required boat size to safely transport n items represented by a graph G and demonstrate a close connection with VERTEX COVER which leads to hardness and approximation results. We also completely solve the problem on trees. Then we focus on a variation of the same problem with the added constraint that only 1 round-trip is allowed (FC(1)). We present a reduction from MAX-NAE{3}-SAT which shows that this problem is NP-hard and APX-hard. We also provide an approximation algorithm for bipartite graphs with a factor asymptotically equal to 4/3 and a 1.56-approximation algorithm for planar graphs. Finally, we generalize the above problem to define FC(m), where at most m round-trips are allowed, and MFT(k), which is the problem of minimizing the number of round-trips when the boat capacity is k. We present some preliminary lemmata for both, which provide bounds on the value of the optimal solution, and relate them to FC.

  • 20.
    Lampis, Michael
    et al.
    National Technical University of Athens.
    Mitsou, Valia
    The Ferry Cover Problem2007In: Fun with Algorithms, Proceedings / [ed] Crescenzi, P; Prencipe, G; Pucci, G, Springer Berlin/Heidelberg, 2007, p. 227-239Conference paper (Refereed)
    Abstract [en]

    In the classical wolf-goat-cabbage puzzle, a ferry boat man must ferry three items across a river using a boat that has room for only one, without leaving two incompatible items on the same bank alone. In this paper we define and study a family of optimization problems called FERRY problems, which may be viewed as generalizations of this familiar puzzle. In all FERRY problems we are given a set of items and a graph with edges connecting items that must not be left together unattended. We present the FERRY COVER problem (FC), where the objective is to determine the minimum required boat size and demonstrate a close connection with VERTEX COVER which leads to hardness and approximation results. We also completely solve the problem on trees. Then we focus on a variation of the same problem with the added constraint that only I round-trip is allowed (FC1). We present a reduction from MAX-NAE-{3}-SAT which shows that this problem is NP-hard and APX-hard. We also provide an approximation algorithm for trees with a factor asymptotically equal to 4/3. Finally, we generalize the above problem to define FC, where at most m round-trips are allowed, and MFTk, which is the problem of minimizing the number of round-trips when the boat capacity is k. We present some preliminary lemmata for both, which provide bounds on the value of the optimal solution, and relate them to FC.

  • 21.
    Lampis, Michael
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mitsou, Valia
    Soltys, Karolina
    Scrabble is PSPACE-Complete2012Conference paper (Refereed)
    Abstract [en]

    In this paper we study the computational complexity of the game of Scrabble.We prove the PSPACE-completeness of a derandomized model of the game, answeringan open question of Erik Demaine and Robert Hearn.

  • 22.
    Lampis, Michail
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Improved inapproximability for TSP2012In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, p. 243-253Conference paper (Refereed)
    Abstract [en]

    The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best known inapproximability threshold known is 220/219 due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to 185/184.

  • 23.
    Lampis, Michail
    KTH.
    Improved inapproximability for TSP2014In: Theory of Computing, E-ISSN 1557-2862, Vol. 10, p. 217-236Article in journal (Refereed)
    Abstract [en]

    The Traveling Salesman Problem is one of the most studied problems in the theory of algorithms and its approximability is a long-standing open question. Prior to the present work, the best known inapproximability threshold was 220/219, due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded-occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to 185/184. 

  • 24.
    Lampis, Michail
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Model checking lower bounds for simple graphs2013In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, p. 673-683Conference paper (Refereed)
    Abstract [en]

    A well-known result by Frick and Grohe shows that deciding FO logic on trees involves a parameter dependence that is a tower of exponentials. Though this lower bound is tight for Courcelle's theorem, it has been evaded by a series of recent meta-theorems for other graph classes. Here we provide some additional non-elementary lower bound results, which are in some senses stronger. Our goal is to explain common traits in these recent meta-theorems and identify barriers to further progress. More specifically, first, we show that on the class of threshold graphs, and therefore also on any union and complement-closed class, there is no model-checking algorithm with elementary parameter dependence even for FO logic. Second, we show that there is no model-checking algorithm with elementary parameter dependence for MSO logic even restricted to paths (or equivalently to unary strings), unless EXP=NEXP. As a corollary, we resolve an open problem on the complexity of MSO model-checking on graphs of bounded max-leaf number. Finally, we look at MSO on the class of colored trees of depth d. We show that, assuming the ETH, for every fixed d ≥ 1 at least d + 1 levels of exponentiation are necessary for this problem, thus showing that the (d + 1)-fold exponential algorithm recently given by Gajarský and Hliněnỳ is essentially optimal.

  • 25. Michael, Lampis
    Parameterized Maximum Path Coloring2011Conference paper (Refereed)
    Abstract [en]

    We study the well-known Max Path Coloring problem from a parameterized point of view, focusing on trees and low-treewidth networks. We observe the existence of a variety of reasonable parameters for the problem, such as the maximum degree and treewidth of the net- work graph, the number of available colors and the number of requests one seeks to satisfy or reject. In an eort to understand the impact of each of these parameters on the problem's complexity we study various pa- rameterized versions of the problem deriving xed-parameter tractability and hardness results both for undirected and bi-directed graphs

    Download full text (pdf)
    fulltext
1 - 25 of 25
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf