CINXE.COM
Search | arXiv e-print repository
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/> <!-- new favicon config and versions by realfavicongenerator.net --> <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b"> <!-- end favicon config --> <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a> <!-- contains Cornell logo and sponsor statement --> <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div> <!-- contains arXiv identity and search bar --> <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div> <!-- closes identity --> <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–14 of 14 results for author: <span class="mathjax">Aravind, N R</span> </h1> </div> <div class="level-right is-hidden-mobile"> <!-- feedback for mobile is moved to footer --> <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a> </span> </div> </div> <div class="content"> <form method="GET" action="/search/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Aravind%2C+N+R">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Aravind, N R"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Aravind%2C+N+R&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Aravind, N R"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2406.01730">arXiv:2406.01730</a> <span> [<a href="https://arxiv.org/pdf/2406.01730">pdf</a>, <a href="https://arxiv.org/ps/2406.01730">ps</a>, <a href="https://arxiv.org/format/2406.01730">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> The Parameterized Complexity of Terminal Monitoring Set </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Saxena%2C+R">Roopam Saxena</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2406.01730v1-abstract-short" style="display: inline;"> In Terminal Monitoring Set (TMS), the input is an undirected graph $G=(V,E)$, together with a collection $T$ of terminal pairs and the goal is to find a subset $S$ of minimum size that hits a shortest path between every pair of terminals. We show that this problem is W[2]-hard with respect to solution size. On the positive side, we show that TMS is fixed parameter tractable with respect to solutio… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2406.01730v1-abstract-full').style.display = 'inline'; document.getElementById('2406.01730v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2406.01730v1-abstract-full" style="display: none;"> In Terminal Monitoring Set (TMS), the input is an undirected graph $G=(V,E)$, together with a collection $T$ of terminal pairs and the goal is to find a subset $S$ of minimum size that hits a shortest path between every pair of terminals. We show that this problem is W[2]-hard with respect to solution size. On the positive side, we show that TMS is fixed parameter tractable with respect to solution size plus distance to cluster, solution size plus neighborhood diversity, and feedback edge number. For the weighted version of the problem, we obtain a FPT algorithm with respect to vertex cover number, and for a relaxed version of the problem, we show that it is W[1]-hard with respect to solution size plus feedback vertex number. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2406.01730v1-abstract-full').style.display = 'none'; document.getElementById('2406.01730v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 June, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2307.03488">arXiv:2307.03488</a> <span> [<a href="https://arxiv.org/pdf/2307.03488">pdf</a>, <a href="https://arxiv.org/format/2307.03488">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Line-Constrained $k$-Semi-Obnoxious Facility Location </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Singireddy%2C+V+R">Vishwanath R. Singireddy</a>, <a href="/search/cs?searchtype=author&query=Basappa%2C+M">Manjanna Basappa</a>, <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2307.03488v2-abstract-short" style="display: inline;"> Suppose we are given a set $\cal B$ of blue points and a set $\cal R$ of red points, all lying above a horizontal line $\ell$, in the plane. Let the weight of a given point $p_i\in {\cal B}\cup{\cal R}$ be $w_i>0$ if $p_i\in {\cal B}$ and $w_i<0$ if $p_i\in {\cal R}$, $|{\cal B}\cup{\cal R}|=n$, and $d^0$($=d\setminus\partial d$) be the interior of any geometric object $d$. We wish to pack $k$ non… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2307.03488v2-abstract-full').style.display = 'inline'; document.getElementById('2307.03488v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2307.03488v2-abstract-full" style="display: none;"> Suppose we are given a set $\cal B$ of blue points and a set $\cal R$ of red points, all lying above a horizontal line $\ell$, in the plane. Let the weight of a given point $p_i\in {\cal B}\cup{\cal R}$ be $w_i>0$ if $p_i\in {\cal B}$ and $w_i<0$ if $p_i\in {\cal R}$, $|{\cal B}\cup{\cal R}|=n$, and $d^0$($=d\setminus\partial d$) be the interior of any geometric object $d$. We wish to pack $k$ non-overlapping congruent disks $d_1$, $d_2$, \ldots, $d_k$ of minimum radius, centered on $\ell$ such that $\sum\limits_{j=1}^k\sum\limits_{\{i:\exists p_i\in{\cal R}, p_i\in d_j^0\}}w_i+\sum\limits_{j=1}^k\sum\limits_{\{i:\exists p_i\in{\cal B}, p_i\in d_j\}}w_i$ is maximized, i.e., the sum of the weights of the points covered by $\bigcup\limits_{j=1}^kd_j$ is maximized. Here, the disks are the obnoxious or undesirable facilities generating nuisance or damage (with quantity equal to $w_i$) to every demand point (e.g., population center) $p_i\in {\cal R}$ lying in their interior. In contrast, they are the desirable facilities giving service (equal to $w_i$) to every demand point $p_i\in {\cal B}$ covered by them. The line $\ell$ represents a straight highway or railway line. These $k$ semi-obnoxious facilities need to be established on $\ell$ to receive the largest possible overall service for the nearby attractive demand points while causing minimum damage to the nearby repelling demand points. We show that the problem can be solved optimally in $O(n^4k^2)$ time. Subsequently, we improve the running time to $O(n^3k \cdot\max{(\log n, k)})$. The above-weighted variation of locating $k$ semi-obnoxious facilities may generalize the problem that Bereg et al. (2015) studied where $k=1$ i.e., the smallest radius maximum weight circle is to be centered on a line. Furthermore, we addressed two special cases of the problem where points do not have arbitrary weights. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2307.03488v2-abstract-full').style.display = 'none'; document.getElementById('2307.03488v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 July, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2209.08757">arXiv:2209.08757</a> <span> [<a href="https://arxiv.org/pdf/2209.08757">pdf</a>, <a href="https://arxiv.org/ps/2209.08757">ps</a>, <a href="https://arxiv.org/format/2209.08757">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Parameterized Complexity of Path Set Packing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Saxena%2C+R">Roopam Saxena</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2209.08757v3-abstract-short" style="display: inline;"> In Path Set Packing, the input is an undirected graph $G$, a collection $\calp$ of simple paths in $G$, and a positive integer $k$. The problem is to decide whether there exist $k$ edge-disjoint paths in $\calp$. We study the parameterized complexity of Path Set Packing with respect to both natural and structural parameters. We show that the problem is $W[1]$-hard with respect to vertex cover numb… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.08757v3-abstract-full').style.display = 'inline'; document.getElementById('2209.08757v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2209.08757v3-abstract-full" style="display: none;"> In Path Set Packing, the input is an undirected graph $G$, a collection $\calp$ of simple paths in $G$, and a positive integer $k$. The problem is to decide whether there exist $k$ edge-disjoint paths in $\calp$. We study the parameterized complexity of Path Set Packing with respect to both natural and structural parameters. We show that the problem is $W[1]$-hard with respect to vertex cover number, and $W[1]$-hard respect to pathwidth plus maximum degree plus solution size. These results answer an open question raised in COCOON 2018. On the positive side, we present an FPT algorithm parameterized by feedback vertex number plus maximum degree, and present an FPT algorithm parameterized by treewidth plus maximum degree plus maximum length of a path in $\calp$. These positive results complement the hardness of Path Set Packing with respect to any subset of the parameters used in the FPT algorithms. We also give a $4$-approximation algorithm for maximum path set packing problem which runs in FPT time when parameterized by feedback edge number. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.08757v3-abstract-full').style.display = 'none'; document.getElementById('2209.08757v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2203.14864">arXiv:2203.14864</a> <span> [<a href="https://arxiv.org/pdf/2203.14864">pdf</a>, <a href="https://arxiv.org/format/2203.14864">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Chess is hard even for a single player </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Misra%2C+N">Neeldhara Misra</a>, <a href="/search/cs?searchtype=author&query=Mittal%2C+H">Harshil Mittal</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2203.14864v2-abstract-short" style="display: inline;"> We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 x 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. Th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.14864v2-abstract-full').style.display = 'inline'; document.getElementById('2203.14864v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2203.14864v2-abstract-full" style="display: none;"> We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 x 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with $n$ pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.14864v2-abstract-full').style.display = 'none'; document.getElementById('2203.14864v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 March, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 March, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">22 pages, a slightly shorter version to appear in FUN 2022</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2107.08584">arXiv:2107.08584</a> <span> [<a href="https://arxiv.org/pdf/2107.08584">pdf</a>, <a href="https://arxiv.org/format/2107.08584">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Perfectly Matched Sets in Graphs: Parameterized and Exact Computation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Saxena%2C+R">Roopam Saxena</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2107.08584v4-abstract-short" style="display: inline;"> In an undirected graph $G=(V,E)$, we say $(A,B)$ is a pair of perfectly matched sets if $A$ and $B$ are disjoint subsets of $V$ and every vertex in $A$ (resp. $B$) has exactly one neighbor in $B$ (resp. $A$). The size of a pair of perfectly matched sets $(A,B)$ is $|A|=|B|$. The PERFECTLY MATCHED SETS problem is to decide whether a given graph $G$ has a pair of perfectly matched sets of size $k$.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.08584v4-abstract-full').style.display = 'inline'; document.getElementById('2107.08584v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2107.08584v4-abstract-full" style="display: none;"> In an undirected graph $G=(V,E)$, we say $(A,B)$ is a pair of perfectly matched sets if $A$ and $B$ are disjoint subsets of $V$ and every vertex in $A$ (resp. $B$) has exactly one neighbor in $B$ (resp. $A$). The size of a pair of perfectly matched sets $(A,B)$ is $|A|=|B|$. The PERFECTLY MATCHED SETS problem is to decide whether a given graph $G$ has a pair of perfectly matched sets of size $k$. We show that PMS is $W[1]$-hard when parameterized by solution size $k$ even when restricted to split graphs and bipartite graphs. We observe that PMS is FPT when parameterized by clique-width, and give FPT algorithms with respect to the parameters distance to cluster, distance to co-cluster and treewidth. Complementing FPT results, we show that PMS does not admit a polynomial kernel when parameterized by vertex cover number unless $NP\subseteq coNP/poly$. We also provide an exact exponential algorithm running in time $O^*(1.966^n)$. Finally, considering graphs with structural assumptions, we show that PMS remains $NP$-hard on planar graphs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.08584v4-abstract-full').style.display = 'none'; document.getElementById('2107.08584v4-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2101.06998">arXiv:2101.06998</a> <span> [<a href="https://arxiv.org/pdf/2101.06998">pdf</a>, <a href="https://arxiv.org/ps/2101.06998">ps</a>, <a href="https://arxiv.org/format/2101.06998">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> An FPT algorithm for Matching Cut and d-cut </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N R Aravind</a>, <a href="/search/cs?searchtype=author&query=Saxena%2C+R">Roopam Saxena</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2101.06998v3-abstract-short" style="display: inline;"> Given a positive integer $d$, the d-CUT is the problem of deciding if an undirected graph $G=(V,E)$ has a cut $(A,B)$ such that every vertex in $A$ (resp. $B$) has at most $d$ neighbors in $B$ (resp. $A$). For $d=1$, the problem is referred to as MATCHING CUT. Gomes and Sau, in IPEC 2019, gave the first fixed parameter tractable algorithm for d-CUT parameterized by maximum number of the crossing e… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2101.06998v3-abstract-full').style.display = 'inline'; document.getElementById('2101.06998v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2101.06998v3-abstract-full" style="display: none;"> Given a positive integer $d$, the d-CUT is the problem of deciding if an undirected graph $G=(V,E)$ has a cut $(A,B)$ such that every vertex in $A$ (resp. $B$) has at most $d$ neighbors in $B$ (resp. $A$). For $d=1$, the problem is referred to as MATCHING CUT. Gomes and Sau, in IPEC 2019, gave the first fixed parameter tractable algorithm for d-CUT parameterized by maximum number of the crossing edges in the cut (i.e. the size of edge cut). However, their paper doesn't provide an explicit bound on the running time, as it indirectly relies on a MSOL formulation and Courcelle's Theorem. Motivated by this, we design and present an FPT algorithm for d-CUT for general graphs with running time $2^{O(k\log k)}n^{O(1)}$ where $k$ is the maximum size of the edge cut. This is the first FPT algorithm for the d-CUT and MATCHING CUT with an explicit dependence on this parameter. We also observe that there is no algorithm solving MATCHING CUT in time $2^{o(k)}n^{O(1)}$ where $k$ is the maximum size of the edge cut unless ETH fails. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2101.06998v3-abstract-full').style.display = 'none'; document.getElementById('2101.06998v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 January, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2010.01286">arXiv:2010.01286</a> <span> [<a href="https://arxiv.org/pdf/2010.01286">pdf</a>, <a href="https://arxiv.org/format/2010.01286">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/978-3-030-39219-2_36">10.1007/978-3-030-39219-2_36 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Planar projections of graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Maniyar%2C+U">Udit Maniyar</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2010.01286v1-abstract-short" style="display: inline;"> We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on $n$ vertices has a representation in $\lceil \sqrt{n/2}+1 \rceil$ planes. In 3 dimensions, we show that there exist graphs with $6n-15$ edges that can be projected onto two or… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.01286v1-abstract-full').style.display = 'inline'; document.getElementById('2010.01286v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.01286v1-abstract-full" style="display: none;"> We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on $n$ vertices has a representation in $\lceil \sqrt{n/2}+1 \rceil$ planes. In 3 dimensions, we show that there exist graphs with $6n-15$ edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of parameters such as geometric thickness and linear arboricity. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.01286v1-abstract-full').style.display = 'none'; document.getElementById('2010.01286v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted at CALDAM 2020</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> In: Changat M., Das S. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2020. Lecture Notes in Computer Science, vol 12016. Springer, Cham (2020) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1912.13328">arXiv:1912.13328</a> <span> [<a href="https://arxiv.org/pdf/1912.13328">pdf</a>, <a href="https://arxiv.org/ps/1912.13328">ps</a>, <a href="https://arxiv.org/format/1912.13328">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Structure and colour in triangle-free graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Cambie%2C+S">Stijn Cambie</a>, <a href="/search/cs?searchtype=author&query=van+Batenburg%2C+W+C">Wouter Cames van Batenburg</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Patel%2C+V">Viresh Patel</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1912.13328v2-abstract-short" style="display: inline;"> Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $蠂$ contains a rainbow independent set of size $\lceil\frac12蠂\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13328v2-abstract-full').style.display = 'inline'; document.getElementById('1912.13328v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1912.13328v2-abstract-full" style="display: none;"> Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $蠂$ contains a rainbow independent set of size $\lceil\frac12蠂\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $蠂$ contains an induced cycle of length $惟(蠂\log蠂)$ as $蠂\to\infty$. Even if one only demands an induced path of length $惟(蠂\log蠂)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13328v2-abstract-full').style.display = 'none'; document.getElementById('1912.13328v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 March, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 31 December, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages; in v2 one section was removed due to a subtle error</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.04016">arXiv:1804.04016</a> <span> [<a href="https://arxiv.org/pdf/1804.04016">pdf</a>, <a href="https://arxiv.org/ps/1804.04016">ps</a>, <a href="https://arxiv.org/format/1804.04016">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Bipartitioning Problems on Graphs with Bounded Tree-Width </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Kalyanasundaram%2C+S">Subrahmanyam Kalyanasundaram</a>, <a href="/search/cs?searchtype=author&query=Kare%2C+A+S">Anjeneya Swami Kare</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.04016v1-abstract-short" style="display: inline;"> For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two non-empty sets A and B such that neither the induced graph G[A] nor G[B] contain H (i) as a subgraph? (ii) as an induced subgraph? These problems are NP-complete and are expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle's th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.04016v1-abstract-full').style.display = 'inline'; document.getElementById('1804.04016v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.04016v1-abstract-full" style="display: none;"> For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two non-empty sets A and B such that neither the induced graph G[A] nor G[B] contain H (i) as a subgraph? (ii) as an induced subgraph? These problems are NP-complete and are expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle's theorem implies linear time solvability on graphs with bounded tree-width. This approach yields algorithms with running time f(|phi|, t) * n, where |phi| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f(|phi|, t) on |phi| can be as bad as a tower of exponentials. In this paper, we present explicit combinatorial algorithms for these problems for graphs G whose tree-width is bounded. We obtain 2^{O(t^r)} * n time algorithms when H is any fixed graph of order r. In the special case when H = K_r, a complete graph on r vertices, we get an 2^{O(t+r \log t)} * n time algorithm. The techniques can be extended to provide FPT algorithms to determine the smallest number q such that V can be partitioned into q parts such that none of the parts have H as a subgraph (induced subgraph). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.04016v1-abstract-full').style.display = 'none'; document.getElementById('1804.04016v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1705.08282">arXiv:1705.08282</a> <span> [<a href="https://arxiv.org/pdf/1705.08282">pdf</a>, <a href="https://arxiv.org/format/1705.08282">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Algorithms and hardness results for happy coloring problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Kalyanasundaram%2C+S">Subrahmanyam Kalyanasundaram</a>, <a href="/search/cs?searchtype=author&query=Kare%2C+A+S">Anjeneya Swami Kare</a>, <a href="/search/cs?searchtype=author&query=Lauri%2C+J">Juho Lauri</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1705.08282v1-abstract-short" style="display: inline;"> In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.08282v1-abstract-full').style.display = 'inline'; document.getElementById('1705.08282v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1705.08282v1-abstract-full" style="display: none;"> In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of happy edges. When we want to maximize the number of happy vertices, the problem is known as Maximum Happy Vertices (k-MHV). We further study the complexity of the problems and their weighted variants. For instance, we prove that for every k >= 3, both problems are NP-complete for bipartite graphs and k-MHV remains hard for split graphs. In terms of exact algorithms, we show both problems can be solved in time O*(2^n), and give an even faster O*(1.89^n)-time algorithm when k = 3. From a parameterized perspective, we give a linear vertex kernel for Weighted k-MHE, where edges are weighted and the goal is to obtain happy edges of at least a specified total weight. Finally, we prove both problems are solvable in polynomial-time when the graph has bounded treewidth or bounded neighborhood diversity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.08282v1-abstract-full').style.display = 'none'; document.getElementById('1705.08282v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 May, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1509.08807">arXiv:1509.08807</a> <span> [<a href="https://arxiv.org/pdf/1509.08807">pdf</a>, <a href="https://arxiv.org/format/1509.08807">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$-free Edge Modification Problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Sandeep%2C+R+B">R. B. Sandeep</a>, <a href="/search/cs?searchtype=author&query=Sivadasan%2C+N">Naveen Sivadasan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1509.08807v1-abstract-short" style="display: inline;"> For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completel… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1509.08807v1-abstract-full').style.display = 'inline'; document.getElementById('1509.08807v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1509.08807v1-abstract-full" style="display: none;"> For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two non-edges and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Additionally, we prove that, these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1509.08807v1-abstract-full').style.display = 'none'; document.getElementById('1509.08807v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 September, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">16 pages. arXiv admin note: substantial text overlap with arXiv:1507.06341</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1508.06511">arXiv:1508.06511</a> <span> [<a href="https://arxiv.org/pdf/1508.06511">pdf</a>, <a href="https://arxiv.org/ps/1508.06511">ps</a>, <a href="https://arxiv.org/format/1508.06511">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> On the expressive power of read-once determinants </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Joglekar%2C+P+S">Pushkar S. Joglekar</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1508.06511v1-abstract-short" style="display: inline;"> We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in $M$. A monomial set $S$ is said to be expressible as read-$k$ projection of determin… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1508.06511v1-abstract-full').style.display = 'inline'; document.getElementById('1508.06511v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1508.06511v1-abstract-full" style="display: none;"> We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in $M$. A monomial set $S$ is said to be expressible as read-$k$ projection of determinant if there is a read-$k$ projection of determinant $f$ such that the monomial set of $f$ is equal to $S$. We obtain basic results relating read-$k$ determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large $n$, the $n \times n$ permanent polynomial $Perm_n$ and the elementary symmetric polynomials of degree $d$ on $n$ variables $S_n^d$ for $2 \leq d \leq n-2$ are not expressible as read-once projection of determinant, whereas $mon(Perm_n)$ and $mon(S_n^d)$ are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1508.06511v1-abstract-full').style.display = 'none'; document.getElementById('1508.06511v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 August, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1507.06341">arXiv:1507.06341</a> <span> [<a href="https://arxiv.org/pdf/1507.06341">pdf</a>, <a href="https://arxiv.org/format/1507.06341">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Parameterized lower bound and NP-completeness of some $H$-free Edge Deletion problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Sandeep%2C+R+B">R. B. Sandeep</a>, <a href="/search/cs?searchtype=author&query=Sivadasan%2C+N">Naveen Sivadasan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1507.06341v2-abstract-short" style="display: inline;"> For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. We prove that $H$-free Edge Deletion is NP-complete if $H$ is a graph with at least two edges and $H$ has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1507.06341v2-abstract-full').style.display = 'inline'; document.getElementById('1507.06341v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1507.06341v2-abstract-full" style="display: none;"> For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. We prove that $H$-free Edge Deletion is NP-complete if $H$ is a graph with at least two edges and $H$ has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1507.06341v2-abstract-full').style.display = 'none'; document.getElementById('1507.06341v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 September, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 July, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages, COCOA 15 accepted paper</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1407.7156">arXiv:1407.7156</a> <span> [<a href="https://arxiv.org/pdf/1407.7156">pdf</a>, <a href="https://arxiv.org/ps/1407.7156">ps</a>, <a href="https://arxiv.org/format/1407.7156">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> On Polynomial Kernelization of $\mathcal{H}$-free Edge Deletion </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Sandeep%2C+R+B">R. B. Sandeep</a>, <a href="/search/cs?searchtype=author&query=Sivadasan%2C+N">Naveen Sivadasan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1407.7156v2-abstract-short" style="display: inline;"> For a set of graphs $\mathcal{H}$, the \textsc{$\mathcal{H}$-free Edge Deletion} problem asks to find whether there exist at most $k$ edges in the input graph whose deletion results in a graph without any induced copy of $H\in\mathcal{H}$. In \cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if $\mathcal{H}$ is of finite cardinality. However, it is proved in \cite{cai2… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1407.7156v2-abstract-full').style.display = 'inline'; document.getElementById('1407.7156v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1407.7156v2-abstract-full" style="display: none;"> For a set of graphs $\mathcal{H}$, the \textsc{$\mathcal{H}$-free Edge Deletion} problem asks to find whether there exist at most $k$ edges in the input graph whose deletion results in a graph without any induced copy of $H\in\mathcal{H}$. In \cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if $\mathcal{H}$ is of finite cardinality. However, it is proved in \cite{cai2013incompressibility} that if $\mathcal{H}$ is a singleton set containing $H$, for a large class of $H$, there exists no polynomial kernel unless $coNP\subseteq NP/poly$. In this paper, we present a polynomial kernel for this problem for any fixed finite set $\mathcal{H}$ of connected graphs and when the input graphs are of bounded degree. We note that there are \textsc{$\mathcal{H}$-free Edge Deletion} problems which remain NP-complete even for the bounded degree input graphs, for example \textsc{Triangle-free Edge Deletion}\cite{brugmann2009generating} and \textsc{Custer Edge Deletion($P_3$-free Edge Deletion)}\cite{komusiewicz2011alternative}. When $\mathcal{H}$ contains $K_{1,s}$, we obtain a stronger result - a polynomial kernel for $K_t$-free input graphs (for any fixed $t> 2$). We note that for $s>9$, there is an incompressibility result for \textsc{$K_{1,s}$-free Edge Deletion} for general graphs \cite{cai2012polynomial}. Our result provides first polynomial kernels for \textsc{Claw-free Edge Deletion} and \textsc{Line Edge Deletion} for $K_t$-free input graphs which are NP-complete even for $K_4$-free graphs\cite{yannakakis1981edge} and were raised as open problems in \cite{cai2013incompressibility,open2013worker}. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1407.7156v2-abstract-full').style.display = 'none'; document.getElementById('1407.7156v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 November, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 26 July, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2014. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages. IPEC 2014 accepted paper</span> </p> </li> </ol> <div class="is-hidden-tablet"> <!-- feedback for mobile only --> <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a> </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary"> <!-- MetaColumn 1 --> <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div> <!-- end MetaColumn 1 --> <!-- MetaColumn 2 --> <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div> <!-- end MetaColumn 2 --> </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>