9 Search Results for "Bang-Jensen, Jørgen"


Document
A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands

Authors: Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
In the Vertex Connectivity Survivable Network Design (VC-SNDP) problem, the input is a graph G and a function d: V(G) × V(G) → ℕ that encodes the vertex-connectivity demands between pairs of vertices. The objective is to find the smallest subgraph H of G that satisfies all these demands. It is a well-studied NP-complete problem that generalizes several network design problems. We consider the case of uniform demands, where for every vertex pair (u,v) the connectivity demand d(u,v) is a fixed integer κ. It is an important problem with wide applications. We study this problem in the realm of Parameterized Complexity. In this setting, in addition to G and d we are given an integer 𝓁 as the parameter and the objective is to determine if we can remove at least 𝓁 edges from G without violating any connectivity constraints. This was posed as an open problem by Bang-Jansen et.al. [SODA 2018], who studied the edge-connectivity variant of the problem under the same settings. Using a powerful classification result of Lokshtanov et al. [ICALP 2018], Gutin et al. [JCSS 2019] recently showed that this problem admits a (non-uniform) FPT algorithm where the running time was unspecified. Further they also gave an (uniform) FPT algorithm for the case of κ = 2. In this paper we present a (uniform) FPT algorithm any κ that runs in time 2^{O(κ² 𝓁⁴ log 𝓁)}⋅ |V(G)|^O(1). Our algorithm is built upon new insights on vertex connectivity in graphs. Our main conceptual contribution is a novel graph decomposition called the Wheel decomposition. Informally, it is a partition of the edge set of a graph G, E(G) = X₁ ∪ X₂ … ∪ X_r, with the parts arranged in a cyclic order, such that each vertex v ∈ V(G) either has edges in at most two consecutive parts, or has edges in every part of this partition. The first kind of vertices can be thought of as the rim of the wheel, while the second kind form the hub. Additionally, the vertex cuts induced by these edge-sets in G have highly symmetric properties. Our main technical result, informally speaking, establishes that "nearly edge-minimal’’ κ-vertex connected graphs admit a wheel decomposition - a fact that can be exploited for designing algorithms. We believe that this decomposition is of independent interest and it could be a useful tool in resolving other open problems.

Cite as

Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 13:1-13:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bangjensen_et_al:LIPIcs.ESA.2023.13,
  author =	{Bang-Jensen, J{\o}rgen and Klinkby, Kristine Vitting and Misra, Pranabendu and Saurabh, Saket},
  title =	{{A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.13},
  URN =		{urn:nbn:de:0030-drops-186663},
  doi =		{10.4230/LIPIcs.ESA.2023.13},
  annote =	{Keywords: Parameterized Complexity, Vertex Connectivity, Network Design}
}
Document
A Succinct Formalization of the Completeness of First-Order Logic

Authors: Asta Halkjær From

Published in: LIPIcs, Volume 239, 27th International Conference on Types for Proofs and Programs (TYPES 2021)


Abstract
I succinctly formalize the soundness and completeness of a small Hilbert system for first-order logic in the proof assistant Isabelle/HOL. The proof combines and details ideas from de Bruijn, Henkin, Herbrand, Hilbert, Hintikka, Lindenbaum, Smullyan and others in a novel way, and I use a declarative style, custom notation and proof automation to obtain a readable formalization. The formalized definitions of Hintikka sets and Herbrand structures allow open and closed formulas to be treated uniformly, making free variables a non-concern. This paper collects important techniques in mathematical logic in a way suited for both study and further work.

Cite as

Asta Halkjær From. A Succinct Formalization of the Completeness of First-Order Logic. In 27th International Conference on Types for Proofs and Programs (TYPES 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 239, pp. 8:1-8:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{from:LIPIcs.TYPES.2021.8,
  author =	{From, Asta Halkj{\ae}r},
  title =	{{A Succinct Formalization of the Completeness of First-Order Logic}},
  booktitle =	{27th International Conference on Types for Proofs and Programs (TYPES 2021)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-254-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{239},
  editor =	{Basold, Henning and Cockx, Jesper and Ghilezan, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2021.8},
  URN =		{urn:nbn:de:0030-drops-167771},
  doi =		{10.4230/LIPIcs.TYPES.2021.8},
  annote =	{Keywords: First-Order Logic, Completeness, Isabelle/HOL}
}
Document
Verifying a Sequent Calculus Prover for First-Order Logic with Functions in Isabelle/HOL

Authors: Asta Halkjær From and Frederik Krogsdal Jacobsen

Published in: LIPIcs, Volume 237, 13th International Conference on Interactive Theorem Proving (ITP 2022)


Abstract
We describe the design, implementation and verification of an automated theorem prover for first-order logic with functions. The proof search procedure is based on sequent calculus and we formally verify its soundness and completeness in Isabelle/HOL using an existing abstract framework for coinductive proof trees. Our analytic completeness proof covers both open and closed formulas. Since our deterministic prover considers only the subset of terms relevant to proving a given sequent, we do so as well when building a countermodel from a failed proof. Finally, we formally connect our prover with the proof system and semantics of the existing SeCaV system. In particular, the prover can generate human-readable SeCaV proofs which are also machine-verifiable proof certificates.

Cite as

Asta Halkjær From and Frederik Krogsdal Jacobsen. Verifying a Sequent Calculus Prover for First-Order Logic with Functions in Isabelle/HOL. In 13th International Conference on Interactive Theorem Proving (ITP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 237, pp. 13:1-13:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{from_et_al:LIPIcs.ITP.2022.13,
  author =	{From, Asta Halkj{\ae}r and Jacobsen, Frederik Krogsdal},
  title =	{{Verifying a Sequent Calculus Prover for First-Order Logic with Functions in Isabelle/HOL}},
  booktitle =	{13th International Conference on Interactive Theorem Proving (ITP 2022)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-252-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{237},
  editor =	{Andronick, June and de Moura, Leonardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2022.13},
  URN =		{urn:nbn:de:0030-drops-167221},
  doi =		{10.4230/LIPIcs.ITP.2022.13},
  annote =	{Keywords: Isabelle/HOL, SeCaV, First-Order Logic, Prover, Soundness, Completeness}
}
Document
k-Distinct Branchings Admits a Polynomial Kernel

Authors: Jørgen Bang-Jensen, Kristine Vitting Klinkby, and Saket Saurabh

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
Unlike the problem of deciding whether a digraph D = (V,A) has 𝓁 in-branchings (or 𝓁 out-branchings) is polynomial time solvable, the problem of deciding whether a digraph D = (V,A) has an in-branching B^- and an out-branching B^+ which are arc-disjoint is NP-complete. Motivated by this, a natural optimization question that has been studied in the realm of Parameterized Complexity is called Rooted k-Distinct Branchings. In this problem, a digraph D = (V,A) with two prescribed vertices s,t are given as input and the question is whether D has an in-branching rooted at t and an out-branching rooted at s such that they differ on at least k arcs. Bang-Jensen et al. [Algorithmica, 2016 ] showed that the problem is fixed parameter tractable (FPT) on strongly connected digraphs. Gutin et al. [ICALP, 2017; JCSS, 2018 ] completely resolved this problem by designing an algorithm with running time 2^{𝒪(k² log² k)}n^{𝒪(1)}. Here, n denotes the number of vertices of the input digraph. In this paper, answering an open question of Gutin et al., we design a polynomial kernel for Rooted k-Distinct Branchings. In particular, we obtain the following: Given an instance (D,k,s,t) of Rooted k-Distinct Branchings, in polynomial time we obtain an equivalent instance (D',k',s,t) of Rooted k-Distinct Branchings such that |V(D')| ≤ 𝒪(k²) and the treewidth of the underlying undirected graph is at most 𝒪(k). This result immediately yields an FPT algorithm with running time 2^{𝒪(klog k)}+ n^{𝒪(1)}; improving upon the previous running time of Gutin et al. For our algorithms, we prove a structural result about paths avoiding many arcs in a given in-branching or out-branching. This result might turn out to be useful for getting other results for problems concerning in-and out-branchings.

Cite as

Jørgen Bang-Jensen, Kristine Vitting Klinkby, and Saket Saurabh. k-Distinct Branchings Admits a Polynomial Kernel. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 11:1-11:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bangjensen_et_al:LIPIcs.ESA.2021.11,
  author =	{Bang-Jensen, J{\o}rgen and Klinkby, Kristine Vitting and Saurabh, Saket},
  title =	{{k-Distinct Branchings Admits a Polynomial Kernel}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.11},
  URN =		{urn:nbn:de:0030-drops-145925},
  doi =		{10.4230/LIPIcs.ESA.2021.11},
  annote =	{Keywords: Digraphs, Polynomial Kernel, In-branching, Out-Branching}
}
Document
Component Order Connectivity in Directed Graphs

Authors: Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlström, and Anders Yeo

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
A directed graph D is semicomplete if for every pair x,y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V,A) and a pair of natural numbers k and 𝓁, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D-X has at most 𝓁 vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for 𝓁 = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, 𝓁, 𝓁+k and n-𝓁. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^*(2^(16k)) but not in time O^*(2^o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^*(2^(16k)) implies the upper bound O^*(2^(16(n-𝓁))) for the parameter n-𝓁. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n-𝓁)) unless ETH fails. Finally, we improve (in dependency on 𝓁) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter 𝓁+k on general digraphs from O^*(2^O(k𝓁 log (k𝓁))) to O^*(2^O(klog (k𝓁))). Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^*(2^o(klog 𝓁)) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).

Cite as

Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlström, and Anders Yeo. Component Order Connectivity in Directed Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 2:1-2:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bangjensen_et_al:LIPIcs.IPEC.2020.2,
  author =	{Bang-Jensen, J{\o}rgen and Eiben, Eduard and Gutin, Gregory and Wahlstr\"{o}m, Magnus and Yeo, Anders},
  title =	{{Component Order Connectivity in Directed Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.2},
  URN =		{urn:nbn:de:0030-drops-133058},
  doi =		{10.4230/LIPIcs.IPEC.2020.2},
  annote =	{Keywords: Parameterized Algorithms, component order connectivity, directed graphs, semicomplete digraphs}
}
Document
A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs

Authors: Jayakrishnan Madathil, Roohani Sharma, and Meirav Zehavi

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that |L| and |R| differ by at most 1 and the number of arcs from R to L is at most k. This problem, in general, is W-hard as it is known to be NP-hard even when k=0. We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection on semicomplete digraphs is one of a handful of problems that admit sub-exponential time fixed-parameter tractable algorithms. That is, we show that the problem admits a 2^{O(sqrt{k} log k)}n^{O(1)} time algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n,k,k^2)-splitters. To the best of our knowledge, this is the first time such pseudorandom objects have been used in the design of kernels. We believe that the framework of designing kernels using splitters could be applied to more problems that admit sub-exponential time algorithms via chromatic coding. To complement the above mentioned results, we prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments.

Cite as

Jayakrishnan Madathil, Roohani Sharma, and Meirav Zehavi. A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{madathil_et_al:LIPIcs.MFCS.2019.28,
  author =	{Madathil, Jayakrishnan and Sharma, Roohani and Zehavi, Meirav},
  title =	{{A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.28},
  URN =		{urn:nbn:de:0030-drops-109721},
  doi =		{10.4230/LIPIcs.MFCS.2019.28},
  annote =	{Keywords: bisection, semicomplete digraph, tournament, fpt algorithm, chromatic coding, polynomial kernel, splitters}
}
Document
The Price of Local Power Control in Wireless Scheduling

Authors: Magnús M. Halldórsson and Tigran Tonoyan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

Cite as

Magnús M. Halldórsson and Tigran Tonoyan. The Price of Local Power Control in Wireless Scheduling. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 529-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.FSTTCS.2015.529,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Tonoyan, Tigran},
  title =	{{The Price of Local Power Control in Wireless Scheduling}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{529--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.529},
  URN =		{urn:nbn:de:0030-drops-56243},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.529},
  annote =	{Keywords: Wireless Scheduling, Physical Model, Oblivious Power}
}
Document
Finding Even Subgraphs Even Faster

Authors: Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k edges(arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees--where the resulting graph is Eulerian,the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al.[Algorithmica, 2014] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time 2^O(k log k)n^O(1). They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time 2^O(k)n^O(1). It was also posed as an open problem at the School on Parameterized Algorithms and Complexity 2014, Bedlewo, Poland. In this paper we answer their question in the affirmative: using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2^O(k)n^O(1). The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

Cite as

Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Finding Even Subgraphs Even Faster. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 434-447, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.FSTTCS.2015.434,
  author =	{Goyal, Prachi and Misra, Pranabendu and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket},
  title =	{{Finding Even Subgraphs Even Faster}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{434--447},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.434},
  URN =		{urn:nbn:de:0030-drops-56336},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.434},
  annote =	{Keywords: Eulerian Edge Deletion, FPT, Representative Family.}
}
Document
Approximating Upper Degree-Constrained Partial Orientations

Authors: Marek Cygan and Tomasz Kociumaka

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
In the Upper Degree-Constrained Partial Orientation (UDPO) problem we are given an undirected graph G=(V,E), together with two degree constraint functions d^-,d^+:V -> N. The goal is to orient as many edges as possible, in such a way that for each vertex v in V the number of arcs entering v is at most d^-(v), whereas the number of arcs leaving v is at most d^+(v). This problem was introduced by Gabow [SODA'06], who proved it to be MAXSNP-hard (and thus APX-hard). In the same paper Gabow presented an LP-based iterative rounding 4/3-approximation algorithm. As already observed by Gabow, the problem in question is a special case of the classic 3-Dimensional Matching, which in turn is a special case of the k-Set Packing problem. Back in 2006 the best known polynomial time approximation algorithm for 3-Dimensional Matching was a simple local search by Hurkens and Schrijver [SIDMA'89], the approximation ratio of which is (3+epsilon)/2; hence the algorithm of Gabow was an improvement over the approach brought from the more general problems. In this paper we show that the UDPO problem when cast as 3-Dimensional Matching admits a special structure, which is obliviously exploited by the known approximation algorithms for k-Set Packing. In fact, we show that already the local-search routine of Hurkens and Schrijver gives (4+epsilon)/3-approximation when used for the instances coming from UDPO. Moreover, the recent approximation algorithm for 3-Set Packing [Cygan, FOCS'13] turns out to be a (5+epsilon)/4-approximation for UDPO. This improves over 4/3 as the best ratio known up to date for UDPO.

Cite as

Marek Cygan and Tomasz Kociumaka. Approximating Upper Degree-Constrained Partial Orientations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 212-224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{cygan_et_al:LIPIcs.APPROX-RANDOM.2015.212,
  author =	{Cygan, Marek and Kociumaka, Tomasz},
  title =	{{Approximating Upper Degree-Constrained Partial Orientations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{212--224},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.212},
  URN =		{urn:nbn:de:0030-drops-53040},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.212},
  annote =	{Keywords: graph orientations, degree-constrained orientations, approximation algorithm, local search}
}
  • Refine by Author
  • 3 Bang-Jensen, Jørgen
  • 3 Saurabh, Saket
  • 2 From, Asta Halkjær
  • 2 Klinkby, Kristine Vitting
  • 2 Misra, Pranabendu
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Automated reasoning
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 Completeness
  • 2 First-Order Logic
  • 2 Isabelle/HOL
  • 1 Digraphs
  • 1 Eulerian Edge Deletion
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2015
  • 2 2022
  • 1 2019
  • 1 2020
  • 1 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail